能否用fold实现Haskell中的iterate函数？

背景 #

我之前想实现一个功能：把函数f重复应用在参数z上，生成无限列表[z, f z, f (f z), f (f (f z)), ...]，这样就能用take n、takeWhile这类函数去截取。

一开始我觉得要处理无限列表，想到了repeat f，觉得应该用foldr来实现，但试了之后发现走不通：对无限列表用foldr的时候，累加器一般设成undefined（因为用不上），但像foldr (\f (x:xs) -> f x:x:xs) undefined (repeat f)这种写法，根本没法把初始参数z加进去。

问题 #

后来准备提问时，发现Haskell里已经有iterate函数了，它的实现是这样的：

{-# NOINLINE [1] iterate #-}
iterate :: (a -> a) -> a -> [a]
iterate f x =  x : iterate f (f x)

所以现在我的问题是：能不能用fold系列函数实现iterate？如果可以，怎么实现？不行的话，原因是什么？

解答 #

完全可以用foldr实现iterate，核心是利用Haskell的惰性求值特性，把初始值z整合到折叠逻辑里，而不是像你之前那样孤立地操作列表结构。

具体实现 #

第一种思路是借助repeat f生成无限个f的列表，然后用foldr从初始值z开始，不断将函数应用到前一个元素上构建列表：

iterateViaFoldr :: (a -> a) -> a -> [a]
iterateViaFoldr f z = z : foldr (\g acc -> g (head acc) : acc) [] (repeat f)

不过这个写法有小缺陷：每次取head acc会有额外开销，而且依赖acc永远非空（这里因为是无限列表所以没问题，但不够优雅）。

更简洁高效的写法是让foldr生成一个递归函数，再把初始值z作为参数传入：

iterateViaFoldr' :: (a -> a) -> a -> [a]
iterateViaFoldr' f z = foldr (\next step x -> x : step (next x)) (const []) (repeat f) z

这里的逻辑是：foldr遍历无限的repeat f列表，每一步生成一个函数——这个函数接收当前值x，返回x拼上“把下一个函数next应用到x后，继续执行后续步骤”的结果。最后把初始值z传给这个由foldr生成的函数，就得到了目标无限列表。

你之前尝试失败的原因 #

你之前的写法没有把初始值z融入折叠过程，只是想直接用foldr操作列表结构，还把累加器设成了undefined，自然没法注入初始值。foldr处理无限列表的关键是让每一步计算都能惰性生成列表元素，同时把初始值作为整个折叠过程的输入，而不是放在逻辑之外。

另外补充：虽然unfoldr是实现iterate更直观的工具（iterate f z = unfoldr (\x -> Just (x, f x)) z），但既然问题聚焦在fold系列，上面的foldr实现完全符合要求。

内容的提问来源于stack exchange，提问作者Enlico