DData revision /equivalence vs equality

[Christian Maeder]

Ketil Malde wrote:
> I think you're saying we might need a bag to hold items where we want
> to group things according to (equivalence on) some arbitrary key?

I think, using an equivalence for the Eq class is not a good idea
in general and particularly not for the Set, (keys of a) Map and Bag 
data types.

An equivalence introduces a quotient, where a representative of an
equivalence class is not fixed.

So using an equivalence bears some risk as the following property does 
not hold: forall f . a == b => f(a) == f(b)  (e.g. for f = show)

Furthermore, having only an equivalence implies that there is a stronger 
equality below that cannot be also an instance of Eq. (A solution might 
be to add a further "Equiv" and "OrdForEquiv" class or to always pass in 
such functions as additional argument as you suggested.)

Daan's Set implementation explicitely explains what happens, if your Eq 
(and matching Ord) instance is only an equivalence, by saying it is 
"left-biased". This feature is not a particular Set property (unions are 
symmetric!), but only of a specific Set implementation, that you may 
exploit (or not).

In fact, I also use equalities that ignore some debugging information 
like positions, but as long these positions are only shown, this seems 
to be ok.

Another example, where an equivalence-order argument seems to make 
sense, is for a map implementation based on "set of pairs", where the 
second component of each pair is ignored for the order. But for such an 
implementation I find the name "set" wrongly chosen.

Christian