[Haskell] combining IntMaps

[Scherrer, Chad]

Thanks! It's interesting the way your AVL tree library is set up --
there seems to be a much broader degree of functionality than that
provided by Data.Set. But I'm trying to see, is there a significant
difference in the fundamental data structure, or is the main point that
the additional functionality could not have otherwise been provided in
an efficient way without going into the guts of Data.Set? 

Chad Scherrer

-----Original Message-----
From: Adrian Hey [mailto:ahey at iee.org] 
Sent: Wednesday, July 20, 2005 10:57 PM
To: Scherrer, Chad; haskell at haskell.org
Subject: Re: [Haskell] combining IntMaps

On Wednesday 20 Jul 2005 4:05 am, Scherrer, Chad wrote:
> I'm using the (IntMap Int) type to implement functions (Int -> Int), 
> by treating non-keys as values that map to zero. I'd like to be able 
> to add two of these pointwise, and delete the key from the resulting 
> map when the sum of the values is zero. My specification is
>
> addMaps :: IntMap Int -> IntMap Int -> IntMap Int addMaps m = 
> IntMap.filter (/= 0) . IntMap.unionWith (+) m
>
> But I'm not really happy with this because it traverses both maps for 
> the union, and then traverses the result to get rid of all the zeros.
> (This function is a performance bottleneck in my current code).

Examples like this are interesting because they show just how difficult
it is produce a comprehensive library for even one common or garden data
structure. I thought my AVL library was reasonably complete when I
released it, but I've subsequently thought of plenty of stuff that's
still missing (arguably), and you've just given me more.

Anyway, you might like to try using AVL trees which I have just upgraded
to provide the necessary functions..
 http://homepages.nildram.co.uk/~ahey/HLibs/Data.Tree.AVL/

You should be able to produce a reasonable alternative to Data.IntMap
with this. I'd be interested to know how it performs. I won't do the
whole thing myself, but here's a start (uses GHCs unboxed Ints).

{-# OPTIONS -fglasgow-exts #-}

import Data.COrdering
import Data.Tree.AVL
import GHC.Base

data IntAssoc = IntAssoc Int# Int# --Perhaps use boxed values instead??
newtype IMap = IMap (AVL IntAssoc)

emptyIMap :: IMap
emptyIMap = IMap empty

lookUp :: IMap -> Int -> Int
lookUp (IMap avl) (I# skey)  = genReadDefault 0 avl cmp  where cmp
(IntAssoc key v) = case compareInt# skey key of
                              LT -> Lt
                              EQ -> Eq (I# v)
                              GT -> Gt

set :: Int -> Int -> IMap -> IMap
set (I# k) (I# v) (IMap avl) = IMap avl'
 where avl' = if v ==# 0# then genDel cmp avl
                          else genPush ccmp ia avl
       ia = IntAssoc k v
       cmp  (IntAssoc k' _) = compareInt# k k'
       ccmp (IntAssoc k' _) = case compareInt# k k' of
                              LT -> Lt
                              EQ -> Eq ia
                              GT -> Gt

addMaps :: IMap -> IMap -> IMap
addMaps (IMap avl0) (IMap avl1) = IMap (genUnionMaybe ccmp avl0 avl1)
where ccmp (IntAssoc k0 v0) (IntAssoc k1 v1) =
        case compareInt# k0 k1 of
             LT -> Lt
             EQ -> let s = v0 +# v1 
                   in if s ==# 0# then Eq Nothing
                                  else Eq (Just (IntAssoc k0 s))
             GT -> Gt

Regards
--
Adrian Hey