λ Tony’s blog λ

B b = start
 
for(final A a : listOfA) {
  b = method(b, a);
}
 
return b;

listOfA.foldLeft(start)(method)

(start /: listOfA)(method)

10 Responses to “scala.List.foldLeft for Java programmers”

1. Matt Hellige Says:
   January 16th, 2008 at 3:35 am

   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.

2. Dave Says:
   February 11th, 2008 at 9:05 am

   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?

3. afsina Says:
   February 11th, 2008 at 9:36 am

   i find the syntax very confusing.

4. Ricky Clarkson Says:
   February 11th, 2008 at 10:54 am

   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.

5. Tony Morris Says:
   February 11th, 2008 at 11:03 am

   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.

6. Dave Says:
   February 11th, 2008 at 11:22 am

   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.

7. Tony Morris Says:
   February 11th, 2008 at 11:35 am

   “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:

   def flatMap[A, B](as: List[A], f: A => List[B]): List[B] = as.foldRight
   

   Here is another one:

   def map[A, B](as: List[A], f: A => B): List[B] = as.foldRight
   

   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!

8. Gavin Bong Says:
   February 11th, 2008 at 8:28 pm

   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

9. Tony Morris Says:
   February 12th, 2008 at 6:20 am

   Hi Gavin,
   Try this:

   scala> val alist = 1 :: 2 :: 3 :: Nil // can also be written List(1, 2, 3)
   alist: List[Int] = List(1, 2, 3)
   
   scala> alist.foldRight(0)((a,b) => a + b)
   res0: Int = 6
   
   scala> alist.foldRight(0)(_ + _) // better form
   res1: Int = 6
   
   scala> alist.foldLeft(0)(_ + _) // best form
   res2: Int = 6
   
   scala> (alist :\\ 0)((a,b) => a + b ) // thanks Ricky
   res3: Int = 6
   

10. Jason Says:
    November 12th, 2008 at 3:34 am

    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)
    }
    }

Leave a Reply