On 1/2/06, Adrian Hey
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).
There is a "definition" of left-bias here: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Set.html -- Note that the implementation is /left-biased/ -- the elements of a -- first argument are always perferred to the second, for example in -- 'union' or 'insert'. Of course, left-biasing can only be observed -- when equality is an equivalence relation instead of structural -- equality. ...which says nothing about biasing inside a list.
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...
The biggest problem with this is that Map.insert changes the value corresponding to the inserted key inside the map, and since it is observable even with structural equality, you can be certain that quite some people rely on that behaviour. Making Set do the opposite is rather counter-intuitive. In summary, left-biasing is important even in with well-behaved equality, in the case of Maps.
<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>
I really wish it too. BTW, the fact that Map and Sets had many problems with non-structural equality and biasing is quite revealing that this is not such a big problem in practice. (For the record I had to fix union and intersection in Set, and union*, intersection*, differenceWith* and insertWith* in Map) Non structural equality seemed not to have many proponents the last time I discussed it. (See http://www.haskell.org//pipermail/libraries/2004-March/001833.html and following messages) Yet, since haskell doesn't rule it out, I guess we have to provide a consitent behaviour, if only to minimize the user's suprise. On the other hand, I wish to deprecate all functions that implicitly promote non-structural Equality, in order not to lead the unsuspecting user to a dangerous path. Interestingly enough, this brings us back to the origin of this thread, namely insertWithKey. Changing it to follow the left-bias rule, it now doesn't depend on the keys present in the map; and hence becomes deprecated, for the reason David mentioned. Cheers, JP.