[E-Lang] Operators #2: Comparison

[Ralph Hartley]

Mark S. Miller wrote:

> 
>> Not defining it at all has its merits, but comparing the sets of keys isn't 
>> right anyway. The comparison of two maps should depend on the values, not 
>> just the keys. Here is a try at a definition: [...]
> 
> 
> Wow.  This is a very clever (and, I think, beautiful) extension of the idea 
> of lexicographic ordering.  I'm not going to think about this yet.

Fair enough. But I will continue on the principle that *I* might not 
have time latter, or might forget. The one operator I would really want 
to have is <=>. Immutable maps are almost never going to be ==, so a way 
to find out if two maps are "the same" would be nice to have.

The definition of <=>  ought to be something like "x<=>y iff ( a<=>b 
implies x[a]<=>y[b])" , that is, all their key/value pairs are <=>. 
That's the math definition for equality of maps.

The definition I gave in the previous message agreed with this one for 
keysets with total orders. For unordered keysets I think the previous 
definition was broken, it sometimes gave NaN when it should have been 0.

There are a lot more ways to order maps than there are equivalences, so 
 >, <, >=, and <= are a lot less clear cut. For instance you might also 
define x<y iff (x keyset() is a propoer subset of y keyset() and for any 
a in x keyset() x[a]<=>y[a]. That would be the submap relation, where x 
and y agree for any key they are defined on but x is defined on a proper 
subset of y's keys. This definition also agrees with <=> but not with 
the lexicographic order. For strings as maps from [0..N] to chars it 
would be the "prefix" relation.

There are enough definitions of < for maps that it would be odd to 
support one without supporting them all. It WOULD be nice if I could 
decide on one (in java you do this by overriding compare()). I don't 
know how often I would use it. Nowhere near as often as <=>, I think.

For <=> the only choice is if the keys and/or values need to be == or 
only <=>. That gives three meaningfull definitions of <=>:

Strict - Each key a of x must be == some key b of y and x[a]==y[b].
    rare.

Canonical - Each key a of x must be <=> some key b of y and x[a]==y[b].
    more common - given a key they always give the exact same value if 
the keys are <=>.

Loose -  Each key a of x must be <=> some key b of y and x[a]<=>y[b].
    common.

I think there is a equivalent issue defining <=> on sets. Do the 
elements need to be the same or just equivalent?

(I know I left out a posibility, but don't remember ever needing 
Co-Canonical).

Ralph Hartley