Построение бесконечного списка в Хаскеле

Question

У меня есть две вещи для желаемого бесконечного списка: его первый элемент

x :: A

и функция, которая генерирует следующий элемент

f :: [A] -> A

Какой лучший (самый идиоматичный? Самый быстрый?) Способ создать бесконечный список? Я имею в виду

xs = x : f [x] : f [x, f [x]] : f [x, f [x], f [x, f [x]]] : ...

Answer 1

Функция, которую вы хотите, может быть реализована как:

constructInf :: ([a] -> a) -> a -> [a]
constructInf f x = xs
  where xs = x:map f (tail $ inits xs)

Производительность consrtuctInf зависит от производительности его функции аргумента f, Если предположить, f занимает O(N) время, затем constructInf займет время O(M*N), где M - количество элементов из результата constructInf что вы будете проверять.

Answer 2

Ты хочешь iterate,

take 10 $ iterate (+1) 0

= [0,1,2,3,4,5,6,7,8,9]

Если вам нужен весь список до сих пор, и вы не против перевернуть его, вы можете сделать это:

mkl f x0 = x0 : unfoldr (\xs -> let x = f xs in Just (x, x:xs)) [x0]

Если вам пока нужен весь список, и вы хотите, чтобы он был в порядке, он будет действительно неэффективным, но вы можете сделать это:

mkl' f x0 = x0 : unfoldr (\xs -> let x = f xs in Just (x, xs ++ [x])) [x0]

Но я не уверен, зачем вам нужен весь список, а не только последний элемент.