Hedge-union

[puffnfresh]

If we assume coherent Ord instances for type-classes, we can provide a very fast algorithm for set union. See pages 19 and 20 of Implementing Sets Efficiently in a Functional Language.

Also implemented in the Haskell containers package.

[paf31]

Sounds good. I'll probably come back to this later, but I definitely think we should try to implement it. I assume it works for Map as well as Set.

[puffnfresh]

@paf31 yep, exactly. Would probably have been more sensible to link to the implementation for Map instead 🐴

[matthewleon]

Some interesting thoughts here: https://cs.stackexchange.com/questions/60973/is-hedge-union-always-as-fast-as-divide-and-conquer