I recently ran another Scala training course and I produced a hand-out that seemed to help people understand what a foldLeft is. Here is a brief explanation of it.
Suppose you have the following Java code:
B b = start
for(final A a : listOfA) {
b = method(b, a);
}
return b;
You can have any value for start, method and listOfA. Also, method may ignore any of its arguments or even not have them passed at all. You’ll notice that a lot of Java code is written this way, so it would be fair to say that “left folds occur a lot in Java”, despite being encoded as loops.
The above Java code is equivalent to the following Scala code, again for all values of the given identifiers (so long as they type check of course):
listOfA.foldLeft(start)(method)
…which is also equivalent to:
(start /: listOfA)(method)
…which by the way, is a perfectly sound approach to performing a list reduction, despite what some clowns rubbish on with.
That’s all, hope it helped 
I agree that this is a really natural way for Java programmers to comprehend a fold. I’d love to see an IDE for Scala (or Haskell, etc.) that allowed selective (and temporary) inlining of higher-order functions so that it would be possible to click on a line of code containing a fold and view/edit it as the expanded loop or recursive definition. This seems like the best of both worlds: easy to view the code in an expanded form when desired, but still avoiding the duplication and error-prone boilerplate.
It might seem like purely a tool for the inexperienced, but I’ve seen some pretty incomprehensible point-free definitions, and a tool like this might really help encourage the use of higher abstractions.
Purely out of curiousity, how often does fold get used over methods other than arithmetic sum and string concatenation? I can see those being very handy, but I can’t easily see many other use cases. I understand that Scala’s type system won’t support sum or concat as methods on List (because they only work for certain types of Lists, not all), but if it did, why would I ever use foldLeft?
Once you start using folds, you find that they’re everywhere – they’re a fundamental primitive when you want to avoid side effects or reason about a reduction from virtually any iterable data structure to an object that aggregates the data of that structure. In my code, I’ve found and eliminated a surprising number of bugs by converting iteration and manipulation of mutable data to folds. Something that seems to be true about functional programming in general is that it forces you to think about all the possibilities of what may happen in any given piece of code, but simplifies this task tremendously by illuminating corner cases that might otherwise hide in the inadvertent mutation of some piece of critical data.
One use of fold that impressed me when I was beginning, was from Venkat’s Programming Scala book to find the sum of factors of a number: (0 /: (1 to number)) { (sum, i) => if (number % i == 0) sum + i else sum }
This is a very nice way to iterate through numbers 1 to n, checking each along the way to see if it evenly divides into n, and if so add it to a running sum. Although this is similar to sum, I think it demonstrates a use of fold that may not be immediately obvious but is very useful once groked.
i find the syntax very confusing.
Dave,
Summing and stringifying are just the easiest cases to show. Fold gets used often throughout computing, though most people prefer to use a less abstract version. Haskell, for instance, has a ’sum’ function, which just delegates to foldl. Ruby has inject, which is more convenient, provided the list is not empty.
Java, C and others have a far less abstract version, the for loop, which is a small subset of what fold can do, if you include foldRight as a fold* – as it can handle folding over infinite lists. Poor programmers tend to feel more comfortable with this less abstract fold.
* To quickly understand how foldRight might work for an infinite list, if you have an infinite list of booleans, where the first is true and the rest false (or undefined, or unevaluated), you can easily see that folding with || across those only requires the 1st to be evaluated.
Hi Dave,
I’m a little apprehensive to answer your question, since the answer is quite deep and I wouldn’t want you to think otherwise. I don’t quite have the time to answer it in full for now, so I’ll just add a little to what Ricky has said:
* Ruby’s inject on non-empty lists is called reduce in Scala (you’ll find the method on List, Stream, etc.)
* Actually, it is possible to write a sum and concatenation on the scala.List[A] type; it would require an extra argument of type Monoid[A]
Furthermore, to answer your question without providing any explanation whatsoever (I hope you don’t mind), the answer is “an awful lot”. How many loops have you written in your time? They can all be abstracted to folds (more correctly called catamorphisms) and some can probably even be specialised to other Higher-Order Functions.
Sorry for the brevity in this response. I’ll have to think about how I’d tackle answering your (very common!) question. I think it comes about because the true answer to your question is so far removed (i.e. to the opposite extreme) from the intuition of who is typically asking it.
It’s okay for there not to be an easy answer, but it does seem to be a very serious question. Most of the for-loops I write in Java seem to be maps (85%) or flat-maps (10%), with sums and concatenations filling out most of the remaining 5%. (Curiously, it’s been years since I wrote a while or do-while loop, which are probably some lower-level fixed-point operation, mathematically speaking.) I get the theory of fold, think I understand the different use-cases of foldRight and foldLeft, get the relation to Monoids, and even fought my way through the bananas/lenses/barbed-wire paper to get some vague idea of catamorphisms, but it just seems like it’s covering a fairly minor use-case.
“it just seems like it’s covering a fairly minor use-case.”
I know it’s probably hard to “just trust anyone”, but I assure you that it is such a major use-case, that I am willing to bet that what you think I think is a severe under-estimate of what I really think, if you know what I mean
You say you have seen instances that could be described as “they were really maps or flatMaps”. Do you know that these are specific types of right folds? As are filter, List append, concatenation of Lists and many many more. This is just right folds; what about left? There is reverse, length, sum as you have mentioned and again, *many more*.
In the same Scala course, I have the students write functions in terms of foldRight and foldLeft. For example, here is an exercise, complete this code:
Here is another one:
And let’s make this clear; we’re only talking about Lists here. What about Binary Trees and BTrees and lazy lists and…?
You can hopefully see that it is the complete opposite (if such a thing could exist) of “minor use case” that is the reality.
I hope this helps a bit; again, sorry for the brevity
Oh and by the way, that paper you mention is an excellent read for anyone!
Tony,
I tried to run this on the prompt but couldn’t figure out how to call foldLeft/foldRight.
scala> val alist = 1 :: 2 :: 3 :: Nil
alist: List[Int] = List(1, 2, 3)
scala> alist.foldRight( 0, (a,b) => a + b )
<console>:6: error: wrong number of arguments for method foldRight: (B)((Int, B) => B)B
alist.foldRight( 0, (a,b) => a + b )
scala> ( alist :\ 1 )( (a,b) => a + b )
res7: Int = 7
What am I doing wrong ?
Thanks
Hi Gavin,
Try this:
This helped me tell my left from my right…
class FoldDemoTest extends TestCase(“folddemo”) {
def f(a:String, b:String):String = {
“f(” + a + “, ” + b + “)”
}
val list = List(“A”, “B”, “C”)
def testFoldLeft() = {
val value = list.foldLeft[String](“0″)(f)
assertEquals(“f(f(f(0, A), B), C)”, value)
}
def testFoldRight() = {
val value = list.foldRight[String](“0″)(f)
assertEquals(“f(A, f(B, f(C, 0)))”, value)
}
}
[...] http://dibblego.wordpress.com/2008/01/15/scalalistfoldleft-for-java-programmers/ [...]