On Sunday 01 Jan 2006 3:28 pm, Jean-Philippe Bernardy wrote:
Yes, union suffers from the same problem; both in Set and Map as well. 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).
Actually I was wondering whether or not the term "left-biasing" was particularly useful. It could be misleading for some functions. For example.. -- | /O(n*log n)/. Create a set from a list of elements. fromList :: Ord a => [a] -> Set a fromList xs = foldlStrict ins empty xs where ins t x = insert x t My interpretation of left biasing would be that if the input list contains multiple occurences of "equal" values then the first occurence is the one which is inserted in the Set and the rest are discarded. But AFAICS the this is not the case with the current Data.Set implementation (or with the clone I just produced). Both are right biased (at least according to my intuitive understanding of the term). I think to get left biasing we need to either.. Use foldr (instead of foldl) with insert as it is. or.. Use foldl but with a "right biased" insert function (I.E. One which prefers to retain existing elements). BTW, I think I would prefer the default behaviour of insert to be to retain existing elements because this allows the optimisation of not updating the data structure representing the set at all (which should help keep heap burn rate down). But I guess this is in effect assuming equality implies structural equality so others may not like it. Sigh.. <whine> I really wish this whole issue of how to properly deal with "things that are equal but may still be different somehow" would just go away :-) It's hard to be precise about what choice you've made, and whatever choice you do make usually seems arbitrary. Even when it doesn't make any semantic difference, the choice you make may well have an observable effect on space and time behavior. </whine> In the toy FPL I implemented a while ago I actually had combining comparison hardwired into the rts. This tested for structural equality and if two values (acyclic graphs) were equal it replaced the "new" one with an indirection node pointing to the "old" one (I could tell their relative age by the addresses). But I still can't quite decide if this was an elegant solution or an evil hack :-) Regards -- Adrian Hey