# Data.Map, Data.Set working together

Benjamin Franksen benjamin.franksen at bessy.de
Tue Apr 5 08:48:05 EDT 2005

```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/

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
```