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@iee.org] Sent: Wednesday, July 20, 2005 10:57 PM To: Scherrer, Chad; haskell@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
Hello, On Tuesday 26 Jul 2005 7:58 pm, Scherrer, Chad wrote:
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.
Well Data.Set is based on a different balanced tree type (weight balanced trees), similar to those used in the Adams paper. I'm also quite sceptical about the Hedge algorithm, so the AVL library doesn't use it. It uses divide and conquer, but not quite as Adams describes it. But IMO the biggest problem with Data.Set is the inflexible API. For example..
From Data.Set: union :: Ord a => Set a -> Set a -> Set a intersect :: Ord a => Set a -> Set a -> Set a
From Data.Tree.AVL: genUnion :: (e -> e -> COrdering e) -> AVL e -> AVL e -> AVL e genIntersection :: (a -> b -> COrdering c) -> AVL a -> AVL b -> AVL c
Of course there's no reason why similar functions could not be provided by Data.Set, but they're not there at present.
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?
Yes. This why producing useable libraries like this is so difficult. There's plenty of reasonable things you just can't do efficiently with Data.Set. Same is probably true of Data.Tree.AVL of course, but I'm trying to make it more complete all the time. Anyway, please try out AVL and let me know if there's anything more missing. Regards -- Adrian Hey
Adrian Hey wrote:
Hello,
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.
Well Data.Set is based on a different balanced tree type (weight balanced trees), similar to those used in the Adams paper. I'm also quite sceptical about the Hedge algorithm, so the AVL library doesn't use it. It uses divide and conquer, but not quite as Adams describes it.
Please note that the original mail was about "IntMap" and "IntSet" and these data structures use patricia trees and have a much different union algorithm alltogether. (a very good one actually -- one of the main reasons to make a special Map and Set instance for integers :-) )
But IMO the biggest problem with Data.Set is the inflexible API. For example..
From Data.Set: union :: Ord a => Set a -> Set a -> Set a intersect :: Ord a => Set a -> Set a -> Set a
From Data.Tree.AVL: genUnion :: (e -> e -> COrdering e) -> AVL e -> AVL e -> AVL e genIntersection :: (a -> b -> COrdering c) -> AVL a -> AVL b -> AVL c
You are right, but there is a reason for this: with the Set api I wanted to expose only operations that do not violate the notion of a mathematical set: ie. the ordering on the elements must be fixed or otherwise the invariants might not hold any longer. One way to insure this is by passing an ordering function when constructing a set, but a nicer way is to use overloading (since only a single instance can hold for the set). Of course, maybe it is a good idea to make two modules: a 'collection' data type that exposes internal operations, and a 'Set' module on top that implements sets and does not expose operations that could violate set invariants. You are right that these considerations do not make as much sense in the context of general AVL trees since no guarantee op "Set" functionality is given there. Same holds for the IntMap and Map interfaces. (but not for "Bag").
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?
Efficiency wise, I think one should only provide functions that ensure that the complexity does not get worse -- if one also considers functionality that improves on a constant factor (like traversing twice) there is no end to the number of functions that can be provided (as one is basically doing deforestation by hand). But this is of course just my personal opinion on how to control the size of the API. All the best, -- Daan Leijen.
Of course there's no reason why similar functions could not be provided by Data.Set, but they're not there at present.
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?
Yes. This why producing useable libraries like this is so difficult. There's plenty of reasonable things you just can't do efficiently with Data.Set. Same is probably true of Data.Tree.AVL of course, but I'm trying to make it more complete all the time.
Anyway, please try out AVL and let me know if there's anything more missing.
Regards -- Adrian Hey
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On Saturday 30 Jul 2005 7:07 pm, Daan Leijen wrote:
Efficiency wise, I think one should only provide functions that ensure that the complexity does not get worse -- if one also considers functionality that improves on a constant factor (like traversing twice) there is no end to the number of functions that can be provided (as one is basically doing deforestation by hand). But this is of course just my personal opinion on how to control the size of the API.
Actually, I think the point of Chads example is that the function he really needs is not a deforestation of the only solution available to him. The values in the two input maps are already known to satisfy the required condition. The test only needs to be applied on the new combined values (where the maps intersect). So I think it would be worthwhile to produce some kind of unionWithMaybe function. But I have no idea how to do this with IntMaps so I'm not volunteering :-) My 2p.. Regards -- Adrian Hey
participants (3)
-
Adrian Hey -
Daan Leijen -
Scherrer, Chad