Как создать бесконечно повторяющийся список в 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'
В чисто функциональном языке эта любопытная техника известна как связывание узла, и она создает циклические структуры данных, а не бесконечные.
Подробнее см.
Ответ 2
Поздний ответ, но он также может быть написан следующим образом:
repeatInts :: Int -> [Int]
repeatInts 0 = []
repeatInts a = [1..a] ++ repeatInts a
