scala - 在 Scala 中使用 FoldRight 的 FoldLeft

Question

在经过时Functional Programming in Scala ，我遇到了这个问题:

Can you right foldLeft in terms of foldRight? How about the other way around?

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

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 的，反之亦然？

谢谢

Answer 1

让我们来看看

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 构建了一个函数至 B .折叠步骤采用 a: A 类型的值和一个函数 g: B => B并产生一个新函数 (b => g(f(b,a))): B => B .该函数可以表示为 g 的组合与 f(_, a) :

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

我们可以这样查看流程:对于每个元素 a的 l我们采取部分申请 b => f(b,a) ，这是一个函数 B => B .然后，我们 compose所有这些函数都以这样一种方式，即对应于最右侧元素(我们开始遍历的元素)的函数位于组合链的最左侧。最后，我们在 z 上应用大组合函数.这导致一系列操作，从最左边的元素(在组合链中最右边)开始，并以最右边的元素结束。

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

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产量

f(f(z, 1), 2)

按要求。