使用foldr编写foldl函数

Question

在《Real World Haskell》中，第4章关于函数式编程的内容：

使用foldr编写foldl：

将foldl用foldr实现：

-- file: ch04/Fold.hs
myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

上面的代码让我感到困惑，有人叫做dps用一个有意义的名称重写了它，使它变得更清晰:

myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)

有人，Jef G，提供了一个很好的例子，并逐步展示了底层机制：

myFoldl (+) 0 [1, 2, 3]
= (foldR step id [1, 2, 3]) 0
= (step 1 (step 2 (step 3 id))) 0
= (step 1 (step 2 (\a3 -> id ((+) a3 3)))) 0
= (step 1 (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2))) 0
= (\a1 -> (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (\a3 -> (+) a3 3) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (+) ((+) a2 2) 3) ((+) a1 1)) 0
= (\a1 -> (+) ((+) ((+) a1 1) 2) 3) 0
= (+) ((+) ((+) 0 1) 2) 3
= ((0 + 1) + 2) + 3

但我仍然无法完全理解，这里是我的问题：

1. id函数是用来做什么的？它的作用是什么？为什么我们需要在这里使用它？
2. 在上面的例子中，id函数是lambda函数中的累加器吗？
3. foldr的原型是foldr :: (a -> b -> b) -> b -> [a] -> b，第一个参数是一个需要两个参数的函数，但是myFoldl实现中的步骤函数使用了3个参数，我完全困惑了！

- ylzhang

---

对于真正的虐待狂者，“step = curry $ uncurry (&) <<< (flip f) *** (.)” - Weijun Zhou

Answer 1

需要说明一些问题！

id函数是用来干什么的？它的作用是什么？为什么我们需要在这里使用它？

id是恒等函数，id x = x，在使用函数组合的时候被用作零的等价物。你可以在Prelude中找到它的定义。

在上面的例子中，id函数是lambda函数中的累加器吗？

累加器是通过反复的函数应用而构建的函数。由于我们命名了累加器为step，所以没有显式地使用lambda表达式。如果你愿意，也可以使用lambda表达式来写：

foldl f a bs = foldr (\b g x -> g (f x b)) id bs a

或者，如Graham Hutton所述：

5.1 foldl操作符

现在让我们从suml的例子中推广，并考虑使用函数f组合值和一个值v作为起始值来从左到右处理列表元素的标准操作符foldl：

foldl :: (β → α → β) → β → ([α] → β)
foldl f v [ ] = v
foldl f v (x : xs) = foldl f (f v x) xs

使用这个操作符，suml可以通过 suml = foldl (+) 0 简单地重新定义。许多其他的函数也可以使用 foldl 以简单的方式被定义。例如，标准函数 reverse 可以通过以下方式使用 foldl 被重新定义:

reverse :: [α] → [α]
reverse = foldl (λxs x → x : xs) [ ]

使用这个定义要比我们原来使用fold的定义更高效，因为它避免了对于列表使用低效的追加操作符(++)。

前一节中针对函数suml的计算的简单泛化展示了如何基于fold重新定义函数foldl：

foldl f v xs = fold (λx g → (λa → g (f a x))) id xs v

相比之下，无法通过foldl来重新定义fold，因为foldl在其列表参数的尾部处是严格的，但fold不是。关于fold和foldl有许多有用的“对偶定理”，还有一些指导方针，可以帮助我们决定哪个操作符最适合特定的应用程序（Bird，1998年）。 foldr的原型是foldr :: (a -> b -> b) -> b -> [a] -> b 一个Haskell程序员会说，foldr的类型是(a -> b -> b) -> b -> [a] -> b。

第一个参数是一个需要两个参数的函数，但是myFoldl的实现中的步骤函数使用了3个参数，这让我完全困惑了。

这很令人困惑和神奇！我们玩一个把累加器替换为一个函数的技巧，这个函数又被应用于初始值以产生结果。

Graham Hutton在上面的文章中解释了将foldl转换为foldr的技巧。我们首先写出foldl的递归定义：

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v []       = v
foldl f v (x : xs) = foldl f (f v x) xs

然后通过对f进行静态参数转换来重构它：

