An intuitive feel for Scala’s /: operator (foldLeft)

I’ve seen folks go a bit postal over Scala’s /: operator, pointing to it as proof that Scala is too difficult for most people to use. I find this a bit surprising, for a couple of reasons. First, programmers have to learn new syntax all the time; having to learn what /: means seems no different to me than having to learn what % {} [] != << and a dozen other symbols mean for a particular language in a particular context. For that matter, did we know what “class” meant in a program before it was explained to us? Or “protected” or “static” or “volatile” or …? Learning new concepts and how to incant them is a way of life for any programmer — unless they have decided not to learn any more languages and are hoping that obsolescence won’t catch up to them too quickly.

But I am also surprised by the scandal over the /: operator because I absolutely love the name. In fact, I would give /: and :\ the Best Operator Name award if there were such a thing. Hopefully after you read this, those symbols will never give you trouble again.

I think of /: as a picture of a domino falling to the right, into the first of a train of other dominoes, the way many of us set them up as kids to see them knock each other over. Every time the calculation-so-far makes contact with a new element in the train, the function is applied. Here, you will see it immediately from this example:

val nums = List(4,2,9,3,1)
val sum  = ( 0 /: nums ) (_+_)

      _ + _     _     _     _     _
     / / | |   | |   | |   | |   | |
    / /  | |   | |   | |   | |   | |
   /0/   |4|   |2|   |9|   |3|   |1|
  / /    | |   | |   | |   | |   | |
 /_/     |_|   |_|   |_|   |_|   |_|
        \____________nums___________/

            _ + _     _     _     _
           / / | |   | |   | |   | |
          / /  | |   | |   | |   | |
 0 + 4 = /4/   |2|   |9|   |3|   |1|
        / /    | |   | |   | |   | |
       /_/     |_|   |_|   |_|   |_|

                  _ + _     _     _
                 / / | |   | |   | |
                / /  | |   | |   | |
 (0 + 4) + 2 = /6/   |9|   |3|   |1|
              / /    | |   | |   | |
             /_/     |_|   |_|   |_|

                        _ + _     _
                       / / | |   | |
                      / /  | |   | |
   (0 + 4 + 2) + 9 = 15/   |3|   |1|
                    / /    | |   | |
                   /_/     |_|   |_|

                              _ + _
                             / / | |
                            / /  | |
     (0 + 4 + 2 + 9) + 3 = 18/   |1|
                          / /    | |
                         /_/     |_|

                                    _
                                   / /
                                  / /
       (0 + 4 + 2 + 9 + 3) + 1 = 19/
                                / /
                               /_/

[Of course, in reality you would just use nums.sum to get that answer, but I wanted a simple example with small integer values, and summing seemed a good choice.]

There are three reasons why I prefer the name /: over foldLeft. First, I find the latter ambiguous. It is the LEFT-associative fold method, meaning that the computation proceeds from LEFT to RIGHT. For some reason the direction of the operation feels to me like the thing that ought to determine the name, not the side you start from, so I constantly have to remind myself “foldLeft folds to the RIGHT.” Second, conciseness improves readability. As long as the names are clear (and to me /: is a crystal-clear diagram), shorter is better, especially for commonly used operations. That is, after all, why we don’t write “x multipliedBy y“. And third, (0 /: nums) and (nums :\ 0) switch the order of the arguments, again a visual aid to what is happening.

So please give that mental model a try — think of /: as “falls right into” rather than “fold left” — and see whether the domino metaphor allows you to read the code more fluently.

[other Scala posts]

About these ads

6 Comments

  1. Martin Odersky
    Posted August 10, 2010 at 1:59 pm | Permalink | Reply

    Brilliant! I always thought of these operators as left-or right-leaning trees, but your explanation is much better than that!

    • Posted August 11, 2010 at 2:17 am | Permalink | Reply

      Thanks! Of course, if you imagine the right-fallen dominoes on a board, and you tip up the right edge of the board, the dominoes take the shape of that very tree — albeit a bit squashed horizontally :^).

  2. John Potter
    Posted October 15, 2010 at 7:02 am | Permalink | Reply

    I wish I had found your blog entry before telling my class (functional OO (Scala) + concurrency) they should learn to use foldLeft etc. To avoid excessive scariness I avoided use of ‘/:’ etc., but no more!

    In the future I would like to refer to your metaphor as the “Sterling Domino”. Like Martin I think it is extremely apt.

    [Aside: Bear with me!
    In Australia we have had an ugly political history associated with dominoes! Post-WW2 our conservative governments exploited the fear of communism spreading in Asia calling it the "Domino Theory". This was political spin to encourage popular Australian support of American adventurism in Asia i.e. to avoid a collapse from the left. FWIW in most people's view the fight in Korea was justifiable, but that in Vietnam was not.]

    It is obvious that with the “Sterling Domino” model, (appropriately tilted to the left or right for the tree-view), the foldRight operator ‘:\’ collapses everything on the right. No wonder we eager people prefer ‘/: ‘, which is purely uplifting…it lifts the left-branch towards the root (aka heaven).

    So, the Sterling Domino model is worth adopting because it makes it clear that we all have two choices: collapse to the right, or lift up from the left!

    • Posted October 15, 2010 at 9:21 am | Permalink | Reply

      Wait, aren’t the operators \: and :/ in Australia?

      (Sorry — couldn’t resist. I appreciate the comment, and good luck with the class!)

  3. Posted July 2, 2013 at 2:47 am | Permalink | Reply

    In this ScalaDays 2013 keynote, Martin talks about foldLeft and /: at about 1:03:00.

    http://www.parleys.com/play/51c1994ae4b0d38b54f4621b/chapter0/about

  4. edcashin
    Posted September 29, 2013 at 1:25 am | Permalink | Reply

    Hi, Nicholas. Thanks to feedly.com, I am giving another go at following some favorite blogs, including yours. What a great post to start it off. I love the domino metaphor.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: