在 scala 中使用 FoldRight 进行 FoldLeft

在经历的同时Scala 中的函数式编程 http://www.manning.com/bjarnason/，我遇到了这个问题：

你能用foldRight 来右转foldLeft 吗？另一种方式怎么样 大约？

在作者提供的解决方案中，他们提供了如下实现：

def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B = 
    foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)

  def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B = 
    foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)

有人可以帮我追踪这个解决方案，让我理解这实际上是如何根据foldr实现foldl的，反之亦然吗？

Thanks

我们来看看

def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B = 
  foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)

（另一个折叠类似）。诀窍在于，在正确的折叠操作期间，我们不会构建类型的最终值B。相反，我们构建一个函数B to B。折叠步骤采用 type 的值a: A和一个函数g: B => B并产生一个新函数(b => g(f(b,a))): B => B。该函数可以表示为以下的组合g with f(_, a):

  l.foldRight(identity _)((a,g) => g compose (b => f(b,a)))(z);

我们可以这样看待这个过程： 对于每个元素a of l我们采取部分申请b => f(b,a)，这是一个函数B => B。然后我们compose https://en.wikipedia.org/wiki/Function_composition所有这些函数都以这样的方式进行：与最右边的元素（我们开始遍历）相对应的函数位于组合链的最左边。最后，我们将大组合函数应用到z。这会产生一系列操作，从最左边的元素（位于组合链的最右边）开始，到最右边的元素结束。

Update:作为一个例子，我们来看看这个定义如何在二元素列表上工作。首先，我们将函数重写为

def foldLeftViaFoldRight[A,B](l: List[A], z: B)
                             (f: (B,A) => B): B =
{
  def h(a: A, g: B => B): (B => B) =
    g compose ((x: B) => f(x,a));
  l.foldRight(identity[B] _)(h _)(z);
}

现在让我们计算一下当我们通过它时会发生什么List(1,2):

List(1,2).foldRight(identity[B] _)(h _)
  = // by the definition of the right fold
h(1, h(2, identity([B])))
  = // expand the inner `h`
h(1, identity[B] compose ((x: B) => f(x, 2)))
  =
h(1, ((x: B) => f(x, 2)))
  = // expand the other `h`
((x: B) => f(x, 2)) compose ((x: B) => f(x, 1))
  = // by the definition of function composition
(y: B) => f(f(y, 1), 2)

将此功能应用到z yields

f(f(z, 1), 2)

按要求。