foldl :: (a -> b -> a) -> a -> [b] -> a    
foldl f v xs = g xs v
    where
        g []     v = v
        g (x:xs) v = g xs (f v x)

现在让我们改写g函数，以便将v向内浮动：

foldl f v xs = g xs v
    where
        g []     = \v -> v
        g (x:xs) = \v -> g xs (f v x)

这相当于将g看作是一个接受一个参数并返回函数的函数：

foldl f v xs = g xs v
    where
        g []     = id
        g (x:xs) = \v -> g xs (f v x)

现在我们有一个函数g，它递归地遍历一个列表并应用某个函数f。最终的值是恒等函数，并且每一步也会产生一个函数。

但是，我们已经有了一个非常类似的递归函数foldr来处理列表！

2 折叠操作符

fold操作符起源于递归理论（Kleene, 1952），而将fold用作编程语言中的核心概念可以追溯到APL的缩减运算符（Iverson，1962）和FP的插入运算符（Backus，1978）。 在Haskell中，可以将列表的fold操作符定义如下：

fold :: (α → β → β) → β → ([α] → β)
fold f v [ ] = v
fold f v (x : xs) = f x (fold f v xs)

给定类型为 α → β → β 的函数 f 和类型为 β 的值 v，函数 fold f v 处理类型为 [α] 的列表，通过将列表末尾的空构造函数 [] 替换为值 v，并将列表中的每个 cons 构造函数 (:) 替换为函数 f，从而得到类型为 β 的结果值。换言之，fold 运算符封装了一种简单的递归模式，用于处理列表，在该模式中，列表的两个构造函数仅被其他值和函数所替换。许多熟悉的列表函数都可以使用 fold 简单地定义。

这看起来与我们的 g 函数非常相似的递归方案。现在的诀窍是：利用手头上所有可用的魔法（即 Bird、Meertens 和 Malcolm），应用一个特殊规则，即 fold 的通用规则，它是一个等价于两个对于处理列表的函数 g 的定义的规则，如下：

g [] = v
g (x:xs) = f x (g xs)

当且仅当

g = fold f v

因此，折叠的普适性原理陈述如下：

    g = foldr k v

其中g必须等于以下两个方程式，对于某些k和v：

    g []     = v
    g (x:xs) = k x (g xs)

从我们之前的foldl设计中，我们知道v == id。不过对于第二个等式，我们需要计算出k的定义：

    g (x:xs)         = k x (g xs)        
<=> g (x:xs) v       = k x (g xs) v      -- accumulator of functions
<=> g xs (f v x)     = k x (g xs) v      -- definition of foldl
<=  g' (f v x)       = k x g' v          -- generalize (g xs) to g'
<=> k = \x g' -> (\a -> g' (f v x))      -- expand k. recursion captured in g'

将我们计算出的k和v的定义代入，得到foldl的定义：

foldl :: (a -> b -> a) -> a -> [b] -> a    
foldl f v xs =
    foldr
        (\x g -> (\a -> g (f v x)))
        id
        xs
        v

使用foldr组合器替代递归的g函数，并且在列表中的每个元素处以相反顺序构建一个由f函数链式组成的函数作为累加器（所以我们向左折叠而不是向右）。

要深入理解这个转换，我推荐Hutton教程中的“fold的普遍性”部分，该教程下面有链接。

---

参考资料

• Haskell Wiki: Foldl as foldr
• A tutorial on the universality and expressiveness of fold，Graham Hutton，J. Functional Programming 9(4)：355-372，1999年7月。
• Malcolm，G.代数数据类型和程序转换。博士论文，格罗宁根大学。

- Don Stewart

---

请修复 k = \x g' -> (\a -> g' (f v x)) 和 (\x g -> (\a -> g (f v x))) 中的拼写错误。 - Kamel

最终的函数似乎有问题，但我不太理解它，无法完全确定。我认为 (\x g -> (\a -> g (f v x))) 应该被替换为 (\x g -> (\a -> g (f a x)))。 - jeanggi90

Answer 2

考虑一下 foldr 的类型：

foldr :: (b -> a -> a) -> a -> [b] -> a

