Proposal: IntMap.differenceKeysSet for removing an IntSet of keys

[Liyang HU]

Greetings!

On 13 June 2011 21:40, Milan Straka <fox at ucw.cz> wrote:
> My point was, that there are many combinations you can think of --
> IntMap minus IntSet, IntMap minus Map Int, IntMap minus list of Ints,
> IntMap union Map Int, IntMap intersection IntSet, IntMap intersection
> Set Int and so on.

Actually, it's just IntMap and IntSet, since they share the same
underlying patricia tree implementation.

> I am quite unhappy about exporting differenceKeysSet and other hybrid functions
> working on different data structures.

Agreed. I don't think we should export differenceKeysSet either.

> But I do not like depending on rules alone either. If we promise that
> difference map (fromSet set) works without creating intermediate map,
> then it
> - works only for GHC
> - is nontrivial to use -- which functions do really fuse with fromSet?

I'm not promising anything performance-wise… it still produces the
same result without the rules, just that an intermediate IntMap will
be produced and consumed. With the rules, it's the same O(m+n) time
complexity, but with a much smaller constant.

How is this any more controversial than list fusion?

> My biggest problem is "Does difference with IntSet deserves to have
> a special function implementing it?" I do not believe so.

The point is that IntSet and IntMap are identical internally.

> For me, right now no functions working with different data structures
> are worth it. The API is complicated as it is and I do not feel adding
> cross-structure functions is a good thing to do. I am happy with
> being able to convert between the structures efficiently.

For the record, the only API extension I'm proposing is:

    fromSet :: (Key -> a) -> IntSet -> IntMap a

Nothing else changes, as far as users are concerned, except that

    intersection m (fromSet f s)    and    difference m (fromSet g s)

will perform equally well as intersection/difference between pairs of maps.

> Thanks for all the pathes! The patch 0006 is unfortunately missing the
> new module and also the changes to IntSet.

Those are in patch 0001.

Cheers,
/Liyang