Expand the Data.Set API

Henning Thielemann lemming at henning-thielemann.de
Fri Mar 6 09:31:44 UTC 2015

On Fri, 6 Mar 2015, Joachim Breitner wrote:

>> 2. A way to insert an element if an == one is not already present
>> (insert replaces an existing one with a new one). Currently, as far as
>> I can tell, this can only be done using either
>>   if e `member` s then s else insert e s
>> which potentially descends the tree twice for no reason
>> or
>>   s `union` singleton e
>> which is documented as being O(|s|+1), although I wouldn't be shocked
>> if the documentation were too pessimistic in this case.
> I’m doubtful about that one.
> This is only needed if == is not „the right equality“, in which case a
> Set might be the wrong data type. Do we want to advocate that style?

We should use Map for element types that contain data which is irrelevant 
to the order.

> Since "s `union` singleton e" does the right thing with almost the right
> performance, maybe that’s sufficient?

I guess he prefered something like runtime log |s| + 1.

>> 3. A way to delete an element and simultaneously find out whether it
>> was in the set.
> +1, possibly with the type
>        a -> Set a -> Maybe (a, Set a)
> to get the remaining set as well.

This would be consistent to minView and maxView. Until there is such a 
delete function, splitMember might be used in a work-around.

More information about the Libraries mailing list