[Haskell-cafe] Why isn't there a cheaper "split-in-two" operation for Data.Set?

[Bertram Felgenhauer]

Ryan Newton wrote:
> Would there be anything wrong with a Data.Set simply chopping off half its
> (balanced) tree and returning two approximately balanced partitions
...
> 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)

This function would expose some of the internal structure of Set - i.e.
there could be equal sets  s1 == s2  with  cleave s1 /= cleave s2.

Maybe a better idea than to expose such a function would be to split
Data.Set into Data.Set.Internal and Data.Set, where Data.Set.Internal
would export the actual Tip and Bin constructors. Then people who want
to break the abstraction, for example to experiment with parallel folds,
could do that easily.

regards,

Bertram