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

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

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

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

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

repeatInts :: Int -> [Int]

так что вызов repeatInts 3 возвращает [1,2,3,1,2,3,1,2,3,1,2,3,..] ad infinitum.

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

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

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

Ответ 1

Используйте 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'

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

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

"Связывание узла" в вики Haskell
"Связывание узла" в комментарии GHC
"Объяснение" привязка узла" здесь в разделе Переполнение стека
Тег [tying-the-knot]

Ответ 2

Поздний ответ, но он также может быть написан следующим образом:

repeatInts :: Int -> [Int]
repeatInts 0 = []
repeatInts a = [1..a] ++ repeatInts a