Data.Map, Data.Set working together

Cale Gibbard cgibbard at
Tue Apr 5 04:51:37 EDT 2005

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.

 - Cale

More information about the Libraries mailing list