在 Scala 中进行函数式编程时，我遇到了这个问题：
你能用 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)
有人可以帮我追踪这个解决方案并让我了解这实际上是如何实现 foldl 的，反之亦然？
谢谢
让我们来看看
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)
（另一折类似）。诀窍在于，在正确的折叠操作期间，我们不会构建 type 的最终值B。B相反，我们从to构建一个函数B。fold 步骤接受一个类型的值a: A和一个函数g: B => B并产生一个新的函数(b => g(f(b,a))): B => B。该函数可以表示为gwith的组合f(_, a)：
l.foldRight(identity _)((a,g) => g compose (b => f(b,a)))(z);
我们可以这样看这个过程：对于每一个元素a我们l取偏应用b => f(b,a)，也就是一个函数B => B。然后，我们组合所有这些函数，使得对应于最右边元素（我们开始遍历）的函数在组合链的最左边。最后，我们在 上应用大组合函数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)
按要求。
我刚刚做了这个练习，并想分享我是如何得出答案的（与问题中的内容基本相同，只是字母不同），希望它对某人有用。
作为背景，让我们从做什么foldLeft和foldRight做什么开始。例如，对列表 [1, 2, 3] 进行 foldLeft 的结果与操作*和起始值z为该值
((z * 1) * 2) * 3
我们可以将 foldLeft 视为从左到右递增地使用列表的值。换句话说，我们最初从值开始z（如果列表为空，结果将是什么），然后我们揭示foldLeft我们的列表从 1 开始并且值变为z * 1，然后foldLeft看到我们的列表下一个具有2并且值变为(z * 1) * 2，最后，作用于 3 后，变为值((z * 1) * 2) * 3。
1 2 3
Initially: z
After consuming 1: (z * 1)
After consuming 2: ((z * 1) * 2
After consuming 3: (((z * 1) * 2) * 3
这个最终值是我们想要达到的值，除非（如练习要求我们）使用foldRight代替。现在请注意，就像foldLeft从左到右使用列表的foldRight值一样，从右到左使用列表的值。所以在列表 [1, 2, 3] 上，
(((z * 1) * 2) * 3换句话说：使用foldRight，我们首先得到如果列表为空的结果是什么，然后是列表只包含 [3] 的结果，然后是列表为 [2, 3] 的结果，最后是结果列表为 [1, 2, 3]。
也就是说，这些是我们想要达到的值，使用foldRight：
1 2 3
Initially: z
After consuming 3: z * 3
After consuming 2: (z * 2) * 3
After consuming 1: ((z * 1) * 2) * 3
所以我们需要从zto(z * 3)到(z * 2) * 3to ((z * 1) * 2) * 3。
作为values，我们不能这样做：对于任意操作，从 value(z * 3)到 value没有自然的方式。（有乘法，因为它是可交换的和关联的，但我们只是用来代表任意操作。）(z * 2) * 3**
但作为函数，我们也许可以做到这一点！我们需要有一个带有“占位符”或“洞”的功能：可以z把它放在适当的位置。
z => (z * 3)。或者更确切地说，作为一个函数必须采用任意值并且我们一直在使用z一个特定的值，让我们把它写成t => (t * 3). （应用于输入的这个函数z给出了值(z * 3)。）t => (t * 2) * 3？我们可以从第一个占位符函数转到下一个吗？让
f1(t) = t * 3
and f2(t) = (t * 2) * 3
f2是什么f1？
f2(t) = f1(t * 2)
我们可以！所以我们想要的函数接受2和f1给出f2。让我们称之为g. 我们有g(2, f1) = f2哪里f2(t) = f1(t * 2)或换句话说
g(2, f1) =
t => f1(t * 2)
让我们看看如果我们继续这样做是否可行：下一步将是g(1, f2) = (t => f2(t * 1))RHS 与t => f1((t * 1) * 2))or相同t => (((t * 1) * 2) * 3)。
看起来它有效！最后我们应用z到这个结果。
第一步应该是什么？我们应用gon3和f0to get f1，其中f1(t) = t * 3定义如上，也f1(t) = f0(t * 3)来自定义g。所以看起来我们需要f0成为身份函数。
让我们重新开始。
Our foldLeft(List(1, 2, 3), z)(*) is ((z * 1) * 2) * 3
Types here: List(1, 2, 3) is type List[A]
z is of type B
* is of type (B, A) -> B
Result is of type B
We want to express that in terms of foldRight
As above:
f0 = identity. f0(t) = t.
f1 = g(3, f0). So f1(t) = f0(t * 3) = t * 3
f2 = g(2, f1). So f2(t) = f1(t * 2) = (t * 2) * 3
f3 = g(1, f2). So f3(t) = f2(t * 1) = ((t * 1) * 2) * 3
最后我们在 z 上应用 f3 并得到我们想要的表达式。一切正常。所以
f3 = g(1, g(2, g(3, f0)))
这意味着 f3 =foldRight(xs, f0)(g)
让我们定义g，这次不是x * y使用任意函数s(x, y)：
g是类型Ag是 these 的类型f，即B => Bg是(A, (B=>B)) => (B=>B)也是这样g：
def g(a: A, f: B=>B): B=>B =
(t: B) => f(s(t, a))
把这一切放在一起
def foldLeft[A, B](xs: List[A], z: B)(s: (B, A) => B): B = {
val f0 = (b: B) => b
def g(a: A, f: B=>B): B=>B =
t => f(s(t, a))
foldRight(xs, f0)(g)(z)
}
在阅读本书的这个级别上，我实际上更喜欢这种形式，因为它更明确且更容易理解。但是为了更接近解决方案的形式，我们可以内联和的定义f0（g我们不再需要在输入时声明类型g并且foldRight编译器推断它），给出：
def foldLeft[A, B](xs: List[A], z: B)(s: (B, A) => B): B =
foldRight(xs, (b: B) => b)((a, f) => t => f(s(t, a)))(z)
这正是问题所在，只是使用了不同的符号。就 foldLeft 而言，对于 foldRight 也是如此。
该代码将几个函数对象链接在一起，列表中的每个元素一个函数。这是一个更清楚地表明这一点的例子。
val f = (a: Int, b: Int) => a+b
val list = List(2,3,4)
println(list.foldLeft(1)(f))
val f1 = (b: Int) => f(b, 2)
val f2 = (b: Int) => f(b, 3)
val f3 = (b: Int) => f(b, 4)
val f4 = (b: Int) => b
val ftotal = f1 andThen f2 andThen f3 andThen f4
println(ftotal(1))
你可以把它想象成一个函数对象的链表。当您传入一个值时，它会“流动”通过所有函数。这有点像数据流编程。
这本书的作者在他们的github/fpinscala页面上提供了很好的解释。