Another Newbie question :)

[Keith Wansbrough]

> 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-)