在scala中使用FoldRight的FoldLeft

Question

在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实现的折叠,反之亦然？

谢谢

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.然后,我们组合所有这些函数,使得对应于最右边元素(我们开始遍历)的函数在组合链中最左边.最后,我们应用了大组合函数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)

按要求.

Answer 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],

• 这个foldRight将作用于3和[某事],给出[结果]
• 然后它将作用于2和[结果],给出[result2]
• 最后它将作用于1和[result2]给出最终表达式
• 我们希望我们的最终表达是 (((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放在适当的位置.

• 例如,在第一步之后(在执行3之后),我们有占位符功能z => (z * 3).或者更确切地说,作为一个函数必须采用任意值,我们一直在使用z特定值,让我们写这个t => (t * 3).(此函数应用于输入时z给出值(z * 3).)
• 在第二步之后(在执行2和结果之后)我们可能有占位符函数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):

• 第一个arg g是类型A
• 第二个arg 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.

Answer 3

该代码将多个函数对象链接在一起,列表中的每个元素都有一个函数.这是一个更清楚地显示的例子.

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))

您可以将其想象为功能对象的链接列表.传入一个值时,它会"流过"所有函数.这有点像数据流编程.