Henning Thielemann | 15 Nov 11:34 2012
Picon

intersectionSet, differenceSet


When using the new Data.Map.fromSet function I encountered that I use it 
many times in connection with Map.intersection and Map.difference like so

   Map.intersection m (Map.fromSet (const ()) s)
   Map.difference m (Map.fromSet (const ()) s)

Actually the element types of the second operands of Map.intersection and 
Map.difference are completely independent and the values of these maps are 
not touched. Thus I think that intersection and difference with a Set are 
the more natural operation. How about adding

   Map.intersectionSet :: Ord k => Map k a -> Set k -> Map k a
   Map.differenceSet :: Ord k => Map k a -> Set k -> Map k a

to Data.Map?
Andreas Abel | 15 Nov 12:14 2012
Picon

Re: intersectionSet, differenceSet

Sounds ok, by why especially for Set.  Why not (also)

     Map.intersectionList :: Ord k => Map k a -> [k] -> Map k a
     Map.differenceList :: Ord k => Map k a -> [k] -> Map k a

? Screams for a generalization.

On 15.11.12 11:34 AM, Henning Thielemann wrote:
>
> When using the new Data.Map.fromSet function I encountered that I use it
> many times in connection with Map.intersection and Map.difference like so
>
>    Map.intersection m (Map.fromSet (const ()) s)
>    Map.difference m (Map.fromSet (const ()) s)
>
> Actually the element types of the second operands of Map.intersection
> and Map.difference are completely independent and the values of these
> maps are not touched. Thus I think that intersection and difference with
> a Set are the more natural operation. How about adding
>
>    Map.intersectionSet :: Ord k => Map k a -> Set k -> Map k a
>    Map.differenceSet :: Ord k => Map k a -> Set k -> Map k a
>
> to Data.Map?
>
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
(Continue reading)

Henning Thielemann | 15 Nov 23:05 2012
Picon

Re: intersectionSet, differenceSet


On Thu, 15 Nov 2012, Andreas Abel wrote:

> Sounds ok, by why especially for Set.  Why not (also)
>
>    Map.intersectionList :: Ord k => Map k a -> [k] -> Map k a
>    Map.differenceList :: Ord k => Map k a -> [k] -> Map k a
>
> ? Screams for a generalization.

I assume that Map.differenceSet can make use of the internal tree 
structure of a set and is thus more efficient. The documentation of 
Map.difference says it uses an adaption of hedge-union and this could also 
be used for Map.differenceSet.
Milan Straka | 16 Nov 08:40 2012
Picon

Re: intersectionSet, differenceSet

> On Thu, 15 Nov 2012, Andreas Abel wrote:
> 
> >Sounds ok, by why especially for Set.  Why not (also)
> >
> >   Map.intersectionList :: Ord k => Map k a -> [k] -> Map k a
> >   Map.differenceList :: Ord k => Map k a -> [k] -> Map k a
> >
> >? Screams for a generalization.
> 
> I assume that Map.differenceSet can make use of the internal tree
> structure of a set and is thus more efficient. The documentation of
> Map.difference says it uses an adaption of hedge-union and this
> could also be used for Map.differenceSet.

This is true for Map and Set, although the difference versus
  Map.insersection m (fromSet (const ()) s)
will be probably minor.

It is not the case for IntMap and IntSet, as these has different
representation.

Cheers,
Milan

Gmane