Would there be anything wrong with a Data.Set simply chopping off half its (balanced) tree and returning two approximately balanced partitions -- i.e. Data.Set.split without the pivot argument? Even though it can't quite be constant-time (still need rebalancing) it could still be cheaper than Data.Set.split, right? In the context of Set.hs, I'm thinking along the lines of something like the following:

cleave :: Set a -> (Set a, Set a)

cleave Tip = (Tip, Tip)

cleave (Bin _ x l r)

| size l > size r = (l, insertMin x r)

| otherwise = (insertMax x l, r)

For one thing, this seems like the proposed function would be useful for consuming a set in parallel, similar to Guy Steele's arguments in recent talks (see Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful). That is, one splits a tree and uses "par" to process the left and right half in parallel, enabling

Alternatively, it would be simple to provide a parallel version of mapMonotonic that does this internally, i.e.:

mapMonotonic _ Tip = Tip

mapMonotonic f (Bin sz x l r) =

Bin sz (f x) (mapMonotonic f l) (mapMonotonic f r)

Becomes something like:

parMapMonotonic f (Bin sz x l r) =

par left $ seq right $

Bin sz (f x) left right

where

left = mapMonotonic f l

right = mapMonotonic f r

Cheers,

-Ryan