在浏览Functional Programming in 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)
有人能帮我追溯一下这个解决方案吗,让我明白这是如何用foldr实现foldl的,反之亦然?
谢谢
5条答案
按热度按时间b91juud31#
让我们一起来看看
(the其他折叠是类似的)。诀窍是在正确的折叠操作中,我们不构建类型
B
的最终值。相反,我们构建一个从B
到B
的函数,fold步骤取一个a: A
类型的值和一个g: B => B
函数,生成一个新的(b => g(f(b,a))): B => B
函数。该函数可以表示为g
与f(_, a)
的合成:我们可以这样看待这个过程:对于
l
的每个元素a
,我们取部分应用b => f(b,a)
,它是函数B => B
,然后,我们以这样的方式compose所有这些函数,即对应于最右边元素的函数(我们以此开始遍历)位于合成链的最左边。最后,我们在z
上应用big composed函数,这会产生一系列操作,从最左边的元素(在组合链中最右边)开始,到最右边的元素结束。**更新:**作为一个例子,让我们看看这个定义是如何在一个两元素列表上工作的。
现在让我们计算一下当我们传递给它
List(1,2)
时会发生什么:将此函数应用于
z
可得到根据需要。
1hdlvixo2#
我刚刚做了这个练习,想和大家分享一下我是如何得出答案的(基本上和问题中的答案一样,只是字母不同),希望能对大家有所帮助。
作为背景,让我们从
foldLeft
和foldRight
的作用开始,例如,使用操作*
和起始值z
对列表[1,2,3]执行foldLeft的结果是值((z * 1) * 2) * 3
我们可以将foldLeft看作从左到右递增地消耗列表的值,换句话说,我们最初从值
z
开始(这是如果列表为空的结果),则我们向foldLeft
揭示我们的列表以1开始并且值变为z * 1
,然后foldLeft
看到我们的列表,接下来有2
,值变成(z * 1) * 2
,最后,在作用于3之后,值变成((z * 1) * 2) * 3
。这个最终值是我们想要得到的值,除了(练习中要求我们)使用
foldRight
。现在注意,就像foldLeft
从左到右消耗列表的值一样,foldRight
从右到左消耗列表的值。所以在列表[1,2,3]上,(((z * 1) * 2) * 3
换句话说:使用
foldRight
,我们首先得出如果列表为空的结果,然后得出如果列表仅包含[3]的结果,然后得出如果列表为[2,3]的结果,最后得出列表为[1,2,3]的结果。也就是说,这些是我们希望使用
foldRight
得到的值:所以我们需要从
z
到(z * 3)
再到(z * 2) * 3
再到((z * 1) * 2) * 3
。作为 * values *,我们不能这样做:对于任意运算
*
,没有从值(z * 3)
到值(z * 2) * 3
的自然方法(乘法有,因为它是交换和结合的,但我们只使用*
来表示任意运算)。但是作为 * 函数 *,我们可以做到这一点!我们需要一个带有"占位符"或"孔"的函数:一个能把
z
放到合适位置的东西。z => (z * 3)
。或者更确切地说,作为一个函数必须接受任意值,并且我们已经使用z
来表示一个特定的值,让我们将其写为t => (t * 3)
。(该函数应用于输入z
,给出值(z * 3)
。)t => (t * 2) * 3
?我们可以从第一个占位符函数转到下一个吗?
用
f1
表示f2
是什么?是的,我们可以!所以我们想要的函数取
2
和f1
,得到f2
,我们称之为g
,我们有g(2, f1) = f2
,其中f2(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
作为恒等函数。让我们重新开始。
最后我们在z上应用f3得到我们想要的表达式,一切都解决了。
这意味着f3 =
foldRight(xs, f0)(g)
让我们定义
g
,这次不是使用x * y
,而是使用任意函数s(x, y)
:g
的第一个参数的类型为A
g
的第二个arg是这些f
的类型,即B => B
g
的类型为(A, (B=>B)) => (B=>B)
g
为:把这些放在一起
在本书的这个层次上,我实际上更喜欢这种形式,因为它更明确,更容易理解。但是为了更接近解决方案的形式,我们可以内联
f0
和g
的定义(我们不再需要声明g
的类型,因为它是foldRight
的输入,编译器会推断它),给出:这正是问题中的内容,只是用了不同的符号。类似地,对于foldright,就foldleft而言。
lymnna713#
这段代码将几个函数对象链接在一起,列表中的每个元素对应一个函数,下面的例子可以更清楚地说明这一点。
你可以把它想象成一个函数对象的链表,当你传入一个值时,它“流过”所有的函数,有点像数据流编程。
fae0ux8s4#
这本书的作者在他们的github/fpinscala页面上提供了很好的解释。
jexiocij5#
我认为@ShreevatsaR的回答有一个错误,它说foldLeft在用操作 * 作用于列表[1,2,3]之后,列表中的起始值z将是
(((z * 1) * 2) * 3
,忘记了关闭括号,然后它说foldRight将是((z * 1) * 2) * 3
,这与前一个语句相同,只是没有成对的括号。foldLeft和foldRight是不同的。foldLeft应该是
(((z * 1) * 2) * 3)
,正如答案中正确陈述的那样,除了不成对的括号现在是成对的。而foldRight应该是(1 * (2 * (3 * z)))
。我没有足够的声誉来发表评论,这就是为什么我做了这个答案,以便有人可以在这个被删除之前添加评论。