How do you know when to use fold-left and when to use fold-right?
I'm aware that fold-left produces left-leaning trees and fold-right produces right-leaning trees, but when I reach for a fold, I sometimes find myself getting bogged down in headache-inducing thought trying to determine which kind of fold is appropriate. I usually end up unwinding the entire problem and stepping through the implementation of the fold function as it applies to my problem.
So what I want to know is:
- What are some rules of thumb for determining whether to fold left or fold right?
- How can I quickly decide which type of fold to use given the problem I'm facing?
There is an example in Scala by Example (PDF) of using a fold to write a function called flatten which concatenates a list of element lists into a single list. In that case, a right fold is the proper choice (given the way the lists are concatenated), but I had to think about it a bit to arrive at that conclusion.
Since folding is such a common action in (functional) programming, I'd like to be able to make these kinds of decisions quickly and confidently. So... any tips?
Answer
You can transfer a fold into an infix operator notation (writing in between):
This example fold using the accumulator function x
fold x [A, B, C, D]
thus equals
A x B x C x D
Now you just have to reason about the associativity of your operator (by putting parentheses!).
If you have a left-associative operator, you'll set the parentheses like this
((A x B) x C) x D
Here, you use a left fold. Example (haskell-style pseudocode)
foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative
If your operator is right-associative (right fold), the parentheses would be set like this:
A x (B x (C x D))
Example: Cons-Operator
foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3]
In general, arithmetic operators (most operators) are left-associative, so foldl is more widespread. But in the other cases, infix notation + parentheses is quite useful.