Expand the Data.Set API

Petr Pudlák petr.mvd at gmail.com
Tue Mar 17 20:57:29 UTC 2015

What would be use-cases for (2)? As Joachim pointed out, for any reasonable
data type inserting an equal element should have no difference.

For (3) I'd be in favor of

    alterF :: (Functor f, Ord a) => a -> (Bool -> f Bool) -> Set a -> f
(Set a)

(with any reasonable name) which'd allow to examine a set and possibly
modify it in one traversal. It should be smart enough not to modify the set
at all if the output of a given function is the same as its input. And it'd
also fit with lens. In particular, query+delete could be then expressed as

    memberDelete :: (Ord a) => a -> Set a -> (Bool, Set a)
    memberDelete k = alterF k (flip (,) False)


čt 5. 3. 2015 v 23:59 odesílatel David Feuer <david.feuer at gmail.com> napsal:

> There are a few rather conspicuously missing features:
> 1. A way to take the intersection of a list of sets. This shouldn't
> really be a big deal, and it already exists for unions, but the
> intersection version should probably sort the sets by size before
> folding, or otherwise try to do something smart.
> 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.
> 3. A way to delete an element and simultaneously find out whether it
> was in the set.
> David Feuer
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20150317/cbd402aa/attachment.html>

More information about the Libraries mailing list