[Haskell-cafe] lookup tables & style guidelines

[Jan-Willem Maessen]

On Apr 24, 2008, at 11:33 AM, Adrian Hey wrote:

> Also, if you're likely to be using union/intersection a lot you should
> know that Data.Map/Set are very slow for this because they use the
> not efficient hedge algorithm :-)

OK, I'm going to bite here: What's the efficient algorithm for union  
on balanced trees, given that hedge union was chosen as being more  
efficient than naive alternatives (split and merge, repeated  
insertion)?  My going hypothesis has been "hedge union is an  
inefficient algorithm, except that it's better than all those other  
inefficient algorithms".

For IntSet/IntMap of course the split structure of the tree is fixed  
(we can think of these as being compressed versions of a complete  
binary tree) and union and intersection are quite efficient.

-Jan-Willem Maessen