Rewrite foldl with foldr, explained

📣 本文修订于 2020 年 11 月 27 日。

问题

在《Real World Haskell》一书中，作者在 95 页中给出了一个神奇的实现：用 foldr 实现 foldl，并在下面附上了一段话。

Understanding foldl in terms of foldr

If you want to set yourself a solid challenge, try to follow our definition of foldl using foldr. Be warned: this is not trivial! You might want to have the following tools at hand: some headache pills and a glass of water, ghci (so that you can find out what the id function does), and a pencil and paper.

You will want to follow the same manual evaluation process as we just outlined to see what foldl and foldr were really doing. If you get stuck, you may find the task easier after reading “Partial Function Application and Currying” on page 100.

大意就是说：理解这个还是比较困难的，准备好笔和纸（以及头疼药）再来思考这个问题。作为爱思考的函数式编程爱好者我偏不信这个邪，本文就是在我苦苦思考后写出的一种容易理解的解释。

观察

如果你对 foldr 和 foldl 两个函数十分熟悉，知道它们是如何求值的，那就可以跳过这一节。

先来看看它们的定义：

foldr :: (b -> a -> a) -> a -> [b] -> a
foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs

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

为了搞清楚这两个函数究竟在做什么，我们分别在 folr 和 foldl 上应用函数 (+)、整数 0 和列表 [1, 2, 3, 4]。

  foldr (+) 0 [1, 2, 3, 4]
= 1 + (foldr (+) 0 [2, 3, 4])
= 1 + (2 + (foldr (+) 0 [3, 4]))
= 1 + (2 + (3 + (foldr (+) 0 [4])))
= 1 + (2 + (3 + (4 + (foldr (+) 0 []))))
= 1 + (2 + (3 + (4 + 0)))

  foldl (+)     0                     [1, 2, 3, 4]
= foldl (+)    (0 + 1)                [2, 3, 4]
= foldl (+)   ((0 + 1) + 2)           [3, 4]
= foldl (+)  (((0 + 1) + 2) + 3)      [4]
= foldl (+) ((((0 + 1) + 2) + 3) + 4) []
=			      ((((0 + 1) + 2) + 3) + 4)

仔细观察求值结果可以发现：foldr 把初始运算元 z 放在列表的最右边，每次取最右边的两个元素，应用二元函数 f 求出结果，并把结果放回最右边；而 foldl 做的事情恰好相反，它把初始运算元放在列表最左边，每次取最左边的两个元素，应用二元函数 f 求出结果，并把结果放回最左边。

你可能会问：两个表达式运算后的结果不是一样吗？这是因为我们用了 (+) 作为二元函数，而 (+) 满足交换律，如果选择一个没有交换律的二元函数，比如 (-) 那么结果就会大不相同了。

通过观察 foldl 和 foldr 的求值过程，我们可以发现，foldl 的运算顺序是一棵左偏树(leftist tree)，而 foldr 的运算顺序可以用一棵右偏树(rightist tree)表示，两个函数的差别主要在于运算顺序。所以用 foldr 重写 foldl，本质上就是要用 foldr 来模拟 foldl 的运算顺序。

函数和数据

在 Haskell 中，如果让你实现一个表示二维实数空间上的一个点，你会怎么表示？我们的第一想法就是去构造新的类型。

data Point = Point Float Float

point :: Float -> Float -> Point
point x y = Point x y

我们可以通过模式匹配(pattern matching)获得结构中的数据。

getX :: Point -> Float
getX (Point x _) = x

getY :: Point -> Float
getY (Point _ y) = y

在《计算机程序设计的构造和解释》的第二章里，作者介绍了数据抽象(data abstraction)的概念。作者演示了如何用函数去构造 cons、car 和 cdr 这三个基本函数。

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else (error "Argument not 0 or 1 -- CONS" m))))
  dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))

在这个例子里，cons 所返回的不是传统意义上的数据(data)，而是一个接受更多参数的函数。car 和 cdr 就是通过对这个函数进行进一步求值而得到所需的值的。

带着这个例子所给我们的启示，我们可以在不构造新类型的情况下定义一个点。

point :: Float -> Float -> Bool -> Float
point x y t = if t then x else y

getX :: (Bool -> Float) -> Float
getX pt = pt True

