在Scala中使用FoldRight的FoldLeft [英] FoldLeft using FoldRight in scala

问题描述

在经历 Scala中的函数编程时，我遇到了一个问题:

While going through Functional Programming in Scala, I came across this question:

就foldRight而言，您可以正确对待foldLeft吗?换一种方式 在附近?

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

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

In solution provided by the authors they have provided an implementation as follows:

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)

有人可以帮助我追溯此解决方案并使我理解这实际上是如何根据文件夹实现文件夹的，反之亦然?

Can somebody help me trace through this solution and make me understand how this actually gets the foldl implemented in terms of foldr and vice-versa?

谢谢

推荐答案

让我们看看

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)的组合:

(the other fold is similar). The trick is that during the right fold operation, we don't build the final value of type B. Instead, we build a function from B to B. The fold step takes a value of type a: A and a function g: B => B and produces a new function (b => g(f(b,a))): B => B. This function can be expressed as a composition of g with f(_, a):

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

我们可以按以下方式查看该过程:对于l的每个元素a，我们采用部分应用程序b => f(b,a)，这是一个函数B => B.然后，我们组成所有这些函数，使得该函数对应于最右边的元素(通过该元素开始遍历) )位于组成链的最左侧.最后，我们在z上应用大组合函数.这样就产生了一系列操作，从最左边的元素(在合成链中最右边)开始，到最右边的元素结束.

We can view the process as follows: For each element a of l we take the partial application b => f(b,a), which is a function B => B. Then, we compose all these functions in such a way that the function corresponding to the rightmost element (with which we start the traversal) is at far left in the composition chain. Finally, we apply the big composed function on z. This results in a sequence of operations that starts with the leftmost element (which is at far right in the composition chain) and finishes with the right most one.

更新:作为示例，让我们检查一下此定义如何在两个元素的列表上起作用.首先，我们将函数重写为

Update: As an example, let's examine how this definition works on a two-element list. First, we'll rewrite the function as

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

Now let's compute what happens when we pass it 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会产生结果

Applying this function to z yields

f(f(z, 1), 2)

根据需要.

这篇关于在Scala中使用FoldRight的FoldLeft的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！