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