As a part of learning Haskell, I've implemented an AVL tree.  As of now, I've only implemented insertion.I've compared its performance to a Java implementation I've picked at random (www.github.com/justinethier/AVL-Tree/blob/master/AvlTree.java).It performs almost as well when given an ascending or descending list ([1..9999999] or [9999999..1]), but significantly slower (2-4X) for a randomly generated list of the same size.My question are:Why is it performing so badly?  My only guess is that it re-evaluates sub tree after rolls, but I don't understand Haskell well enough to know.What can I do to improve its performance?The code:data Tree a =   Empty |                Branch {    key     :: a,                            balance :: Int,                            left    :: Tree a,                            right   :: Tree a,                            up      :: Bool                              --used internally to stop updating balance                       }                deriving (Eq)leaf :: (Ord a, Eq a) => a -> Tree aleaf x = Branch x 0 Empty Empty True-- insert ------------------------------------treeInsert :: (Eq a, Ord a) => Tree a -> a -> Tree atreeInsert Empty x  = leaf xtreeInsert (Branch y b l r _) x   | x < y =    let nl@(Branch _ _ _ _ nlu) = treeInsert l x   -- nl = new left    in      if nlu        then if b==1                 then roll $ Branch y  2      nl r False                else        Branch y (b + 1) nl r (b /= (-1))         else               Branch y  b      nl r False  | x > y =     let nr@(Branch _ _ _ _ nru) = treeInsert r x   -- nr = new right    in      if nru         then if b==(-1)                then roll $ Branch y (-2)    l nr False                else        Branch y (b - 1) l nr (b /= 1)         else               Branch y  b      l nr False  | otherwise =            Branch x  b      l r  False-- rolls -------------------------------------roll :: (Eq a, Ord a) => Tree a -> Tree a-- ll rollroll (Branch y 2 (Branch ly 1 ll lr _) r _) =             Branch ly  0 ll (Branch y 0 lr r False) False-- rr rollroll (Branch y (-2) l (Branch ry (-1) rl rr _) _) =             Branch ry  0 (Branch y 0 l rl False) rr False-- lr rollsroll (Branch y 2 (Branch ly (-1) ll (Branch lry lrb lrl lrr _) _) r _) =    case lrb of      0  ->  Branch lry 0 (Branch ly 0   ll  lrl False)                          (Branch y  0   lrr r   False) False     1  ->  Branch lry 0 (Branch ly 0   ll  lrl False)                          (Branch y (-1) lrr r   False) False     (-1)-> Branch lry 0 (Branch ly 1   ll  lrl False)                          (Branch y  0   lrr r   False) False-- rl rollsroll (Branch y (-2) l (Branch ry 1 (Branch rly rlb rll rlr _) rr _) _) =    case rlb of      0  ->  Branch rly 0 (Branch y  0   l   rll False)                          (Branch ry 0   rlr rr  False) False     1  ->  Branch rly 0 (Branch y  0   l   rll False)                          (Branch ry (-1) rlr rr False) False     (-1)-> Branch rly 0 (Branch y  1   l   rll False)                          (Branch ry 0   rlr rr  False) False-- construct a tree --------------------------construct :: (Eq a, Ord a) => Tree a -> [a] -> Tree aconstruct = foldl' treeInsert-- rands -------------------------------------rands :: Int -> Int -> Int -> Int -> [Int]rands n low high seed = take n $ randomRs (low, high) (mkStdGen seed)-- test runmain = do    seed <- round `fmap` getPOSIXTime    let ma = 9999999    let t = construct Empty ( rands ma 1 ma seed )     start <- getPOSIXTime    end <- t `seq` getPOSIXTime    print (end - start)
Optimizing AVL tree
optimization;performance;haskell