On Tuesday 05 April 2005 10:51, 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:
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.
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.
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.
You might be interested in using http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/ instead of Data.*. It is a framework for abstract collections (with interesting implementations, too) where the things you want come out almost automatically. For instance, in the interface http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/Collections.hs you'll find these definitions: class ( Collection coll (a, b) , Eq a, Eq b -- , Ord a, Ord b ) => AssociativeCollection coll a b where domain :: Collection coll' a => coll (a, b) -> coll' a range :: Collection coll' b => coll (a, b) -> coll' b -- [...] (<|), (<-|) :: OrderedSet set a => set a -> coll (a, b) -> coll (a, b) (|>), (|->) :: OrderedSet set b => coll (a, b) -> set b -> coll (a, b) set <| rel = filter ((set`has`).fst) rel set <-| rel = filter (not.(set`has`).fst) rel rel |> set = filter ((set`has`).snd) rel rel |-> set = filter (not.(set`has`).snd) rel Ben