在浏览Functional Programming in Scala时,我遇到了这个问题:
你可以在foldRight方面正确折叠左边吗?反过来怎么样?
在作者提供的解决方案中,他们提供了如下实现:
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)
(另一个折叠类似)。诀窍是在右折叠操作期间,我们不构建类型为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)
按要求。
我刚刚做了这个练习,想分享我是如何得出答案的(基本上与问题中的内容相同,只是字母不同),希望它对某人有用。
作为背景,让我们从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
所以我们需要从z
到(z * 3)
到(z * 2) * 3
到((z * 1) * 2) * 3
。
作为价值观,我们不能这样做:对于任意操作(z * 3)
,没有自然的方法可以从值(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))
或t => (((t * 1) * 2) * 3)
相同。
看起来很有效!最后我们将z
应用于此结果。
初步步骤应该是什么?我们将g
应用于3
和f0
以获得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
是A
类型g
是这些f
的类型,这是B => B
g
的类型是(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)
这正是问题所在,只是用不同的符号。类似地,对于foldRft而言,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页面提供了很好的解释。