iterate可以用fold写吗？

Question

前言

我正在尝试将函数

f

反复应用于给定参数

z

的想法，一遍又一遍，从而得到一个无限列表。

基本上我想要列表

[z, f z, f (f z), f (f (f z)), ...]

，我可以将其提供给

take n

，

takeWhile whatever

，或其他东西。

最初我认为由于我要处理的列表是无限的（我在想

repeat f

），我应该使用

foldr

，但实际上这是不可能的，因为当

foldr

ing一个无限列表时累加器通常设置为

undefined

因为使用过，所以在像

foldr (\f (x:xs) -> f x:x:xs) undefined (repeat f)

这样的情况下我不会放

z

.

问题

所以我开始写这个问题，多亏了我发现

iterate

的建议，它的实现是，

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

所以我的问题变了：是否可以将

iterate

写成折叠？如果是这样，如何？如果不是，为什么？

Answer 1

不，或者至少不是以任何惯用的方式。但那是因为

foldr

是错误的工作工具。

foldr

是折叠，或 catamorphism。这是一种奇特的数学表达方式，它采用聚合数据（在本例中为列表）并产生单个结果（标量，例如数字）。这就是为什么像

sum

这样的操作可以直接用

foldr

来写，因为

sum

从根本上采用聚合数据并产生单一结果。

你想要的是一个变形，或者一种获取单点数据的方法（在你的例子中是

z

）并从中产生聚合数据。在 Haskell 中，这被恰当地命名为

unfoldr

。

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 

unfoldr

以 ab 初始值

b

开始并调用它给定的函数。每次它调用该函数时，如果它产生一个

Just (a, b')

，那么我们使用

a

作为列表的第一个元素并继续以

b'

作为状态值。如果函数返回

Nothing

，那么我们就停止迭代。

在您的情况下，您想生成一个无限列表，因此我们将始终返回一个

Just

值。你可以用

iterate

来写

unfoldr

，如下所示。

import Data.List(unfoldr)

iterate' :: (a -> a) -> a -> [a]
iterate' f = unfoldr (\z -> Just (z, f z))

Answer 2

对我来说，按照你的建议使用

repeat f

相当于“作弊”，因为你在那个无限列表中隐藏了一个无限递归。正如 Silvio Mayolo 已经解释的那样，正确的方法是使用变形 (

unfoldr

)。

也就是说，如果允许的话，我们可以将

iterate

实现为折叠。这是我们在 GHCi 中获得

iterate ('b':) "X"

的示例：

> take 9 $ foldr (\ x xs k -> k : xs (x k) ) (\_ -> []) (repeat ('b':)) "X"
["X","bX","bbX","bbbX","bbbbX","bbbbbX","bbbbbbX","bbbbbbbX","bbbbbbbbX"]

这使用了（不）著名的技巧“用四个参数调用

foldr

”。我们的想法是让折叠返回一个函数，我们最终用

iterate

的初始值提供给它，即

"X"

。这允许我们在每个“递归调用”中修改第四个参数：当我们写

xs (x k)

时，我们实际上是在调用

xs

，由列表其余部分的折叠计算的函数，

x k

实际上是

 'b':k

，有效地传递迭代列表中的下一个值。

---

我不喜欢这种方法的原因之一是我们甚至不需要

repeat f

。事实上，

repeat ()

就足以推动折叠。

> take 9 $ foldr (\ _ xs k -> k : xs ('b':k) ) (\_ -> []) (repeat ()) "X"
["X","bX","bbX","bbbX","bbbbX","bbbbbX","bbbbbbX","bbbbbbbX","bbbbbbbbX"]

更糟糕的是：如果我们可以访问

repeat ()

我们可以写出一个定点组合器（对于函数类型）：

> myFix f = foldr (\ _ xs -> f . xs) id (repeat ()) id
> :t myFix
myFix :: ((a -> a) -> a -> a) -> a -> a

这是使用定点运算符计算的阶乘：

> myFix (\g n -> if n==0 then 1 else n * g (n-1)) 5
120