Take the 2-minute tour ×

In Haskell, like in many other functional languages, the function foldl is defined such that, for example, foldl (-) 0 [1,2,3,4] = -10.

This is OK, because foldl (-) 0 [1, 2,3,4] is, by definition, ((((0 - 1) - 2) - 3) - 4).

But, in Racket, (foldl - 0 '(1 2 3 4)) is 2, because Racket "intelligently" calculates like this: (4 - (3 - (2 - (1 - 0)))), which indeed is 2.

Of course, if we define auxiliary function flip, like this:

(define (flip bin-fn)
  (lambda (x y)
    (bin-fn y x)))

then we could in Racket achieve the same behavior as in Haskell: instead of (foldl - 0 '(1 2 3 4)) we can write: (foldl (flip -) 0 '(1 2 3 4))

The question is: Why is foldl in racket defined in such an odd (nonstandard and nonintuitive) way, differently than in any other language?

share|improve this question
FWIW, Chez Scheme's fold-left is consistent with what you're expecting: (fold-left - 0 '(1 2 3 4)) is -10 and (fold-left cons '() '(1 2 3 4)) is ((((() . 1) . 2) . 3) . 4). –  erjiang Jan 13 '12 at 2:21

4 Answers 4

  • The Haskell definition is not uniform. In Racket, the function to both folds have the same order of inputs, and therefore you can just replace foldl by foldr and get the same result. If you do that with the Haskell version you'd get a different result (usually).

  • This has the nice byproduct where you're encouraged to choose either foldl or foldr according to their semantic differences. My guess is that with Haskell's order you're likely to choose according to the operation. You have a good example for this: you've used foldl because you want to subtract each number -- and that's such an "obvious" choice that it's easy to overlook the fact that foldl is usually a bad choice in a lazy language.

  • Another difference is that the Haskell version is more limited than the Racket version in the usual way: it operates on exactly one input list, whereas Racket can accept any number of lists. This makes it more important to have a uniform argument order for the input function).

  • Finally, it is wrong to assume that Racket diverged from "many other functional languages", since folding is far from a new trick, and Racket has roots that are far older than Haskell (or these other languages). The question can therefore go the other way: why is Haskell's foldl defined in a strange way? (And no, (-) is not a good excuse.)

share|improve this answer
I would upvote this 10 times if I could. :-D –  Chris Jester-Young Jan 8 '12 at 20:17
For what it's worth, I think that the reasoning is thus: for cons lists, foldr is precisely the natural catamorphism, and thus its first argument has type a -> b -> b over a list with constructor (:) :: a -> [a] -> [a]. On the other hand, foldl is precisely the natural catamorphism for a snoc list, built in reverse, and so the first argument has b -> a -> b for the imaginary constructor Snoc :: [a] -> a -> [a]. –  Antal S-Z Jan 9 '12 at 4:18
"The Haskell definition is not uniform" -- but it is! There exists x, y such that foldl (foldl f) x y is well-typed for all f in Haskell, and the same holds true for foldr (foldr f) x y. This is not true of Racket's foldl! Granted this doesn't matter much in Racket (not having currying) but currying is big in ML-derived languages so the order used in Haskell is important. Of course one could say foldl & foldr should both just use Haskell's foldr arg order. (BTW Eli -- I had a long discussion with SK once about this, it was one of the few times I was able to change his mind!) –  Chris K Jan 9 '12 at 14:59
foldl is not "usually" a bad choice in a lazy language - especially if you employ it to compute a single number, string or such like. If you need that number, you need it, there is no way around evaluating the whole list, no matter if from the right or from the left. –  Ingo Jan 9 '12 at 16:58
@Eli - the definition of foldl is tail recursive in Haskell, so it doen't use any stack space. The problem is sometimes when foldl builds a large thunk that represents the result. When that thunk is evaluated after foldl is done, then stack overflows may happen. Use foldl' in such cases which needs constant stack space. Btw, the same problem with the unevaluated thuks can happen with foldr f where f is strict in its second argument. –  Ingo Jan 9 '12 at 17:30

"differently than in any other language"

As a counter-example, Standard ML (ML is a very old and influential functional language)'s foldl also works this way: http://www.standardml.org/Basis/list.html#SIG:LIST.foldl:VAL

share|improve this answer

Racket's foldl and foldr (and also SRFI-1's fold and fold-right) have the property that

(foldr cons null lst) = lst
(foldl cons null lst) = (reverse lst)

I speculate the argument order was chosen for that reason.

share|improve this answer

From the Racket documentation, the description of foldl:

(foldl proc init lst ...+) → any/c

Two points of interest for your question are mentioned:

the input lsts are traversed from left to right


foldl processes the lsts in constant space

I'm gonna speculate on how the implementation for that might look like, with a single list for simplicity's sake:

(define (my-foldl proc init lst)
  (define (iter lst acc)
    (if (null? lst)
        (iter (cdr lst) (proc (car lst) acc))))
  (iter lst init))

As you can see, the requirements of left-to-right traversal and constant space are met (notice the tail recursion in iter), but the order of the arguments for proc was never specified in the description. Hence, the result of calling the above code would be:

(my-foldl - 0 '(1 2 3 4))
> 2

If we had specified the order of the arguments for proc in this way:

(proc acc (car lst))

Then the result would be:

> -10

My point is, the documentation for foldl doesn't make any assumptions on the evaluation order of the arguments for proc, it only has to guarantee that constant space is used and that the elements in the list are evaluated from left to right.

As a side note, you can get the desired evaluation order for your expression by simply writing this:

(- 0 1 2 3 4)
> -10
share|improve this answer
Personally, I would much rather the description for a function was specific about the result it returns than how much stack space it uses! –  Ben Jan 9 '12 at 23:31
@Ben the doc does show an example application of > (foldl cons '() '(1 2 3 4)) ==> '(4 3 2 1) which can only be with one specific order of args. They could stress it some more, I agree. –  Will Ness Feb 4 '13 at 17:31

Your Answer


