As defined by Scala, foldLeft
is a linear operation while fold
is allowed to be a tree operation. For example:
List(1,2,3,4,5).foldLeft(0)(_ + _)
// This is the only valid order of operations
0+1 = 1
1+2 = 3
3+3 = 6
6+4 = 10
10 + 5 = 15
15 // done
List(1,2,3,4,5).fold(0)(_ + _)
// This is valid
0+1 = 1 0+3 = 3 0+5 = 5
1+2 = 3 3+4 = 7 5
3 + 7=10 5
10 + 5 = 15
15 // done
In order to allow arbitrary tree decompositions of a sequential list, you must have a zero that doesn’t do anything (so you can add it wherever you need it in the tree) and you must create the same sort of thing that you take as your binary arguments so the types don’t change on you depending on how you decompose the tree.
(Being able to evaluate as a tree is nice for parallelization. If you want to be able to transform your output time as you go, you need both a combination operator and a standard start-value-transforms-sequence-element-to-desired-type function just like foldLeft
has. Scala has this and calls it aggregate
, but in some ways this is more like foldLeft
than fold
is.)