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

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

13 голосов
/ 10 января 2010

Я - парень на C #, пытаюсь научить себя Хаскеллу из трансляций Эрика Мейера на 9 канале. Я натолкнулся на интересную головоломку, которая включала пропуск всех 'n' элементов списка с использованием zip и мода. 

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?

Ответы [ 2 ]

20 голосов
/ 10 января 2010

Использование 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 with 

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

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

Дляподробности см.

2 голосов
/ 10 мая 2014

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

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