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 BinaryTree a = Empty
                  | Leaf a
                  | Branch (BinaryTree a) a (BinaryTree a)
                    deriving Show

btree = Branch (Leaf 1)
               2
               (Branch (Branch Empty
                               4
                               (Leaf 5))
                       3
                       Empty)

reduceBinaryTree f g z Empty          = z
reduceBinaryTree f g z (Leaf x)       = g x
reduceBinaryTree f g z (Branch l x r) = f (reduceBinaryTree f g z l)
                                          x
                                          (reduceBinaryTree f g z r)

mapBinaryTree f = reduceBinaryTree (\l x r -> Branch l (f x) r)
                                   (Leaf . f)
                                   Empty

filterBinaryTree2List p = reduceBinaryTree (\l x r -> 
                                            let lr = l `appendList` r
                                            in if p x then Cons x lr
                                               else lr)
                                           (\x -> if p x then Cons x Nil
                                                  else Nil)
                                           Nil