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