Data.Tree.AVL

[Adrian Hey]

Hello Christian

On Thursday 19 Jan 2006 9:38 pm, Christian Maeder wrote:
> I've found some time to try out (part of) your library (below). And it
> speeded up my whole application for about 5%!

Thanks. The current AVL implementation isn't specialised for Maps (you
get an extra indirection overhead by using pairs), but AVL does seem to
more or less hold it's own against Data.Map despite this handicap for
basic operations like insert and lookup. Where I think you should
see significant improvement is in tree balancing if you end up
growing a tree from a sorted list (that you don't know is sorted)
and in Set operations (union etc). The Hedge algorithm seems to
require many more comparisons. Of course how much this contributes
to overall program speedup depends on a lot of things (what else
program is doing, how much comparison costs..)

> 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

I deprecated pushWith. The Data.Map clone I started (but haven't
got around to finishing) has insert defined thus..

newtype Map k a = Map (AVL.AVL (k,a))

insert :: Ord k => k -> a -> Map k a -> Map k a
insert k a (Map t) = Map (AVL.genPush cc (k,a) t)
 where cc (k',_) = case compare k k' of
                   LT -> COrdering.Lt
                   EQ -> COrdering.Eq (k',a)
                   GT -> COrdering.Gt

Here's my versions of some of the other functions (not
that I think there's anything wrong with yours).

> 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

readValCC :: Ord k => k -> (k,a) -> COrdering.COrdering a
readValCC k (k',a) = case compare k k' of
                     LT -> COrdering.Lt
                     EQ -> COrdering.Eq a
                     GT -> COrdering.Gt

lookup :: (Monad m,Ord k) => k -> Map k a -> m a
lookup k (Map t) = case AVL.genTryRead t (readValCC k) of
                   Just a  -> return a
                   Nothing -> fail "AvlMap.lookup: Key not found"

findWithDefault :: Ord k => a -> k -> Map k a -> a
findWithDefault def k (Map t) = AVL.genDefaultRead def t (readValCC 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

insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWith f k a (Map t) = Map (AVL.genPush cc (k,a) t)
 where cc (k',a') = case compare k k' of
                    LT -> COrdering.Lt
                    EQ -> COrdering.Eq (k',f a a')
                    GT -> COrdering.Gt

Regards
--
Adrian Hey