在哈斯克尔中构建无限列表

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]

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