getY :: (Bool -> Float) -> Float
getY pt = pt False

你会发现，上面代码里的 point、getX 和 getY 的用法和最初的版本并没有什么差别。Bool -> Float 其实和 Point 无异，都是一个可以表示出两个坐标的类型。讲到这，你可能已经明白了这道题的做法。

构造

上一节的内容启发了我们，我们可以用 foldr 构造一个结构，再把这个结构按照 foldl 的方法展开并计算，就可以达到我们的目的了。

我们先对 foldr 进行拆分，把它分为两部分：构造右偏树(rightist tree)和对右偏树结构进行求值。我们定义出右偏树类型 FoldRight，它有两个类型构造器(type constructor)：

第一个是 Compute x y，其中 x 是列表中的元素，y 是嵌套的 FoldRight a，表示计算；
第二个是 Stop 表示已经到了尽头，不需要计算了。

data FoldRight a = Compute a (FoldRight a)
                 | Stop

我们可以轻松用 foldr 写出从数组中构建 FoldRight 的函数。

makeFold :: [a] -> FoldRight a
makeFold = foldr f Stop
    where f x y = Compute x y

有人可能会问，之所以没有把类型 b 写进去，是因为我们接下来要按照 foldl 的顺序执行计算，也就是 evalFold 函数。

evalFold :: (a -> b -> a) -> a -> FoldRight b -> a
evalFold f z Stop = z
evalFold f z (Compute x y) = evalFold f (f z x) y

evalFold 函数做的事其实很简单，就是把 FoldRight 结构按照 foldl 的顺序进行运算。有了这 makeFold 和 evalFold 我们就可以用 foldr 实现出 foldl。

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f z xs = evalFold f z (makeFold xs)

读者可能会问：虽然你实现出来了，但形式太复杂了，而且书中给出的答案并没有构造中间数据结构。别急，还记得上一节我们提到的可以用高阶函数来表示数据结构吗？我们可以重写 FoldRight 的定义，使之用起来一模一样，但本质上是个函数。

在开始之前，我们要调整一下 evalFold 函数的参数的顺序，把 FoldRight b 变成第一个参数。为了表达清楚，我干脆就把调整过后的函数写出来好了。

evalFold' :: FoldRight b -> (a -> b -> a) -> a -> a
evalFold' Stop f z = z
evalFold' (Compute x y) f z = evalFold' y f (f z x)

把 FoldRight b 调整到第一个后，evalFold' 函数其实是在对 FoldRight 的两种构造进行分情况讨论。如果我们用函数重写了 FoldRight 结构，那么其实可以把每种情况的构造和计算合并成一个函数。

第一步，重写 evalFold' Stop f z。我们可以直接抹掉 evalFold' 这个名字，把 Stop 改成小写。这样就得到了 stop 函数的定义。你可能会开始考虑类型，但这里不妨再等一下，等重写完后，我们再来看类型能不能说得通。

stop f z = z

第二步，重写 evalFold' (Compute x y) f z。同样，我们可以直接抹掉 evalFold 这个名字，把 Compute 改成小写，并去掉构造的括号，我们就得到了 compute 的定义。

compute x y f z = y $ f (f z x)

在检查类型前，我们发现 f 在整个过程中保持不变，不如把它当作类似全局变量的东西，所以我们可以直接从两个函数中删掉它。得到新版的 stop 和 compute 定义。

compute x y z = y (f z x)
stop z = z

这个定义就非常简洁了，stop 就是一个 id 函数，我们尝试写出它们的类型，发现完全可以跑得通。

compute :: b -> (a -> a) -> a -> a
stop :: a -> a

观察一下结构，其实 a -> a 就是用于代替 FoldRight 的类型。接下来，把我们新的实现带回到上面的实现中，经过下面的三步替换，就可以得到书中的版本了。

foldl'   f z xs = evalFold f z (makeFold xs) -- Step 1
foldl''  f z xs = evalFold' (makeFold xs) f z -- Step 2
foldl''' f z xs = foldr compute stop f z -- Step 3

作业

是不是很神奇？来尝试做一下下面的作业吧。

请尝试用类似的方法，用 foldl 实现 foldr。
完成 1 后，思考 foldl 和 foldr 之间的关联。