DData revision /equivalence vs equality
ketil+haskell at ii.uib.no
Wed Mar 17 13:30:21 EST 2004
Christian Maeder <maeder at tzi.de> writes:
> 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
(I assume you mean "using an arbitrary equivalence relation", and not
that Eq's (==) shouldn't be an equivalence relation)
> 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.
> Furthermore, having only an equivalence implies that there is a
> stronger equality below that cannot be also an instance of Eq.
I've already said that I think Eq's (==) should be "structural
equality", which I thought meant that there shouldn't be any
My question is that since Set uses this equality, and MultiSet uses it
with a count, I don't see how this leaves any space for Bag? Unless,
that is, it uses an arbitrary equivalence relation, and bags an object
in its quotient group (which possibly is a Set with "real" equality).
Maybe I'm mistaken, maybe there's some other way Bag makes sense --
I've never really felt I needed Bag (nor MultiSet, although I've used
explicit FMs with counts).
> 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.
I added Int labels to somewhat complex structures in order to speed up
Eq (quite) a bit. Which means I accept the burden of keeping them
> 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.
So - how about "Bag" instead? :-)
If I haven't seen further, it is by standing in the footprints of giants
More information about the Libraries