jrsall92 jrsall92 - 6 days ago 5
Scala Question

Scala fold right and fold left

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.

Answer

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, fildLeft/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.

Comments