step 的类型类似于 b -> (a -> a) -> a -> a。由于 step 被传递给了 foldr，因此我们可以得出结论，在这种情况下，fold 的类型类似于 (b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a)。

不要被不同签名中的 a 的不同含义所迷惑；它只是一个类型变量。此外，请记住函数箭头是右结合的，因此 a -> b -> c 和 a -> (b -> c) 是相同的东西。

是的，foldr 的累加器值是类型为 a -> a 的函数，初始值为 id。这有一些道理，因为 id 是一个什么也不做的函数--这就是你在对列表中的所有值进行求和时从零开始的原因。

至于 step 取三个参数，尝试将其重写为：

step :: b -> (a -> a) -> (a -> a)
step x g = \a -> g (f a x)

那么这样做是否更容易看出发生了什么？它需要一个额外的参数，因为它正在返回一个函数，而两种写法是等价的。还要注意在foldr之后的额外参数：(foldr step id xs) z。括号中的部分是折叠本身，它返回一个函数，然后应用于z。

- C. A. McCann

Answer 3

这是我的证明，表明foldl可以用foldr表示，除了step函数引入的名称混乱之外，我认为它非常简单明了。

命题是foldl f z xs等价于：

myfoldl f z xs = foldr step_f id xs z
        where step_f x g a = g (f a x)

这里需要注意的第一件重要的事情是，第一行右侧实际上被评估为

(foldr step_f id xs) z

由于foldr只接受三个参数。这已经暗示了foldr将计算的不是一个值，而是一个柯里化函数，然后应用于z。有两种情况需要调查以找出myfoldl是否为foldl：

1. Base case: empty list

     myfoldl f z []
   = foldr step_f id [] z    (by definition of myfoldl)
   = id z                    (by definition of foldr)
   = z
   
     foldl f z []
   = z                       (by definition of foldl)
   

2. Non-empty list

     myfoldl f z (x:xs)
   = foldr step_f id (x:xs) z          (by definition of myfoldl)
   = step_f x (foldr step_f id xs) z   (-> apply step_f)
   = (foldr step_f id xs) (f z x)      (-> remove parentheses)
   = foldr step_f id xs (f z x)
   = myfoldl f (f z x) xs              (definition of myfoldl)
   
     foldl f z (x:xs)
   = foldl f (f z x) xs
   

由于在第2步中，无论哪种情况下，第一行和最后一行的形式都相同，因此可以使用它将列表折叠到xs == []，在这种情况下，1.保证了相同的结果。因此，通过归纳，myfoldl == foldl。

- David

Answer 4

^{快速浏览我的答案[1], [2], [3], [4]以确保你理解Haskell的语法、高阶函数、柯里化、函数组合、$运算符、中缀/前缀运算符、部分应用和lambda表达式。}

fold的通用性质

fold只是某些递归形式的编码。通用性质简单地说明，如果你的递归符合某种形式，它可以按照一些正式的规则转换为fold。反过来，每个fold都可以转换为那种递归。同样地，有些递归可以被转换为完全相同的fold，而有些递归则不能，但是有一个精确的过程可以做到这一点。

基本上，如果你的递归函数在列表上运行，并且看起来像 左侧，那么你可以将其转换为折叠一个 右侧，用实际存在的 f 和 v 替换它们。

g []     = v              ⇒
g (x:xs) = f x (g xs)     ⇒     g = foldr f v

例如：

sum []     = 0   {- recursion becomes fold -}
sum (x:xs) = x + sum xs   ⇒     sum = foldr 0 (+)

这里v = 0和sum (x:xs) = x + sum xs等价于sum (x:xs) = (+) x (sum xs)，因此f = (+)。另外还有两个例子。

product []     = 1
product (x:xs) = x * product xs  ⇒  product = foldr 1 (*)

length []     = 0
length (x:xs) = 1 + length xs    ⇒  length = foldr (\_ a -> 1 + a) 0

练习:

1. 递归实现 map, filter, reverse, concat 和 concatMap，就像左侧的函数一样。

2. 根据上面的公式将这5个函数转换为 foldr，即在右侧的 fold 公式中替换 f 和 v。

