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.

回答1:

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.

回答2:

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.