FoldLeft Via FoldRight

怎么用FoldRight实现FoldLeft呢？两个函数的签名如下

def foldLeft[A,B]: (List[A], B) => ((B, A) => B) => B

def foldRight[A,B]: (List[A], B) => ((A, B) => B) => B

最简单的方式就是先把列表翻转，头变尾，然后对翻转后的列表直接使用foldRight就可以了。

def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B, A) => B): B =
  foldRight(reverse(l), z)((x, acc) => f(acc, x))

能不能直接对原列表使用foldRight呢？先来看一个例子：对于List(X1, X2, X3, X4)，分别使用二者的等效表达式为

foldLeft = f(f(f(f(z, X1), X2), X3), X4) // from left to right

foldRight = f(X1, f(X2, f(X3, f(X4, z)))) // from right to left

foldLeft从左向右计算，foldRight从右向左计算。要用foldRight实现与foldLeft一样的效果，那么就要把计算推迟，不能让计算从右边发生。

我们可以使用函数来使真正的计算从左往右进行。即给foldRight传入的z是一个函数，foldRight的计算结果也是一个函数，得到的这个函数接收真正的z，进而完成计算。

def foldLeftViaFoldRight2[A,B](l: List[A], z: B)(f: (B, A) => B): B = {
    val g: (A, (B => B)) => B => B =
      (a: A, acc: (B => B)) =>
        (b: B) => acc(f(b, a))

    val id: (B => B) = (b: B) => b

    val delay: (B => B) = foldRight(l, id)(g)

    delay(z)
  }

id函数返回传入的参数，仅仅是为了推迟计算。解释如下

l : [X1, X2, X3......Xn]

acc = id // init

acc = (b: B) => id(f(b, Xn+1))  // n + 1

acc = (b: B) =>
        ((b2 :B) => id(f(b2, Xn+1))) (f(b, Xn)) // pass f(b, Xn) to b2
    = (b: B) =>
        id(f(f(b, Xn), Xn+1)) // n

...............................

acc = (b: B) =>
        id(f(...f(f(f(f(b, X1), X2), X3), X4)..., Xn))

acc(z) = foldLeft(l, z)(f)