DData revision /equivalence vs equality

[Ketil Malde]

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
"deeper" equality.

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
unique. 

> 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? :-)

-kzm
-- 
If I haven't seen further, it is by standing in the footprints of giants