Difference between fold and foldLeft or foldRight?

Question

NOTE: I am on Scala 2.8—can that be a problem?

Why can't I use the fold function the same way as foldLeft or foldRight?

In the Set scaladoc it says that:

The result of folding may only be a supertype of this parallel collection's type parameter T.

But I see no type parameter T in the function signature:

def fold [A1 >: A] (z: A1)(op: (A1, A1) ⇒ A1): A1 

What is the difference between the foldLeft-Right and fold, and how do I use the latter?

EDIT: For example how would I write a fold to add all elements in a list? With foldLeft it would be:

val foo = List(1, 2, 3) foo.foldLeft(0)(_ + _)  // now try fold: foo.fold(0)(_ + _) >:7: error: value fold is not a member of List[Int]   foo.fold(0)(_ + _)     ^ 

Answer 1

Short answer:

foldRight associates to the right. I.e. elements will be accumulated in right-to-left order:

List(a,b,c).foldRight(z)(f) = f(a, f(b, f(c, z))) 

foldLeft associates to the left. I.e. an accumulator will be initialized and elements will be added to the accumulator in left-to-right order:

List(a,b,c).foldLeft(z)(f) = f(f(f(z, a), b), c) 

fold is associative in that the order in which the elements are added together is not defined. I.e. the arguments to fold form a monoid.

Answer 2

fold, contrary to foldRight and foldLeft, does not offer any guarantee about the order in which the elements of the collection will be processed. You'll probably want to use fold, with its more constrained signature, with parallel collections, where the lack of guaranteed processing order helps the parallel collection implements folding in a parallel way. The reason for changing the signature is similar: with the additional constraints, it's easier to make a parallel fold.