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