Re: Proposal: containers: add indexing operations for Set

On Tue, Jul 10, 2012 at 1:59 AM, Johan Tibell wrote:

On Thu, Jul 5, 2012 at 8:01 AM, Milan Straka 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)