通过 Scala 中的 FoldLeft 可读 FoldRight

Question

在Functional Programming in Scala, the author asks to express FoldRight via FoldLeft. And then the author offers the following implementation中：

  def foldRightViaFoldLeftAuthor[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)
  }

有几个问题如this要求解释作者的解决方案。并且可能还有很多人还在努力理解它。

当我考虑这个任务时，我想到了一个不同的实现，它看起来更具可读性，至少对我来说更容易掌握

  def foldRightViaFoldLeftMy[A, B](l: List[A], z: B)(f: (A, B) => B): B = {
    foldLeft(l, z)(((g: (A, B) => B) => (b: B, a: A) => g(a, b)) (f))
  }

所以我基本上准备了一个将 f(a,b) 转换为 f(b,a) 的函数，现在我可以调用尾递归的 foldLeft。

所以我的问题是：

有没有理由按照作者的方式来实现？
与作者的相比，我的实现有什么缺点吗？

Answer 1

您已经编写了一个与 foldRight 具有相同签名的实现，但是当组合操作不可交换时它没有正确的语义。举个例子，以空列表为零，cons为组合操作的右折叠应该是identity:

scala> val input = List(1, 2, 3)
input: List[Int] = List(1, 2, 3)

scala> val f: (Int, List[Int]) => List[Int] = _ :: _
f: (Int, List[Int]) => List[Int] = $$Lambda12/991363637@5e9bf744

scala> foldRightViaFoldLeftAuthor(input, List.empty[Int])(f)
res0: List[Int] = List(1, 2, 3)

但是你的实现颠倒了列表：

scala> foldRightViaFoldLeftMy(input, List.empty[Int])(f)
res1: List[Int] = List(3, 2, 1)

这是因为您仍在从左向右折叠，即使您已经切换了组合函数参数的顺序。我发现 the Wikipedia page about fold 上的图表对于可视化差异很有用。在您的实施中，应用程序是这样发生的：

scala> f(3, f(2, f(1, Nil)))
res2: List[Int] = List(3, 2, 1)

虽然在本书的实现中你有这样的东西：

((b3: List[Int]) =>
  ((b2: List[Int]) =>
    ((b1: List[Int]) => identity(f(1, b1)))(f(2, b2)))(f(3, b3)
  )
)(Nil)

归结为：

scala> f(1, f(2, f(3, Nil)))
res3: List[Int] = List(1, 2, 3)

所以你的两个问题的答案都是"yes"，你的实现和书中的有一个重要的区别。

通过 Scala 中的 FoldLeft 可读 FoldRight

Readable FoldRight via FoldLeft in Scala

scala

functional-dependencies