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-)
More information about the Haskell-Cafe
mailing list