Left-bias and non-structural equality.

[Jean-Philippe Bernardy]

On 1/2/06, Adrian Hey <ahey at iee.org> wrote:
> 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.