[Haskell-cafe] strange stack overflow with Data.Map

Christian Maeder maeder at tzi.de
Mon Jan 2 13:55:11 EST 2006

Jean-Philippe Bernardy wrote:
> Yes, union suffers from the same problem; both in Set and Map as well.

In Data.Map "left-biasing" is correct wrt the values (but if "Map a ()" 
should correspond to "Set a" then the keys need also be considered.)

> The testing code can now detect problems of left-biasing in presence
> of non-structural equality. (That's what I wanted to implement before
> applying the fix).


The problem in Data.Set seems to be limited to insert, union, unions, 
intersection, fromList and fromAscList.

I find only union and intersection more problematic because biasing 
depends on the size and is thus hard to predict (if needed).

Currently, Set.fromList is right-biased (and the only function that uses 

How about an additional left-biased function of type "Set a -> a -> Set 
a"? What name for it?


More information about the Libraries mailing list