haskell - Haskell中无限列表的构造

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) 时间，那么将花费 O(M*N) 时间，其中 M 是您将检查constructInf的结果中的元素数。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]

但我不确定为什么你需要整个列表而不是最后一个元素。