DData revision /equivalence vs equality
maeder at tzi.de
Wed Mar 17 13:02:33 EST 2004
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
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.
More information about the Libraries