[Haskell-cafe] Test on identity?
jo at durchholz.org
Fri Jul 10 06:49:06 UTC 2020
Am 09.07.20 um 20:26 schrieb Olaf Klinke:
> Joachim Durchholz wrote:
>> This "identity is equality under change" definition captures not
>> two objects at identical addresses, but also proxies, network
>> files, and whatever there is.
>> Step 3: Realize that if you have an immutable object, there is no
>> relevant difference between equality and identity anymore. (You can
>> various formal statements about this.)
> Is that what is called "extensional equality"? Values a,b :: A are
> extensionally equal if they behave the same in all contexts.
To fully treat this, you have to explore some pretty interesting waters.
First, "all contexts" can mean pretty different things.
E.g. in Haskell (without unsafe* and similar), everything is immutable,
so you have contexts that exist in languages with mutability but not in
Haskell, and you'd have to define what "all contexts" means for a
general term like "extensional equality".
Second, "behave the same" means that for all functions, the result it equal.
That's a recursive definition. You need fixed-point theory to turn that
statement into an actual definition.
And that's surprisingly tricky.
One fixed point is to say "the largest set of equal objects", which
means everything is equal to everything - fits the above definition
(applying any function to anything will trivially return results that
are equal under this definition), but is obviously not what we wanted.
Another one would be to have what we'd intuitively define as equality.
Say, in Haskell, the minimum set of equalities that makes different
constructor calls unequal. (Plus a handful of clerical definitions to
catch special cases like integers.)
Another one would be to have what we'd intuitively define as identity.
Plus various other fixed points.
For example, consider proxies - say, an object that talks to a remote
machine to produce its function results.
Now if you assume a proxy for integer values, is the proxy equal to an
arbitrary integer you may have locally?
Again, this depends on what fixed point you choose for your equality
definition. You can define that as an exception, you consider two
objects equal if their functions return equal results, except for those
that inspect the proxy-specific state; then proxy and local value are
equal. Or you don't make an exception, then the two are not equal.
From a mathematical standpoint, either fixed point will satisfy the
above recursive definition (definition template, if you will). From a
computing standpoint, you'll find that depending on context, you want
one or the other!
There are different types of proxy objects, and you can have different
kinds of equality depending on how you treat them.
That multitude of equality functions is pretty useless in a programming
context; nobody wants to mentally deal with a gazillion of subtly
So I belive what one should do in practice is to have converter
functions. E.g. one that turns an Int proxy into an Int, merely by
stripping the proxy-specific functions.
That keeps the special cases to the place where they belong - all those
types that have funky special kinds of equality.
Mutable data is another case of this. The equality of a mutable object
can be defined as identity, and a converter function returns an
immutable copy so that equality is what's usually considered "value
equality" (equals() in Java).
(Languages that do not cleanly separate mutable and immutable types will
still have to deal with two equalities, value equality and identity...
well, the above is type and language design theory, practical languages
are always a set of trade-offs, restricted by the limited knowledge and
experience of the language designer. I guess that's why we have so many
More information about the Haskell-Cafe