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).
Good! 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 Set.insert). How about an additional left-biased function of type "Set a -> a -> Set a"? What name for it? C.