通过 foldr 实现 foldl

如何编写一个从左到右递归求和的函数？

sum [] = 0     -- given `sum [1,2,3]` expands into `(1 + (2 + 3))`
sum (x:xs) = x + sum xs

第一个递归函数在开始加法之前就已经完全展开了，这不是我们需要的。一种方法是创建一个具有累加器的递归函数，在每个步骤上立即添加数字（阅读尾递归以了解更多递归策略）。

suml :: [a] -> a
suml xs = suml' xs 0
  where suml' [] n = n   -- auxiliary function
        suml' (x:xs) n = suml' xs (n+x)

好的，请在GHCi中运行此代码，并确保您理解其工作原理，然后仔细地、深思熟虑地继续。 suml 无法使用折叠重新定义，但是可以使用 suml'。

suml' []       = v    -- equivalent: v n = n
suml' (x:xs) n = f x (suml' xs) n

suml' [] n = n 是从函数定义得出的，对吗？而 v = suml' [] 是根据通用属性公式得出的。两者结合得到了一个函数 v n = n，它会立即返回接收到的内容： v = id。现在让我们计算 f：

suml' (x:xs) n = f x (suml' xs) n
-- expand suml' definition
suml' xs (n+x) = f x (suml' xs) n
-- replace `suml' xs` with `g`
g (n+x)        = f x g n

因此，suml' = foldr (\x g n -> g (n+x)) id，因此，suml = foldr (\x g n -> g (n+x)) id xs 0。

foldr (\x g n -> g (n + x)) id [1..10] 0 -- return 55

现在我们只需要进行概括，将+替换为一个变量函数：

foldl f a xs = foldr (\x g n -> g (n `f` x)) id xs a
foldl (-) 10 [1..5] -- returns -5

结论

现在阅读Graham Hutton的“fold”的普适性和表达能力教程。拿出笔和纸，尝试理解他写的每个内容，直到你自己能够推导出大多数的折叠函数。如果你不理解某些东西，不要着急，你可以随时回来看，但是也不要太拖延。

- Mirzhan Irkegulov

---

我觉得这个答案比被接受的那个更简单明了。可惜它的赞数太少了... - gigabytes

Answer 5

没有通向数学的皇家大道，甚至没有通过Haskell。让我们看看一些基本的数学概念，以便更好地理解IT技术。

h z = (foldr step id xs) z where   
     step x g =  \a -> g (f a x)

什么是

h z

？假设xs = [x0, x1, x2]。

应用foldr的定义：

h z = (step x0 (step x1 (step x2 id))) z 

应用步骤的定义：

