-- $Id: FoldTree.hs,v 1.2 2013/10/02 01:47:08 leavens Exp leavens $
module FoldTree where
data Tree a = Lf
| Br (a, Tree a, Tree a)
deriving (Eq, Show)
-- We want to generalize the following functions on the above grammar
preorder :: Tree a -> [a]
preorder Lf = []
preorder (Br(v,t1,t2)) = [v] ++ preorder t1 ++ preorder t2
inc :: Num a => Tree a -> Tree a
inc Lf = Lf
inc (Br(v,t1,t2)) = Br(v + fromInteger 1, inc t1, inc t2)
-- It may be helpful to think of the following equivalent versions of the above
-- as these highlight the functions that are differences more clearly.
preorder0 Lf = []
preorder0 (Br(v,t1,t2)) =
(\v l1 l2 -> v:(l1 ++ l2)) v (preorder0 t1) (preorder0 t2)
inc0 Lf = Lf
inc0 (Br(v,t1,t2)) =
(\v t1 t2 -> Br(v + fromInteger 1, t1, t2)) v (inc0 t1) (inc0 t2)
-- We make the changing parts parameters in the following abstraction
foldTree :: (a -> b -> b -> b) -> b -> Tree a -> b
foldTree combine base Lf = base
foldTree combine base (Br(v, t1, t2)) =
combine v (recur t1) (recur t2)
where recur = foldTree combine base