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.