--------------------
-- 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)