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