[swift-evolution] Universal Equatability, Hashability, and Comparability

[Dave Abrahams]

on Tue Mar 08 2016, Joe Groff <jgroff-AT-apple.com> wrote:

> (starting a new thread by DaveA's request)
>
> There's a definition of equality that makes sense as a default for nearly every type in our system:
>
> - Basic types like IntNN, FloatNN, String, etc. have domain-defined
> equality,

But floats, as ever, are weird because their domain equality isn't an
equivalence relation.  Just one of the many little issues to be worked
out ;-).

> - Structs and tuples can be considered equal if their corresponding fields are equal,
> - Enums can be considered equal if they carry the same, equal payload,
> - Class references can be considered equal if they refer to the same instance,
> - Metatypes can be considered equal if they represent the same type, and
> - Existentials can be considered equal if they carry equal values of the same dynamic type.
>
> and similarly, reasonable hash code implementations could be
> synthesized by applying a standard hash combine operation over the
> components, and a default ordering could be assigned to values of
> every type. I think it's worth considering whether Equatable,
> Hashable, and/or Comparable, instead of being explicit protocols,
> should become universal behavior like 'print', with customization
> points to override the default behavior. 

Yes, please, let's consider that.  If the default behavior is going to
be a reasonable correct behavior 95% of the time (which IMO it is), this
will increase interoperability and decrease boilerplate.

I think because of the tight relationship between ==, copying, and
assignment, this discussion probably drags in the issues of:

* how to constrain generic parameters to having value semantics
* how to universally clone/assign mutable instances
* one more I thought of that slipped my mind; it'll come back to me.

> If Equatable and Hashable behavior were universal, that would solve
> many of the common problems people currently have trying to work with
> heterogeneous containers. In object-oriented frameworks, including
> Cocoa, Java, and .NET, it is common for the root (NS)Object class to
> provide default equality and hashing operations. There are of course
> some tradeoffs:
>
> - Universal behavior would require us to either generate code for
> '==', 'hashValue', and/or '<' for every type, or provide sufficient
> reflection info for a common runtime implementation to do it. The
> reflection-based approach may be reasonable for print(), since dumping
> reflection info only reduces the quality of the default logging
> behavior, but '==' and 'hashValue' are more essential to proper
> behavior, so relying on reflection might be too slow, and would be
> brittle when we introduce the ability to drop reflection info.
> - Type safety with '==' is important to prevent accidental '1 == "1"'
> type comparsions, and a fully generic 'func ==<T>(x: T, y: T) -> Bool'
> could potentially allow those sorts of mixed-type comparisons by
> accident. Language rules that constrained when generic parameters can
> be resolved to supertypes might help here.
> - Function types in Swift do not provide a ready equality
> operation. We could provide a default implementation that always
> returns 'false', perhaps.

Like Float equality, that's not an equivalence relation, only this
one is more serious, because for most Floats you can pretend it's an
equivalence relation unless you run into NaN.  I'm unsure what to do
about these two, but they bear careful consideration.

> - A Comparable ordering can be dreamt up for many types, but it's not
> always a stable ordering, 

What do you mean by stable ordering?

> or a desired one. 

That's true.  But what's important is that it's consistent with == and
allows lookup in a sorted container.  The core ordering operation should
not be spelled "<" though; we should use "<=>" for that so that types
can keep their domain-specific "<" if necessary.  Too bad the same trick
doesn't work for "==" :-).

> Many people have complained that 'nil < .Some(1)' works for optionals,
> for instance, ordering 'nil' below Some values. We could use pointer
> identity to order class instances and types, but this wouldn't be a
> stable ordering across process runs. 

Oh, that's what you mean by "stable."  So what?

> That might be good enough for ordered collections like search trees,
> but is weaker than what many people expect '<' to do.

MMmph.  I don't think it's unreasonable to say that if your expectations
don't match the defaults, you can define your own.

-- 
-Dave