module Trees where import Char import List (sortBy) data Rose a = Branch a [Rose a] deriving Show -- List a = Nil | Cons a (List a) rsize :: Rose a -> Integer rsize (Branch x rs) = 1 + sum (map rsize rs) rheight (Branch x []) = 1 rheight (Branch x rs) = 1 + maximum (map rheight rs) rmap :: (a -> b) -> Rose a -> Rose b rmap f (Branch x rs) = Branch (f x) (map (rmap f) rs) data BTree a = Tip | BNode a (BTree a) (BTree a) deriving Show offices = [("Orr", 210), ("Levenick",206), ("Ruehr",208), ("Cheng",209)] insert (x,y) Tip = BNode (x,y) Tip Tip insert (x,y) (BNode (q,p) l r) = if x < q then BNode (q,p) (insert (x,y) l) r else BNode (q,p) l (insert (x,y) r) offtree = foldr insert Tip offices onntree = foldl (flip insert) Tip offices badtree = foldl (flip insert) Tip (sortBy (\(x,y) (p,q) -> compare x p) offices) awftree = foldr insert Tip (sortBy (\(x,y) (p,q) -> compare x p) offices) outline :: Show a => String -> BTree a -> String outline p Tip = p ++ "." outline p (BNode a l r) = unlines [outline ('\t':p) r, p++show a, outline ('\t':p) l] fold t b Tip = t fold t b (BNode x l r) = b x (fold t b l) (fold t b r) size' = fold 0 (\x y z -> 1 + y + z) height' = fold 0 (\x y z -> 1 + max y z) tmap' f = fold Tip (\x y z -> BNode (f x) y z) mirror' = fold Tip (\x y z -> BNode x z y) size :: BTree a -> Integer size Tip = 0 size (BNode x l r) = 1 + size l + size r height :: BTree a -> Integer height Tip = 0 height (BNode x l r) = 1 + max (height l) (height r) tmap :: (a -> b) -> BTree a -> BTree b tmap f Tip = Tip tmap f (BNode x l r) = BNode (f x) (tmap f l) (tmap f r) tlist :: BTree a -> [a] tlist Tip = [] tlist (BNode x l r) = concat [tlist l, [x], tlist r] mirror :: BTree a -> BTree a mirror Tip = Tip mirror (BNode x l r) = BNode x (mirror r) (mirror l) sample = BNode "Ben" (BNode "Wes" (BNode "Wes" Tip Tip) (BNode "Dianne" Tip Tip)) (BNode "Jenny" (BNode "John" Tip Tip) (BNode "Donna" Tip Tip)) leaf x = BNode x Tip Tip twig x y z = BNode x (leaf y) (leaf z) nums = BNode 1 (BNode 2 (leaf 4) (leaf 5)) (BNode 3 (leaf 6) (leaf 7)) rsample = Branch 'a' [Branch 'b' [ Branch 'c' [Branch 'd' []], Branch 'e' [ Branch 'f' [], Branch 'g' [], Branch 'h' [] ], Branch 'i' [Branch 'j' [] ], Branch 'k' [ Branch 'l' [], Branch 'm' [], Branch 'n' [], Branch 'o' [] ] ] ] perms [] = [[]] perms (x:xs) = concat (map (sperse x) (perms xs)) sperse x [] = [[x]] sperse x (y:ys) = (x:y:ys) : map (y:) (sperse x ys)