# Another Newbie question :)

Keith Wansbrough Keith.Wansbrough at cl.cam.ac.uk
Wed Nov 5 12:27:35 EST 2003

```> I seem to understand the basic idea behind the fold function, i think but do
> not seem to be able to write them myself. My understanding is that it works
> by replacing every constructor with a fold ?

I think you mean "replaces every constructor with a function or
constant".

Think of a list [1,2,3].  Recall this is "syntactic sugar"
(abbreviation) for 1:(2:(3:[])).  That looks like

:
1 \
:
2 \
:
3 \
[]

in memory.

Recall (+) is the function that takes two arguments and returns their
sum.

Now do

foldr (+) 0 [1,2,3]

What happens is that (:) is replaced by the first argument (+) and []
is replaced by the second argument 0, as follows:

+
1 \
+
2 \
+
3 \
0

This is just 1+(2+(3+0)), which is 6.

You can see this from the definition of foldr:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z   []   = z
foldr f z (x:xs) = f x (foldr f z xs)

where clearly every [] is replaced by z and every : by f.

A similar fold can be written for any datatype; it just takes a
different number of arguments, one for every constructor.  The general
term is "catamorphism".  E.g.:

data Expr = Num Int
| Plus Expr Expr
| Times Expr Expr

foldExpr :: Int -> (b -> b -> b) -> (b -> b -> b) -> b
foldExpr n p t (Num   i    ) = n i
foldExpr n p t (Plus  e1 e2) = p (foldExpr n p t e1) (foldExpr n p t e2)
foldExpr n p t (Times e1 e2) = t (foldExpr n p t e1) (foldExpr n p t e2)

Hope this helps.

> Could anyone please point me in the direction of a suitable resource of
> attempt to explain this to me :)

You could try googling for "catamorphism", or looking at some of Erik
Meijer et al's papers on "bananas, lenses, and barbed wire" and so on.

--KW 8-)
```