These things are weight-balanced search trees augmented with semi-heaps. We have play, which joins together matching pieces. So that means if we can write a split and splitMaybe (like in the Data.Map internals), we should probably be able to get variations on union, intersection, and difference, along with something like the mergeA interface of Data.Map. I doubt we'll be able to come up with solid proofs of performance (those are quite subtle), but I would expect very good practical performance. Of course, this is all assuming that there isn't something major I'm missing; I haven't actually finished reading Hinze's paper.
These things are weight-balanced search trees augmented with semi-heaps. We have
play
, which joins together matching pieces. So that means if we can write asplit
andsplitMaybe
(like in theData.Map
internals), we should probably be able to get variations onunion
,intersection
, anddifference
, along with something like themergeA
interface ofData.Map
. I doubt we'll be able to come up with solid proofs of performance (those are quite subtle), but I would expect very good practical performance. Of course, this is all assuming that there isn't something major I'm missing; I haven't actually finished reading Hinze's paper.