reduce.hs

data List a = Nil
            | Cons a (List a)
              deriving Show

xs = Cons 1 (Cons 2 (Cons 3 Nil))

reduceList f z Nil         = z 
reduceList f z (Cons x xs) = f x (reduceList f z xs)

idList = reduceList Cons Nil

mapList f = reduceList (Cons . f) Nil

filterList p = reduceList (\x xs -> 
                             if p x then Cons x xs
                             else xs) 
                          Nil

mapListIf p f = reduceList (\x xs ->
                              if p x then Cons (f x) xs
                              else Cons x xs)
                           Nil

appendList xs1 xs2 = reduceList Cons xs2 xs1

reverseList = reduceList (\x xs -> xs `appendList` (Cons x Nil)) Nil


data Tree a = Node a (List (Tree a)) deriving Show

tree = Node 1 
            (Cons (Node 2 Nil)      
            (Cons (Node 3 
                        (Cons (Node 5 Nil) 
                        (Cons (Node 6 Nil) Nil)))
            (Cons (Node 4 Nil) Nil)))

reduceTree f g z (Node x trees) = 
    f x (reduceList g z (mapList (reduceTree f g z) trees))

idTree = reduceTree Node Cons Nil

mapTree f = reduceTree (Node . f) Cons Nil


reduceListTree f g z trees = 
    reduceList f z (mapList (reduceTree g f z) trees)

tree2ListTree tree = Cons tree Nil

mapListTree f = reduceListTree Cons (Node . f) Nil

filterListTree p = reduceListTree (\n@(Node x trees) ts -> 
                                   if p x then Cons n ts 
                                   else trees `appendList` ts)
                                  Node
                                  Nil