Как создать бесконечно повторяющийся список в Haskell?

Я парень, работающий на С#, и пытаюсь выучить Haskell из веб-трансляций Эрика Мейера на канале 9. Я наткнулся на интересную головоломку, в которой нужно было пропустить все n элементов списка с помощью zip и mod.

every :: Int -> [a] -> [a]
every _ [] = []
every n xs = [x | (x,i) <- zip xs [1..], i `mod` n == 0]

Я подумал, что было бы более эффективно (для действительно больших списков или потоков), если бы мы могли избежать использования мода.

Я подумал о ленивом создании повторяющегося списка целых чисел, чтобы мы могли просто сравнить значение i с n.

repeatInts :: Int -> [Int]

так что вызов repeatInts 3 возвращает [1,2,3,1,2,3,1,2,3,1,2,3,..] до бесконечности.

Учитывая это, мы могли бы переопределить every следующим образом:

every :: Int -> [a] -> [a]
every _ [] = []
every n xs = [x | (x,i) <- zip xs (repeatInts n), i == n]

Итак, мои вопросы: как бы вы реализовали repeatInts?


list lazy-evaluation haskell
person Damian Powell    schedule 09.01.2010    source источник
comment
См. stackoverflow.com/questions/2026912/   -  person Charles Stewart    schedule 11.01.2010

Ответы (2)


arrow_upward
26
arrow_downward

Используйте cycle:

cycle :: [a] -> [a]

cycle связывает конечный список в циклический или, что то же самое, бесконечное повторение исходного списка. Это тождество в бесконечных списках.

Вы можете определить repeatInts в терминах cycle:

*Main> let repeatInts n = cycle [1..n]
*Main> :t repeatInts
repeatInts :: (Num t, Enum t) => t -> [t]
*Main> take 10 $ repeatInts 3
[1,2,3,1,2,3,1,2,3,1]

Для любопытных, GHC реализует cycle с

cycle [] = errorEmptyList "cycle"
cycle xs = xs' where xs' = xs ++ xs'

На чисто функциональном языке этот любопытный метод известен как завязывание узла, и он создает циклические структуры данных, а не бесконечные.

Подробнее см.

person Greg Bacon    schedule 10.01.2010
comment
Спасибо, gbacon. Почему-то я знал, что будет простой ответ! Теперь я могу копаться в работе cycle. - person Damian Powell; 10.01.2010
comment
Как ни странно, cycle является стандартным для Haskell '98, хотя циклические списки - нет. Посмотрите, что говорит об этом источник (выше) - вы можете получить или не получить циклический список... - person Charles Stewart; 11.01.2010
comment
как ни странно, этот Q/A сам по себе является примером проблемы XY. ;) пропуск каждого n-го элемента в списке не должен включать ни mod, ни счет до бесконечности. правильное решение, по-видимому, либо с zip с (cycle $ (0 <$ [2..n]) ++ [1]), либо через iterate с splitAt. :) - person Will Ness; 18.10.2017

arrow_upward
4
arrow_downward

Поздний ответ, но его также можно записать так:

repeatInts :: Int -> [Int]
repeatInts 0 = []
repeatInts a = [1..a] ++ repeatInts a
person Sam R.    schedule 10.05.2014