Data.Tree.AVL

[Christian Maeder]

Hello Adrian,

I've found some time to try out (part of) your library (below). And it 
speeded up my whole application for about 5%!

I've used the following "interface" to simulate Data.Map and was a bit 
uncertain if my construction of COrdings were all correct. (It's easy to 
exchange variables being compared, isn't it.)

Cheers Christian


import Data.Tree.AVL as AVL
import Data.COrdering
import Prelude hiding (null, lookup)

type Map a b = AVL (a, b)

empty :: Map a b
empty = AVL.empty

insert :: Ord a => a -> b -> Map a b -> Map a b
insert k v m = AVL.pushWith (\ (a, _) (c, _) ->
            case compare a c of
              LT -> Lt
              EQ -> Eq (k, v)
              GT -> Gt) (k, v) m

null :: Map a b -> Bool
null = AVL.isEmpty

lookup :: Ord a => a -> Map a b -> Maybe b
lookup k m = AVL.genTryRead m (\ (a, b) ->
            case compare k a of
              LT -> Lt
              EQ -> Eq b
              GT -> Gt)

findWithDefault :: Ord a => b -> a -> Map a b -> b
findWithDefault d k = maybe d id . lookup k

insertWith :: Ord a => (b -> b -> b) -> a -> b -> Map a b -> Map a b
insertWith f k v m = AVL.pushWith (\ (a, b) (c, d) ->
            case compare a c of
              LT -> Lt
              EQ -> Eq (k, f b d)
              GT -> Gt) (k, v) m

elems :: Ord a => Map a b -> [b]
elems m = map snd $ AVL.asListL m