fold is a Swiss Army knife in functional programming. It is expressive enough to write an interpreter for a simple functional programming language.

Let’s start with a simple arithmetic language.

> data Expr = Const Int
>           | Add Expr Expr
>           | Mul Expr Expr

Writing an interpreter for this language is trivial.

> interp :: Expr -> Int
> interp (Const x) = x
> interp (Add e1 e2) = interp e1 + interp e2
> interp (Mul e1 e2) = interp e1 * interp e2

Writing a pretty printer is also easy.

> pretty :: Expr -> String
> pretty (Const x) = show x
> pretty (Add e1 e2) = "(" ++ pretty e1 ++ " + " ++ pretty e2 ++ ")"
> pretty (Mul e1 e2) = "(" ++ pretty e1 ++ " * " ++ pretty e2 ++ ")"

Sensitive readers might have noticed the duplication of code in interp and pretty. Yes, recursion on the structure of Expr is repeated.

We can extract recursion as foldExpr and algorithms as ExprA. foldExpr does recursion on the structure of Expr regardless of the algorithm being used.

> data ExprA a = ExprA
>   { val :: Int -> a
>   , add :: a -> a -> a
>   , mul :: a -> a -> a
>   }
> 
> foldExpr :: ExprA a -> Expr -> a
> foldExpr alg (Const i)   = val alg i
> foldExpr alg (Add e1 e2) = add alg (foldExpr alg e1) (foldExpr alg e2)
> foldExpr alg (Mul e1 e2) = mul alg (foldExpr alg e1) (foldExpr alg e2)

Now it is possible to define the interpreter just by giving val, add and mul functions.

> interpA :: ExprA Int
> interpA = ExprA
>   { val = id
>   , add = (+)
>   , mul = (*)
>   }

The same goes for pretty printer.

> prettyA :: ExprA String
> prettyA = ExprA
>   { val = show
>   , add = \a b -> "(" ++ a ++ " + " ++ b ++ ")"
>   , mul = \a b -> "(" ++ a ++ " * " ++ b ++ ")"
>   }

Here is our interp' function defined in terms of foldExpr and interpA.

> interp' :: Expr -> Int
> interp' = foldExpr interpA

We successfully isolated algorithms from recursion, but we are still not satisfied. ExprA is mostly duplication of Expr and defining foldExpr is boilerplate.

We can fix this by introducing F-algebras and catamorphisms. Interested readers might want to take a look at Bartosz Milewski’s Understanding F-Algebras article.

Chris Allen mentioned foldl as one of the newbie traps in Haskell.

foldl’ is always what you want, don’t use foldl!

Because foldl always has to examine the whole list, there is no reason to make it lazy. It just uses more memory to do the same thing as foldl'.

Real World Haskell also recommends using foldl' instead of foldl.

Due to the thunking behavior of foldl, it is wise to avoid this function in real programs: even if it doesn’t fail outright, it will be unnecessarily inefficient. Instead, import Data.List and use foldl’

Haskell Wiki compares foldr, foldl and foldl' and recommends using either foldr or foldl'.

foldl’ is the more efficient way to arrive at that result because it doesn’t build a huge thunk.

But here comes a question. If foldl' is almost always better than foldl, why do we have foldl anyway? It makes sense only when the combining function is non-strict in its first argument. (The example is taken from the Haskell Wiki.)

(?) :: Int -> Int -> Int
_ ? 0 = 0
x ? y = x*y

list :: [Int]
list = [2,3,undefined,5,0]

okey = foldl (?) 1 list
boom = foldl' (?) 1 list

Evaluation of okey:

okey -->
foldl (?) 1 [2,3,undefined,5,0] -->
foldl (?) (1 ? 2) [3,undefined,5,0] -->
foldl (?) ((1 ? 2) ? 3) [undefined,5,0] -->
foldl (?) (((1 ? 2) ? 3) ? undefined) [5,0] -->
foldl (?) ((((1 ? 2) ? 3) ? undefined) ? 5) [0] -->
foldl (?) (((((1 ? 2) ? 3) ? undefined) ? 5) ? 0) [] -->
((((1 ? 2) ? 3) ? undefined) ? 5) ? 0 -->
0

Evaluation of boom:

boom -->
foldl' (?) 1 [2,3,undefined,5,0] -->
    1 ? 2 --> 2
foldl' (?) 2 [3,undefined,5,0] -->
    2 ? 3 --> 6
foldl' (?) 6 [undefined,5,0] -->
    6 ? undefined -->
*** Exception: Prelude.undefined

This example actually shows why foldl is so useless because it is hard to find a function which is non-strict in its first argument.

Many functions in Haskell are non-strict in its second argument and this is why foldr is useful. For example, (&&) is non-strict in its second argument and and can be efficiently defined using foldr.

(&&)                    :: Bool -> Bool -> Bool
True  && x              =  x
False && _              =  False

and                     :: [Bool] -> Bool
and                     =  foldr (&&) True

In conclusion, we should use foldl' by default unless we have a very compelling reason to use foldl instead.

But, wait! Let’s check how our beloved sum function is written. Because (+) is strict in both of its arguments, foldl' should have been used. But here’s the actual code taken from the base package.

sum                     :: (Num a) => [a] -> a
{-# INLINE sum #-}
sum                     =  foldl (+) 0

OMG! There is a historical accident here. Interested readers are referred to Fixing foldl article from Well-Typed.

unfold

Every functional programmer loves fold. fold is universal and expressive. But fold has a secret twin brother named unfold which undoes what fold does. In this post, we will see what unfold is and how it is related to fold.

unfoldr builds a list from a seed value while foldr reduces a list to a summary value.

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

unfoldr takes the element and returns Nothing if it is done producing the list or returns Just (a, b), in which case, a is a prepended to the list and b is used as the next element in a recursive call.

For example, we can define iterate as follows:

iterate f == unfoldr (\x -> Just (x, f x))

Another simple use of unfoldr:

> unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
[10,9,8,7,6,5,4,3,2,1]

As the name suggests, unfold is the categorical dual of fold. (Maybe it should be cofold instead of unfold.) It means we can get the signature of foldr by reversing the arrows of unfoldr, and vice versa.

Let’s try this.

unfoldr :: (b -> Maybe (a, b)) -> (b -> [a])
foldr   :: (Maybe (a, b) -> b) -> ([a] -> b)

Oops! It is not our beloved foldr function whose signature is:

foldr :: (a -> b -> b) -> b -> [a] -> b

Type isomorphisms

But don’t be disappointed! We can show that they represent the same thing by using type isomorphisms:

(a → b → b) → b → ([a] → b)

by a -> b -> c ~= (a, b) -> c

((a, b) → b) → b → ([a] → b)

by a ~= () -> a

((a, b) → b) → (() -> b) → ([a] → b)

by a -> b -> c ~= (a, b) -> c

(((a, b) → b), (() -> b)) → ([a] → b)

by ((a -> c), (b -> c)) ~= Either a b -> c

((Either (a, b) ()) → b) → ([a] → b)

by Either a () ~= Maybe a

(Maybe (a, b) -> b) → ([a] → b)

Now we can clearly see that unfold is the dual of fold. If you want to learn more on the relationship between fold and unfold, see Conal Elliott’s Folds and unfolds all around us.

Implementation

Here’s an implementation of unfoldr.

unfoldr :: (b -> Maybe (a, b)) -> (b -> [a])
unfoldr f b = case f b of
                Just (a, b') -> a : unfoldr f b'
                Nothing -> []