September 8, 2026

Haskell for Hobos -- Folds

I'll say it again. When you think you need a loop, you generally need a list and some function from the Haskell library (or recursion).

I'll say another thing. My understanding of folds was totally flawed until I wrote this section. See the epilogue at the end.

We have seen map and zip with start with a list (or two) and produce another list. What a fold does is to start with a list and produce a result. The result is usually not a list, but it can be.

Suppose you wanted to add up all the elements in a list (assuming they were numerical values). You should be thinking about a fold. Actually you would just use the "sum" function from the Haskell library. But, let's ignore sum and write what we need using a fold. 

mysum ll = foldr (\x rv -> x + rv) 0 ll
I use the name "rv" to stand for "return value". This is one of my naming conventions in many situations. Here we have a binary function, expressed as a lambda that adds the first argument "x" onto the second argument. The constant "0" is an initializer for rv. You could consider the second argument an "accumulator".

There is a more succinct (and classy) way to write this (equivalent to the above) as follows: 

mysum ll = foldr (+) 0 ll
How about that?! Here the "+" operator, enclosed in parenthesis (a section) serves just fine as the 2 argument function we need. We could even go a step further and write: 
mysum = foldr (+) 0
Dropping the explicit single argument like this works when it would be the last thing tacked on the the function body. This is called "point free style" -- don't ask me why.

Deeper waters - foldl versus foldr

First I will note that in the general and common case where you are just generating a scalar result using a commutative operator like (+) it doesn't matter which you use -- just use foldr and get on with it.

There are both foldr and foldl. I thought that foldl ran through the list from left to right (it does), and foldr ran through the list from right to left (not the case, which is why we are here).

Both deal with the list from left to right. The difference is associativity, which requires some explanation.

A couple of comments deserve to be made at this point. It is recommended that you generally use foldr and ignore foldl. it is also stated that foldr can work with infinite lists, but foldl will fail. Clearly things are deeper than I thought.

Consider the following: 

foldr f z [a, b, c] == a `f` (b `f` (c `f` z))

foldl f z [a, b, c] == (((z `f` a) `f` b)) `f` c
Now consider these when the operator is (+) It is easy to see that it matters not at all whether we use foldr or foldl 
foldr f z [a, b, c] == a + (b + (c + z))

foldl f z [a, b, c] == (((z + a) + b)) + c
Now look what we get when the operator is a (++) and we are generating a list: 
foldr f z [a, b, c] == [a] ++ ([b] ++ ([c] ++ z))

foldl f z [a, b, c] == (((z ++ [a]) ++ [b])) ++ [c]
Both cases yield the original list all over again, and actually the function must be: 
\x rv = [x] ++ rv -- for foldr
\rv x = rv ++ [x] -- for foldl
Given this knowledge, let's write a function to reverse the order of elements in a string using each fold. And what the heck, let's show them written in point free style also: 
revlist ll = foldr (\x rv -> rv ++ [x]) [] ll
revlist = foldr (\x rv -> rv ++ [x]) []

revlist ll = foldl (\rv x -> [x] ++ rv) [] ll
revlist = foldl (\rv x -> [x] ++ rv) []
Once again, it is recommended that you just forget about foldl and always use foldr. That is reportedly what the people in the know do.

Infinite lists and foldr

What is this business about foldr handling infinite lists? Surely I cannot expect my list reversing function to work just because it uses foldr. We cannot use "sum" on an infinite list just because we implement it using foldr.

It can only be true in cases where Haskell laziness would not require traversing the entire list.

Here is the authoritative discussion:


From the above, we get the following definition of foldr: Notice that the right associativity is expressed by the recursion on the right. 
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)
By contrast, here is the definition of foldl: 
foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs
Here is the explanation from the above:
One important thing to note in the presence of lazy, or normal-order evaluation, is that foldr will immediately return the application of f to the recursive case of folding over the rest of the list. Thus, if f is able to produce some part of its result without reference to the recursive case, and the rest of the result is never demanded, then the recursion will stop. This allows right folds to operate on infinite lists. By contrast, foldl will immediately call itself with new parameters until it reaches the end of the list. This tail recursion can be efficiently compiled as a loop, but can't deal with infinite lists at all -- it will recurse forever in an infinite loop
Here is an example. The key point is the use of the || operator, which will yield True when the left argument is True and won't bother to try to evaluate the right argument. 
hasLargeNumber = foldr (\x rv -> x > 3 || rv) False [1..]
It indeed returns True for the infinite list of natural numbers given to it, as it should.

foldr1 and foldl1

These allow you to skip giving the initializer argument. In other words, they are a kind gesture towards lazy people. I'm not lazy, so I don't use these and was tempted to skip them.

They use the element on one end of the list as the initializer then process the remainder of the list like a regular fold of the same flavor.
So we could write our summing function as: 

mysum = foldr1 (+)

foldr1 uses the rightmost (last) element as the initializer.
foldl1 uses the leftmost (first) element as the initializer.

Once again, to understand these in depth (or at all correctly), we need to look at the definitions expressed as recursions: 

foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 _ [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)
foldr1 _ []     = error "foldr1: empty list"

foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 _ []     = error "foldl1: empty list"
foldl1 f (x:xs) = helper x xs
  where
    helper acc []     = acc
    helper acc (y:ys) = helper (f acc y) ys
Once again, foldr1 can work correctly with infinite lists while foldl1 will loop forever. Consider the following, which will immediately return True: 
infiniteTrue = [True, True, True ..]
result = foldr1 (||) infiniteTrue

Epilogue - foldl versus foldr

I had this all wrong. And I doubt whether I am the first. In large part, I blame the book "Learn you a Haskell" for an incomplete and misleading discussion of folds and for pretty much using foldl as the default of the two folds. Nobody is perfect.

The discussion there left me thinking that foldr traversed the input list from right to left, but it doesn't. I made the discovery when I wrote the following code, expecting it to reverse the order of a list: 

revlist ll = foldr (\x rv -> [x] ++ rv) [] ll
I worked just fine, but did not change the order at all.

The end of the story

I learned several lessons:

The first is that it is valuable to write a tutorial like this.

The second is that it is valuable and important to test even what seem to be simple or trivial examples when writing a tutorial like this. Testing reveals trivial typos or mistakes in understanding syntax -- but it also reveals total misunderstandings like this one.

A clue was the statement that foldr can handle infinite lists but foldl cannot. This made no sense (naturally) when I misuderstood the difference.

Have any comments? Questions? Drop me a line!

Tom's software pages / tom@mmto.org