Another Newbie question :)

[Derek Elkins]

On Wed, 5 Nov 2003 07:17:23 -0800 (PST)
Hal Daume III <hdaume at ISI.EDU> wrote:

> Keith is entirely correct.
> 
> > 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.
> 
> I had heard this before when I was first beginning and didn't really
> find it "clear" :).  I think if you write foldr with f in infix
> notation it's a bit more clear:
> 
> > foldr f z       [] = z
> > foldr f z   (x:xs) = x `f` foldr f z xs
> 
> or even write the second line as
> 
> > foldr f z   (x:xs) = x `f` xs'
> >   where xs' = foldr f z xs
> 
> I think in this case it's a bit more clear how "f" is replacing the
> ":".
> 
>  - Hal

Simply choose better names,
data Tree a = Empty | Leaf a | Branch (Tree a) (Tree a)

foldTree empty leaf branch Empty = empty
foldTree empty leaf branch (Leaf a) = leaf a
foldTree empty leaf branch (Branch l r)
    = branch (foldTree empty leaf branch l)
             (foldTree empty leaf branch r)

data List a = Nil | Cons a (List a)
foldList nil cons Nil = nil
foldList nil cons (Cons a as) = cons a (foldList nil cons as)