在Functional Programming in Scala,作者要求通过FoldLeft表达FoldRight。然后作者提供以下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
。
所以我的问题是:
您编写了一个与foldRight
具有相同签名的实现,但是当组合操作不可交换时,它没有正确的语义。举一个例子,将空列表为零的右折叠和组合操作的缺点应该是标识:
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] = $$Lambda$1912/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)
因此,您的两个问题的答案都是“是”,您的实施与本书之间存在重大差异。