= (\a0 -> (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (f a0 x0)) z

将内容替换为lambda函数：

= (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (f z x0)

= (\a2 -> id (f a2 x2)) (f (f z x0) x1)

= id (f (f (f z x0) x1) x2)

应用 ID 的定义：

= f (f (f z x0) x1) x2

应用foldl的定义：

= foldl f z [x0, x1, x2]

这是皇家之路吗？

- disznoperzselo

Answer 6

我发布这篇答案是为了那些可能认为这种方法更适合他们思维方式的人。答案可能包含冗余的信息和想法，但这是我解决问题所需要的。此外，由于这是对同一个问题的另一个答案，它显然与其他答案有很大的重叠，但它讲述了我如何理解这个概念的故事。

事实上，当我试图理解这个主题时，我开始写下这些笔记作为我的思考记录。如果我真的理解了它，那么我花了一整天才接触到它的核心。

我理解这个简单练习的漫长过程

容易部分：我们需要确定什么？

以下示例调用会发生什么情况

foldl f z [1,2,3,4]

可以通过以下图表进行可视化（该图表位于维基百科上，但我最初是在另一个答案中看到的）：

          _____results in a number
         /
        f          f (f (f (f z 1) 2) 3) 4
       / \
      f   4        f (f (f z 1) 2) 3
     / \
    f   3          f (f z 1) 2
   / \
  f   2            f z 1
 / \
z   1

作为一个侧面说明，当使用 foldl 时，每个 f 的应用程序都不会被执行，并且表达式被惰性求值，就像我上面写的那样；原则上，它们可以从底部到顶部计算，这正是 foldl' 所做的。

本练习实质上挑战我们通过适当改变步骤函数（因此我们使用 s 而不是 f）和初始累加器（因此我们使用 ? 而不是 z）来使用 foldr 替换 foldl；否则列表保持不变，否则我们在谈论什么？

调用 foldr 必须如下所示：

foldr s ? [1,2,3,4]

"相应的图表如下："

    _____what does the last call return?
   /
  s
 / \
1   s
   / \
  2   s
     / \
    3   s
       / \
      4   ? <--- what is the initial accumulator?

电话通话的结果是

s 1 (s 2 (s 3 (s 4 ?)))

“s”和“？”是什么？它们的类型是什么？看起来，“s”是一个带有两个参数的函数，与“f”非常相似，但让我们不要过早下结论。此外，让我们暂时搁置“？”这个符号，观察当“1”出现时，“z”必须立即参与进来；然而，在调用可能具有两个参数的“s”函数（即调用“s 1（...）”）中，如何让“z”参与进来呢？我们可以通过选择一个需要三个参数的“s”来解决这个谜题的一部分，而不是我们之前提到的那两个参数，这样最外层的调用“s 1（...）”将产生一个带有一个参数的函数，我们可以将“z”传递给它！

这意味着我们想要原始调用，扩展为：

f (f (f (f z 1) 2) 3) 4

等同于

s 1 (s 2 (s 3 (s 4 ?))) z

或者说，换句话说，我们想要部分应用的函数。

s 1 (s 2 (s 3 (s 4 ?)))

等价于以下的 lambda 函数

(\z -> f (f (f (f z 1) 2) 3) 4)

再次强调，我们所需的“唯一”部分是s和?。

转折点：认识函数组合

让我们重新绘制之前的图表，并在右侧写下我们希望每个对s的调用等价于什么：

  s          s 1 (…) == (\z -> f (f (f (f z 1) 2) 3) 4)
 / \
1   s        s 2 (…) == (\z -> f (f (f    z    2) 3) 4)
   / \
  2   s      s 3 (…) == (\z -> f (f       z       3) 4)
     / \
    3   s    s 4  ?  == (\z -> f          z          4)
       / \
      4   ? <--- what is the initial accumulator?

希望从图表的结构清楚地看出，每行中的 (...) 是下面一行的右侧；更好的说法是它是上一个（下面的）对 s 的调用返回的函数。

应该也清楚，使用参数 x 和 y 对 s 进行调用是将 f 的部分应用于唯一的参数 x（作为其第二个参数）的 y 的（完整）应用。由于对 x 的 f 的部分应用可以写成 lambda (\z -> f z x)，所以完全将 y 应用于它会得到 lambda (\z -> y (f z x))，在这种情况下我会将其重写为 y . (\z -> f z x)；将这些话翻译成 s 的表达式，我们得到：

s x y = y . (\z -> f z x)

这段话的翻译如下：

（这与 s x y z = y (f z x) 相同，如果您重命名变量，则与书中相同。）

最后一部分是：累加器的初始“值”是什么？上述图可以通过展开嵌套调用来重写，使它们成为组合链。

  s          s 1 (…) == (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) . (\z -> f z 1)
 / \
1   s        s 2 (…) == (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2)
   / \
  2   s      s 3 (…) == (\z -> f z 4) . (\z -> f z 3)
     / \
    3   s    s 4  ?  == (\z -> f z 4)
       / \
      4   ? <--- what is the initial accumulator?

我们在这里看到，s 简单地“堆积”了连续的 f 的部分应用，但在 s x y = y . (\z -> f z x) 中的 y 表明解释 s 4 ?（以及所有其他函数）时错过了一个要与最左边的 lambda 组合的前导函数。

那就是我们的 ? 函数：现在是给它一个存在的理由的时候了，除了占据调用 foldr 中的一个位置，我们可以选择什么来保持结果函数不变呢？答案是 id，恒等函数，它也是组合运算符 (.) 的恒等元素。

  s          s 1 (…) == id . (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) . (\z -> f z 1)
 / \
1   s        s 2 (…) == id . (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2)
   / \
  2   s      s 3 (…) == id . (\z -> f z 4) . (\z -> f z 3)
     / \
    3   s    s 4 id  == id . (\z -> f z 4)
       / \
      4   id

所寻找的函数是：

myFoldl f z xs = foldr (\x g a -> g (f a x)) id xs z

- Enlico

Answer 7

我知道这个问题很旧了，但我想加入一个不同的角度，我认为这对其他人也有帮助。

从一个小例子开始，关键的洞察力在于注意到foldr和foldl作用于短列表时可以分别重写为

foldr f z [a, b, c]
    == a `f` (b `f` (c `f` z))
    == (a `f`) . (b `f`) . (c `f`) $ z
    == (f a) . (f b) . (f c) $ z

并且

foldl f z [a, b, c]
    == ((z `f` a) `f` b) `f` c
    == (`f` c) . (`f` b) . (`f` a) $ z
    == ((flip f) c) . ((flip f) b) . ((flip f) a) $ z

请注意，主要区别在于f被翻转，组合顺序相反。

我们通常认为折叠是以某种方式“处理列表”; 我提倡的变化是，我们将它们视为由列表参数化的函数组合构建。

让我们从一个明显的离题开始。

简单组合

如果我们有一个函数列表a -> a，我们可以将它们全部组合在一起，并获得一个新的函数a -> a。 在foldr方面，实现非常简单：

compose :: [a -> a] -> (a -> a)
compose = foldr (.) id

如果我们想要以相反的顺序组合它们，当然可以链接compose . reverse，但是另一种方法是通过翻转(.)来直接使用foldr定义操作：

composeRev :: [a -> a] -> (a -> a)
composeRev = foldr (flip (.)) id

参数化组合

现在假设我们不是拥有一个函数列表[a -> a]，而是拥有一个列表[b]和一个函数b -> (a -> a)，对于列表中的每个项目，它都会产生如上所述的函数a -> a。我们可以将列表中的每个项目映射到其相应的函数，然后组合生成的函数列表：

compMap :: (b -> (a -> a)) -> [b] -> (a -> a)
compMap f = compose . map f

同样，这可以直接使用foldr实现：

compMap f = foldr (\x chain -> f x . chain) id
          = foldr ((.) . f) id

同样的，要进行反向组合，我们可以采用以下方法之一

compMapRev :: (b -> (a -> a)) -> [b] -> (a -> a)
compMapRev f = composeRev . map f
             = compose . map f . reverse
             = compMap f . reverse

或者用foldr重新编写它：

compMapRev f = foldr (\x chain -> chain . f x) id
             = foldr ((flip (.)) . f) id

回到折叠

回顾我们最初的小例子，我们可能会感觉到foldr/foldl和compMap/compMapRev之间存在强烈的关系。

如果我们对齐它们的类型签名，foldr和compMap之间的相似之处变得更加明显：

foldr   :: (b -> (a -> a)) ->  a  -> [b] -> a
compMap :: (b -> (a -> a)) -> [b] ->  a  -> a

我们立即意识到，foldr和compMap只是它们的第二个和第三个参数翻转了，即foldr f == flip (compMap f)，即foldr == flip . compMap。

让我们看看是否可以用类似的方法来处理foldl。这次我们必须记得将其与compMapRev进行比较，因为组合顺序必须相同：

foldl      :: (a ->  b -> a)  ->  a  -> [b] -> a
compMapRev :: (b -> (a -> a)) -> [b] ->  a  -> a

除了交换第二个和第三个参数之外，这次还翻转了第一个函数参数，即 foldl f == flip (compMapRev (flip f))，即 foldl == flip . compMapRev . flip。

前面的观察表明以下等式成立：

foldr f z list =  compMap f list z
               == foldr ((.) . f) id list z -- does not work as a recursive definition

foldl f z list = compMapRev (flip f) list z
               = foldr ((flip (.)) . (flip f)) id list z

这最后一个正是我们一直在寻找的。

我们还可以简化和对齐这两个身份以突出相似之处：

foldr f == flip $ foldr (      (.)  .       f ) id -- does not work as a definition
foldl f =  flip $ foldr ((flip (.)) . (flip f)) id

- Federico

Answer 8

foldr step zero (x:xs) = step x (foldr step zero xs)
foldr _ zero []        = zero

myFold f z xs = foldr step id xs z
  where step x g a = g (f a x)

myFold (+) 0 [1, 2, 3] =
  foldr step id [1, 2, 3] 0
  -- Expanding foldr function
  step 1 (foldr step id [2, 3]) 0
  step 1 (step 2 (foldr step id [3])) 0
  step 1 (step 2 (step 3 (foldr step id []))) 0
  -- Expanding step function if it is possible
  step 1 (step 2 (step 3 id)) 0
  step 2 (step 3 id) (0 + 1)
  step 3 id ((0 + 1) + 2)
  id (((0 + 1) + 2) + 3)

好的，至少这对我有帮助，即使它并不完全正确。

- hanrai

Answer 9

这可能会有帮助，我尝试用另一种方式来扩展。

myFoldl (+) 0 [1,2,3] = 
foldr step id [1,2,3] 0 = 
foldr step (\a -> id (a+3)) [1,2] 0 = 
foldr step (\b -> (\a -> id (a+3)) (b+2)) [1] 0 = 
foldr step (\b -> id ((b+2)+3)) [1] 0 = 
foldr step (\c -> (\b -> id ((b+2)+3)) (c+1)) [] 0 = 
foldr step (\c -> id (((c+1)+2)+3)) [] 0 = 
(\c -> id (((c+1)+2)+3)) 0 = ...

- Dulguun Otgon

Answer 10

以下定义经过三个简单步骤，便容易理解。

-- file: ch04/Fold.hs
myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

步骤1. 将函数评估的折叠转换为函数组合

foldl f z [x1 .. xn] = z & f1 & .. & fn = fn . .. . f1 z。其中fi = \z -> f z xi。

(使用z & f1 & f2 & .. & fn表示fn ( .. (f2 (f1 z)) .. )。)

步骤2. 以foldr方式表达函数组合

foldr (.) id [f1 .. fn] = (.) f1 (foldr (.) id [f2 .. fn]) = f1 . (foldr (.) id [f2 .. fn])。展开其余部分，得到foldr (.) id [f1 .. fn] = f1 . .. . fn。

注意到序列是反转的，我们应该使用反转形式的(.)。定义rc f1 f2 = (.) f2 f1 = f2 . f1，然后foldr rc id [f1 .. fn] = rc f1 (foldr (.) id [f2 .. fn]) = (foldr (.) id [f2 .. fn]) . f1。展开其余部分以获得foldr rc id [f1 .. fn] = fn . .. . f1。

第三步。将函数列表上的折叠转换为操作数列表上的折叠

找到使foldr step id [x1 .. xn] = foldr rc id [f1 .. fn]的step。很容易找到step = \x g z -> g (f z x)。

通过3个步骤，使用foldr定义foldl就很清晰了：

  foldl f z xs
= fn . .. . f1 z
= foldr rc id fs z
= foldr step id xs z

证明正确性：

foldl f z xs = foldr (\x g z -> g (f z x)) id xs z
             = step x1 (foldr step id [x2 .. xn]) z
             = s1 (foldr step id [x2 .. xn]) z
             = s1 (step x2 (foldr step id [x3 .. xn])) z
             = s1 (s2 (foldr step id [x3 .. xn])) z
             = ..
             = s1 (s2 (.. (sn (foldr step id [])) .. )) z
             = s1 (s2 (.. (sn id) .. )) z
             = (s2 (.. (sn id) .. )) (f z x1)
             = s2 (s3 (.. (sn id) .. )) (f z x1)
             = (s3 (.. (sn id) .. )) (f (f z x1) x2)
             = ..
             = sn id (f (.. (f (f z x1) x2) .. ) xn-1)
             = id (f (.. (f (f z x1) x2) .. ) xn)
             = f (.. (f (f z x1) x2) .. ) xn

in which xs = [x1 .. xn], si = step xi = \g z -> g (f z xi)

如果您发现有任何不清楚的地方，请添加评论。:)

- qimokao