Scala fold right and fold left

14
votes

I am trying to learn functional programming and Scala, so I'm reading the "Functional Programming in Scala" by Chiusano and Bjarnason. I' m having trouble understanding what fold left and fold right methods do in case of a list. I've looked around here but I haven't find something beginner friendly. So the code provided by the book is:

def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B = as match {
  case Nil => z
  case Cons(h, t) => f(h, foldRight(t, z)(f))
}

def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
  case Nil => z
  case Cons(h,t) => foldLeft(t, f(z,h))(f)
}

Where Cons and Nil are:

case class Cons[+A](head: A, tail: List[A]) extends List[A]
case object Nil extends List[Nothing]

So what do actually fold left and right do? Why are needed as "utility" methods? There are many other methods that use them and I have trouble to understand them as well, since I don't get those two.

2
scalafunctional-programmingpurely-functionalfoldleft
have a look at the next thread. stackoverflow.com/questions/24370549/… there is a lot of information regarding these operations. Looks like a duplicate to me. – Pavel
In that question it seems the user asking has a pretty good understanding of the matter at hand, I don't, which is what I want help with. – jrsall92
For the code you have provided. Do you have any specific question? What exactly create a difficulty? syntax ? The key to understand the difference is the way recursive call made to itself in both cases. Its different. Read about tail recursion. Hope this will help. More links: oldfashionedsoftware.com/2009/07/10/… – Pavel
If you have time and would really like to put pieces together. mitpress.mit.edu/sicp - reading will take some time. Could be selective reading if base computer science knowledge strong. Good luck. – Pavel
@jrsall92 you are right. – michaJlS

2 Answers

34
votes

According to my experience, one of the best ways to workout the intuition is to see how it works on the very simple examples:

List(1, 3, 8).foldLeft(100)(_ - _) == ((100 - 1) - 3) - 8 == 88
List(1, 3, 8).foldRight(100)(_ - _) == 1 - (3 - (8 - 100)) == -94

As you can see, foldLeft/Right just passes the element of the list and the result of the previous application to the the operation in second parentheses. It should be also mentioned that if you apply these methods to the same list, they will return equal results only if the applied operation is associative.

5
votes

Say you have a list of numbers, and you want to add them all up. How would you do that? You add the first and the second, then take the result of that, add that to the third, take the result of that, add it to the fourth.. and so on.

That's what fold let's you do.

List(1,2,3,4,5).foldLeft(0)(_ + _)

The "+" is the function you want to apply, with the first operand being the result of its application to the elements so far, and the second operand being the next element. As you don't have a "result so far" for the first application, you provide a start value - in this case 0, as it is the identity element for addition.

Say you want to multiply all of your list elements, with fold, that'd be 

List(1,2,3,4,5).foldLeft(1)(_ * _)

Fold has it's own Wikipedia page you might want to check.

Of course there are also ScalaDoc entries for foldLeft and foldRight.