BTree

module BinomialTree
   (
      BinTree,
      key,
      rank,
      children,
      createTree,
      mergeTrees,
      treeFoldr,
      treeFoldl
   ) where

data (Eq a, Ord a) => BinTree a = BTree a Int [BinTree a] deriving (Eq, Show)

key :: Ord a => BinTree a -> a
key (BTree a _ _) = a

rank :: Ord a => BinTree a -> Int
rank (BTree _ r _) = r

children :: Ord a => BinTree a -> [BinTree a]
children (BTree _ _ c) = c

createTree :: Ord a => a -> Int -> [BinTree a] -> BinTree a
createTree k r c = BTree k r c

mergeTrees :: Ord a => BinTree a -> BinTree a -> BinTree a
mergeTrees t1 t2 =
   if key t1 <= key t2 then
      BTree (key t1) (rank t1 + 1) ((children t1) ++ [t2])
   else
      mergeTrees t2 t1

treeFoldr :: Ord a => (a -> b -> b) -> b -> BinTree a -> b
treeFoldr f z (BTree k _ []) = f k z
treeFoldr f z (BTree k _ (hd:tl)) = treeFoldr f (treeFoldr f z hd) (BTree k 0 tl)

treeFoldl :: Ord a => (b -> a -> b) -> b -> BinTree a -> b
treeFoldl f z (BTree k _ []) = f z k
treeFoldl f z (BTree k _ (hd:tl)) = treeFoldl f (treeFoldl f z (BTree k 0 tl)) hd