-------------------- -- Binary trees, traversal and treesort data BTree a = Tip | Branch a (BTree a) (BTree a) deriving (Show, Eq, Ord) fold t b Tip = t fold t b (Branch a l r) = b a (fold t b l) (fold t b r) inorder = fold [] (\x l r -> l ++ x : r) summ = fold 0 (\x l r -> x + l + r) prod = fold 1 (\x l r -> x * l * r) size = fold 0 (\x l r -> 1 + l + r) depp = fold 0 (\x l r -> 1 + l `max` r) {- inn :: BTree a -> [a] inn Tip = [] inn (Branch x l r) = inn l ++ (x : inn r) summ :: BTree Int -> Int summ Tip = 0 summ (Branch x l r) = x + summ l + summ r prod :: BTree Int -> Int prod Tip = 1 prod (Branch x l r) = x * prod l * prod r size :: BTree a -> Int size Tip = 0 size (Branch x l r) = 1 + size l + size r depp :: BTree a -> Int depp Tip = 0 depp (Branch x l r) = 1 + (depp l `max` depp r) -} ins x Tip = Branch x Tip Tip ins x (Branch y l r) | x <= y = Branch y (ins x l) r | otherwise = Branch y l (ins x r) buildtree :: Ord a => [a] -> BTree a buildtree = foldr ins Tip treesort :: Ord a => [a] -> [a] treesort xs = inorder (buildtree xs) t :: BTree Int t = Branch 3 (Branch 1 Tip (Branch 2 Tip Tip)) (Branch 5 (Branch 4 Tip Tip) (Branch 7 Tip (Branch 9 Tip Tip)) ) -------------------- -- Base conversions for numerals unfoldl p f a x = if p x then a else unfoldl p f (y:a) r where (r,y) = f x sumProd b n m = n * b + m contract b = foldl (sumProd b) 0 expand b = unfoldl (==0) (`divMod` b) [] number b = contract b . map digitToInt string b = map intToDigit . expand b [ (bin, unbin), (dec, undec), (hex, unhex) ] = map base [2, 10, 16] where base b = (string b, number b)