Proposal: containers: add indexing operations for Set
qdunkan at gmail.com
Tue Jul 10 02:46:34 CEST 2012
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)
More information about the Libraries