Search code examples
scalafunctional-dependencies

Readable FoldRight via FoldLeft in Scala

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

There have been a couple of questions like this asking to explain the author's solution. And probably a lot of people are still struggling to understand it.

While I was thinking about the task I came up with a different implementation that seems much more readable and easier to grasp at least for me

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

So I basically prepare a function that converts f(a,b) to f(b,a) and now I'm able to call foldLeft that is tail-recursive.

So my questions are:

  1. Is there any reason to implement it in the way the author did?
  2. Are there any drawbacks in my implementation in comparison to the author's?
Solution

  • You've written an implementation that has the same signature as foldRight, but it doesn't have the right semantics when the combination operation isn't commutative. To take one example, a right fold with the empty list as zero and cons as the combination operation should be 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] = $$Lambda$1912/991363637@5e9bf744

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

    But your implementation reverses the list:

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

    This is because you're still folding from left to right, even though you've switched the order of the combination function's arguments. I find the diagrams on the Wikipedia page about fold useful for visualizing the difference. In your implementation the applications happen like this:

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

    While in the book's implementation you have something like this:

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

    Which boils down to:

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

    So the answer to both of your questions is "yes", there is an important difference between your implementation and the book's.