Data.Map, Data.Set working together

[Adrian Hey]

Hello,

On Tuesday 05 Apr 2005 9:51 am, Cale Gibbard wrote:
> It just crossed my mind that due to the apparent similarity in
> implementation it might be possible to implement some extra functions
> on Maps which take Sets as parameters and which are more efficient
> than first going through lists. For instance:
>

My AVL library was designed to allow easy implementation of things
like this (I.E. Uses general purpose AVL tree type and functions
rather than specialised Set/Map types).

 http://homepages.nildram.co.uk/~ahey/HLibs/Data.Tree.AVL/

> restrict :: Set a -> Map a b -> Map a b
> which would restrict the map's domain to the given set -- basically
> set intersection, but one of the objects is a map.

With the AVL library this would use..

genIntersection :: (a -> b -> COrdering c) -> AVL a -> AVL b -> AVL c

-- Assumes both trees are sorted
restrict :: Ord a => AVL a -> AVL (a,b) -> AVL (a,b)
restrict = genIntersection ccmp
 where ccmp a p@(a',_) = case compare a a' of
                         LT -> Lt
			 EQ -> Eq p
                         GT -> Gt

> fromFunction :: Set a -> (a -> b) -> Map a b
> Build a finite map in the obvious way from a set and a function.
> (basically, restrict the function on the potentially infinite domain a
> to the finite one given by the set, and record the result as a finite
> map) Depending on the way things work internally, perhaps the
> constructed Map could inherit the tree structure of the Set directly.

With the AVL library this would just be..

-- Assumes tree is sorted
fromFunction :: AVL a -> (a -> b) -> AVL (a,b)
fromFuncton set f = mapAVL' (\a -> (a, f a)) set -- uses strict map

or maybe a stricter version if you wanted..

fromFuncton' set f = mapAVL' (\a -> let b = f a in b `seq` (a,b)) set

> Thoughts? I haven't really looked at the code, but it seems plausible
> that these sorts of operations where a Set and Map are involved could
> be done in a better fashion than going through association lists.

Well (not that I'm biased at all :-), but I think all set/map users should
look at the AVL library. It's generally more efficient, flexible and gives
better control over practical things (like strictness control).

Both the old and the new set/map libraries are based on the weight balanced
trees Adams used in his "efficient sets" paper. Trouble is these don't seem
to be very efficient at all compared to AVL trees. I suspect they might be
a better choice sequences though.

BTW, I've been working on an improved version of the AVL library, which will
include..
 * Flexible zipper for AVL trees
 * AVL tree based clones of Data.Set and Data.Map
 * Other stuff too.

Hopefully I'll get that finished off soon.

Regards
--
Adrian Hey