Proposal: containers: add indexing operations for Set

[Evan Laforge]

On Tue, Jul 10, 2012 at 1:59 AM, Johan Tibell <johan.tibell at gmail.com> wrote:
> On Thu, Jul 5, 2012 at 8:01 AM, Milan Straka <fox at ucw.cz> wrote:
>> Any balanced tree can support indexing API, as long as every subtree
>> stores its size. That is obviously trivially true for size-balanced
>> trees, as the subtree sizes are used for balancing. If for example AVL
>> trees were used, sizes would have to be stored explicitly in every node
>> for indexing API to work fast.
>
> There might be some other benefits to adding the size as well. IIRC
> union is faster if the first set is smaller than the second set. If we
> can look up the sizes in O(1) time we can rearrange the arguments to
> make sure this is the case.

I've always wondered why Data.Map doesn't do this by default.  E.g. I have:

-- | Map.union says it's more efficient with @big `union` small@, so this one
-- flips the args to be more efficient.  It's still left-biased.
union2 :: (Ord k) => Map.Map k v -> Map.Map k v -> Map.Map k v
union2 m1 m2
    | Map.size m1 < Map.size m2 = m2 `right` m1
    | otherwise = m1 `Map.union` m2
    where right = Map.unionWith (\_ a -> a)