Proposal: IntMap.differenceKeysSet for removing an IntSet of keys

[wren ng thornton]

On 6/9/11 10:17 PM, Liyang HU wrote:
> On 10 June 2011 10:09, Felipe Almeida Lessa<felipe.lessa at gmail.com>  wrote:
>> If we had something like fromIntSet :: IntSet ->  IntMap ()
>> then at least we could have a RULE to convert "difference m
>> (fromIntSet s)" to "differenceIntSet m s".  Then we could just hide
>> differenceIntSet and the name wouldn't matter.  Perhaps this
>> "fromIntSet" function should be proposed as well?
>
> Sure, that sounds quite reasonable. Have done that as patch 0005 on
> the ticket. I've generalised it a bit to:
>
>      fromSet :: (Key ->  a) ->  IntSet ->  IntMap a
>
> Which version does everyone prefer? differenceKeysSet m s, or
> difference m (fromSet f s) ?

One downside of using fromSet is that it clones the IntSet before 
differencing. Since IntSet is spine-strict, this can be quite expensive 
since it'll clone the whole thing no matter how much is used.

I like the idea of having a fromSet function with the (Key->a) argument. 
But there's also room for differenceKeysSet for efficiency reasons. 
Perhaps you can come up with some fusion rules to get rid of the 
overhead of difference m (fromSet f s)?

Certainly there should be the rule:

     map f . fromSet g = fromSet (f . g)

and similar for the other mapping functions.

-- 
Live well,
~wren