Data.Map, Data.Set working together

[Benjamin Franksen]

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