data Tree a = Leaf a | Branch (Tree a) (Tree a)
fringe :: Tree a -> [a]
fringe (Leaf x) = [x]
fringe (Branch t1 t2) = (++) (fringe t1) (fringe t2)
treeSize :: Tree a -> Integer
treeSize (Leaf x) = 1
treeSize (Branch t1 t2) = (+) (treeSize t1) (treeSize t2)
treeHeight :: Tree a -> Integer
treeHeight (Leaf x) = 0
treeHeight (Branch t1 t2) = 1 + max (treeHeight t1) (treeHeight t2)
{-
fold' ?? (Leaf x) = ?
fold' ?? (Branch t1 t2) = f (fold' ?? t1) (fold' ?? t2)
fold' f g (Leaf x) = g x
fold' f g (Branch t1 t2) = f (fold' f g t1) (fold' f g t2)
g :: a -> b
f :: b -> b -> b
fold' :: (b->b->b) -> (a->b) -> Tree a -> b
-}
treeFold :: (b -> b -> b) -> (a -> b) -> Tree a -> b
treeFold f g (Leaf x) = g x
treeFold f g (Branch t1 t2) = f (treeFold f g t1) (treeFold f g t2)
treeSize' :: Tree a -> Integer
treeSize' = treeFold (+) (\_ -> 1)
fringe' :: Tree a -> [a]
fringe' = treeFold (++) (:[])
treeHeight' :: Tree a -> Integer
treeHeight' t = treeFold (\x y -> 1 + max x y) (\_ -> 0) t
----- some tests -----
t1 = Leaf 'a'
t2 = Branch (Leaf 'a') (Leaf 'b')
t3 = Branch (Branch (Leaf 'a') (Leaf 'b')) (Branch (Leaf 'c') (Leaf 'd'))
t4 = Branch (Branch (Leaf 'a') (Leaf 'b')) (Leaf 'c')
t = [t1, t2, t3, t4]
main = do
putStrLn $ "fringe ===> " ++ show (map fringe t)
putStrLn $ "fringe' ===> " ++ show (map fringe' t)
putStrLn $ "treeSize ===> " ++ show (map treeSize t)
putStrLn $ "treeSize' ===> " ++ show (map treeSize' t)
putStrLn $ "treeHeight ===> " ++ show (map treeHeight t)
putStrLn $ "treeHeight' ===> " ++ show (map treeHeight' t)
This entry was posted
on Wednesday, May 23rd, 2007 at 2:20 pm and is filed under Haskell - SOE.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.