A shift in perspective that I enjoy is that it’s not that the world is as it is and equality is broken, but instead that picking an equality tells us what the world is. Your choice of equality nails down the finest distinction you’re allowed to make.
So, practically speaking, tossing away access to reference equality is a necessary part of abstracting away our notion of PLs operating on a computer atop a pool of memory. If we retain it, we can make distinctions which violate that model of the world.
Often the trouble is that IEEE floats are designed such that they cannot be abstracted from their memory representation. On the one hand, NaN != NaN. On the other hand, Floats are supposed to represent Real numbers when you throw away the memory model, but Real numbers don’t support computable equality at all!
So IEEE floating point is pretty incompatible with a language model that tries to hide memory representations. But it’s critical for fast math. Now, the correctness of your language has to do not just with equality but how it allows these two incompatible worlds to live together as harmoniously as possible.
Wow, this reads as a great list of “reasons why I’m glad I don’t use language X”.
But as I hinted above, there are certainly cases where structural equality does not make sense. One example is with languages which support mutation of variables, which is most of them.
I don’t think this is correct; it’s mutation of data structures which makes structural equality problematic. That’s different from mutation of variables, which doesn’t interfere with equality at all.
One of the first lessons we learn when becoming a programmer is that there are two different concepts which we both call “equals.” One is assignment, the other is testing equality.
Also there are languages like Prolog and Erlang in which = simultaneously binds and asserts equality!
To throw in yet another perspective, Baker’s Equal Rights for Functional Objects proposes a refinement of these equality relations for Lisps. Based on this paper, and inheriting E’s operators, I designed an equality operator and a multi-directional comparison operator for Monte. Here’s how our design decisions stack up against your recommendations.
Monte has one equality operator, ==. It is an equivalence relation. There is also a multi-directional comparison operator, using the syntax <, <=, >, >=, <=> which perform the familiar quartet of less-than, less-than-or-equal, greater-than, greater-than-or-equal, and also as-same-as; this is like a generalized signed comparison operator.
Equality comparisons are always available. For mutable objects, equality is by identity, as expected; for immutable objects, the programmer can choose, by explicitly choosing whether the object is shared or created many times. For floating-point types, equality obeys the laws. As a consequence, NaN == NaN is true; NaN <=> NaN is false.
Edit: Crucially, in the above paragraph, I should have pointed out that equality cares about representation, because computer programming incorporates details and nuances of representations. 4 == 4.0 is false; 4 <=> 4.0 is true. As a result, integers and floating-point numbers are rarely confused for each other. Similarly, mutable collections are not equal to their immutable variants, nor are unordered collections equal before sorting. Our generalized comparison acts as a comfort operator; [1,2].asSet() == [2,1].asSet() is false; [1,2].asSet() <=> [2,1].asSet() is true.
Structural comparison is supported for immutable objects. An object must explicitly opt-in with annotations for being transitively immutable, and it must implement a method which exports its state, “uncalling” the operation which originally built the object. Correctness is enforced by construction; the annotations can prove facts about annotated objects. Note that Monte syntax annotates every local name with def or var to indicate whether it is mutable; without this, as you say, “I don’t know of any language which has mutable by default variables which handles structural comparisons in a non-confusing way.”
Have you read Bill Kent’s essay on this? I think you’d really like it.
The choice of syntax is partially due to heritage: F# is based on ML, which is based on math, and JavaScript syntax is based on Java -> C -> Algol -> FORTRAN.
This is incorrect. Algol does not derive from FORTRAN. Additionally, neither Algol nor FORTRAN follow C’s style of equality and assignment. Algal uses := for assignment and = for equality, while FORTRAN uses = and .EQ.. C actually gets its style from BCPL, which got its own style from a deliberate simplification of CPL. I wrote a bit more about this here.
Edit: This chart indicates otherwise? It’s a minor point in the article, but I’m interested in the truth. Why do you say “Algol does not derive from FORTRAN?”
Edit: This chart indicates otherwise? It’s a minor point in the article, but I’m interested in the truth. Why do you say “Algol does not derive from FORTRAN?”
Oop, I could be completely wrong here! I’d have to go and review all my notes on that. This is all stuff I’m now pulling out of my butt:
In Favor:
John Backus worked on both
Everybody knew about Fortran at the time
Against:
None of the Algol material I could dig up mentioned FORTRAN
I haven’t found any “language cognates” in Algol that could have come from FORTRAN
I think ALGOL derived from FORTRAN about as much as any other language [edit: ..that existed at the time]. It would depend if we’re talking ALGOL 60 specifically, or 58 (arguably closer to FORTRAN), or the whole “family”.
I have thought a while about this, and will (eventually) implement this scheme for equality, mostly inspired by Scheme:
identical? for reference equality (and possibly also primitives),
equal? for structural equality (for types that support it),
equivalent? as a more general trait which also requires a context within which you are comparing, like hashing or floats within a given epsilon. (The above two are special cases of this.)
Hopefully it will be intuitive and obvious, with no gotchas.
(Minor note: F# will let you use mutable as an adjective for Offspring and jane in case you didn’t want to switch to C# for that example).
You want the developer to see === and think “reference equality,” not “more equals signs is better.”
No, you don’t want this. You want === to stand for identity, such that it can have a definition that works consistently across all types, reference and value. Both sane handling of floating point values as well as the ability to freely change types from reference types to value types (and back) depend on it.
Some minor nipicks:
programming languages should make it simple to create types where equality comparison is disabled …
It’s probably easier to pick sane defaults and stop the runtime from implementing random methods “for convenience”.
… they should use this feature in their standard library where needed, such as on floating point types
Not really seeing the reason for this.
Overall a nice article with an entertaining description of an interesting problem!
Your “fixing Haskell” article does not fix anything. The actual fix is to make Float and Double not implement the Eq type class, period.
One thing Standard ML does right is using different functions for comparing eqtypes (e.g. int, bool, tuples of eqtypes, etc.) and floating points (i.e. real). When you use the former, you can expect all the usual mathematical properties of equality to hold. When you use the latter, you know what you are getting into.
Your “fixing Haskell” article does not fix anything.
I think the article does a good job to explain why you’re wrong.
The actual fix is to make Float and Double not implement the Eq type class, period.
Why not just drop floating point values altogether, “language design is hard, let’s go shopping”-style?
When you use the former, you can expect all the usual mathematical properties of equality to hold. When you use the latter, you know what you are getting into.
That’s exactly what happens – you specify the properties you need:
If you require identity and the guarantees it provides, e. g. for keys of maps, simply demand that the type implements it.
class HashMap[K: Identity + Hash, V] { ...}
// Double implements Identity
let map = HashMap[Double, String]()
map.put(Double.NaN, "found me")
// Lookup works, even for NaN:
assert(map.get(Double.NaN) == Some("found me"))
I think the article does a good job to explain why you’re wrong.
Your article literally asks for the Eq class to expose two distinct equality testing functions. What can be more broken than that? I am having a lot of trouble imagining it.
If you require identity and the guarantees it provides, e. g. for keys of maps, simply demand that the type implements it.
Using a type class to constrain the key type of a map is in itself broken. Suppose for the sake of the argument that you have a type that can be totally ordered in two different ways, both useful. (I could have also said “hashed in two different ways, both useful”, but that is less realistic.) It is perfectly reasonable to want to construct two distinct ordered map types, one for each total order. With a type class constraint on the map’s key type, you cannot this, because type classes must have canonical instances. (Or you could destroy canonicity at your own peril, as Scala does.)
The correct solution is to do exactly what ML does:
signature ORDERED =
sig
type key
val compare : key * key -> order
end
functor TreeMap (Key : ORDERED) :> MAP
where type key = Key.key =
struct
(* ... *)
end
The map abstraction is not parameterized just by the key type but rather by the whole ordered type structure, of which the naked key type is but one component. This is exactly how things should be.
Applying this lesson to your hash map example, we have
signature HASHABLE =
sig
type key
val equal : key * key -> bool (* not necessarily ML's built-in equality! *)
val hash : key -> int
end
functor HashMap (Key : HASHABLE) :> MAP
where type key = Key.key =
struct
(* ... *)
end
Your article literally asks for the Eq class to expose two distinct equality testing functions. What can be more broken than that? I am having a lot of trouble imagining it.
As mentioned in the article, you could also introduce a new trait for it.
I think the SML approach is well-known to those who thought about non-canonical instances in Haskell and Scala.
(Rust seems to enforce uniqueness of instances, so that’s another interesting data point.)
The core question is whether the price one would pay for this feature is worth the cost – I wouldn’t say so; that’s why I’m approaching this by splitting things into better-defined typeclasses to relieve the pressure on needing multiple instances of the same typeclass even for trivial things.
For instance for numbers, you don’t need to engage in crazy contortions anymore (like in Haskell) to swap behavior between floats that compare nicely in the domain (NaN != NaN) and floats that can be put and retrieved from data structures.
I think the SML approach is well-known to those who thought about non-canonical instances in Haskell and Scala.
Haskell’s designers know very well the importance of having canonical instances for type classes to work correctly, as well as the inherent conflict between canonicity of instances and modularity.
And yet Haskell has the -XIncoherentInstances extension.
The core question is whether the price one would pay for this feature is worth the cost
The payoff is huge. The type checker will stop you immediately if you conflate two structures constructed from different instances on the same type. For example, suppose you have two ordered sets and want to merge them. The obvious O(n) algorithm only works correctly if both ordered sets are ordered using the same total order on the element type. But Scala will silently allow you to use the wrong order on one of the sets, due to the way implicits work when used as type class instances.
that’s why I’m approaching this by splitting things into better-defined typeclasses
The problem with your “better-defined” type classes is that many of them will support similar operations. In fact, similar enough that you will want to define the same algorithms on them. But, since your “better-defined” type classes are not literally the same as each other, as far as the type checker cares, you still need to reimplement the same algorithms over and over, which defeats the point to using type classes in the first place.
Another way to work around this issue is to use newtype wrappers to mediate the conversion between instances. But that is disgusting in its own way. For example, before Applicative became a superclass of Monad, Haskell used to have a WrappedMonad newtype as a contrived way to get an Applicative instance from a Monad one.
And yet Haskell has the -XIncoherentInstances extension.
… which you don’t even need. GHC allows defining incoherent instances without it.
For example, suppose you have two ordered sets and want to merge them. The obvious O(n) algorithm only works correctly if both ordered sets are ordered using the same total order on the element type.
Scala supports this with path-dependent types, but the syntactical and mental overhead never felt worth it.
Anyway, I wasn’t aware that SML supported applicative functors (which I think are a requirement to make this work) – when did this change?
A conservative approximation could also be done at the value-level – if typeclass instances were first-class values (but I don’t think that’s worth it).
But, since your “better-defined” type classes are not literally the same as each other, as far as the type checker cares, you still need to reimplement the same algorithms over and over, which defeats the point to using type classes in the first place.
Agreed. I just think that’s vastly preferable to people using one (or a few) typeclasses as random dumping grounds until these typeclass has no laws left (see Eq, Ord in Haskell).
Another way to work around this issue is to use newtype wrappers to mediate the conversion between instances. But that is disgusting in its own way.
Ick, that’s way more ugly than the “recommended” approach in Haskell; that is wrapping the data types and reimplementing the typeclass instance (e. g. TotalDouble wrapping Double to implement Eq and Ord differently from Float).
Scala supports this with path-dependent types, but the syntactical and mental overhead never felt worth it.
Scala’s troubles arise from the desire to make everything first-class. “Objects with type members are basically first class modules, right?” It sounds good until you realize it does not interact well with type inference. Knowing what to make second-class is an art.
Anyway, I wasn’t aware that SML supported applicative functors (which I think are a requirement to make this work) – when did this change?
Standard ML does not have applicative functors. Making applicative functors work correctly requires a notion of “pure functor body”, which no ML dialect has as far as I can tell. (OCaml’s applicative functors create broken abstract data types when their bodies are impure.)
In any case, using applicative functors is not the only way to make this work. Another way is to arrange your code so that you do not need to apply the same functor to the same module twice. Unfortunately, this requires a way of thinking that is not very compatible with how either object-oriented or functional programmers design their libraries.
I have two cardinal rules for library design.
Do not expose higher-order interfaces when first-order ones will do.
As a counterexample, consider the Haskell API for maps:
empty :: Map k a
lookup :: Ord k => k -> Map k a -> Maybe a
insert :: Ord k => k -> a -> Map k a -> Map k a
delete :: Ord k => k -> Map k a -> Map k a
{- more functions -}
This is higher-order than necessary. Essentially, lookup, insert and delete are functors that are applied to an Ord structure every time they are called. Only from the canonicity of Ord instances can you argue that the effect of these multiple applications is equivalent to a single application of a functor that produces a map type whose key type is monomorphic.
Have you gained anything? Strictly speaking, yes. You have gained the ability to tell your users that the implementation code for inserting into a Map Int a and into a Map String a is really the same.
Is this something the user cares about? IMO, no. If I am working with maps with 64-bit integer keys, I do not care whether the underlying implementation is a generic red-black tree (which would work just as well with any other key type) or a radix tree (which requires lexicographically ordered bit vectors as keys).
The right interface, as previously stated, has an abstract but monomorphic key type:
type Key
type Map a
empty :: Map a
lookup :: Key -> Map a -> Maybe a
insert :: Key -> a -> Map a -> Map a
delete :: Key -> Map a -> Map a
Do not enforce two unrelated sets of invariants in the same module.
According to most standard libraries, the obvious way to implement ordered maps is something like:
functor TreeMap (Key : ORDERED) :> MAP
where type key = Key.key =
struct
(* hard-coded implementation of red-black trees or what have you *)
end
Never mind that you have to reimplement red-black trees from scratch if you want to implement sets as well. This design is bad for a more fundamental reason: you cannot debug the red-black tree implementation without tearing down the map abstraction!
The problem here is that TreeMap enforces two unrelated sets of invariants:
Trees are correctly balanced.
The in-order traversal of a tree produces a strictly ascending sequence of keys.
The first invariant actually does not depend on the key type, so it can be factored out into a separate module:
signature SEARCH_TREE =
sig
type 'a tree
(* Manipulate self-balancing search trees using zippers.
* The user must know how to look for a given element. *)
end
structure RedBlackTree :> SEARCH_TREE = (* ... *)
Once we have a working search tree implementation, we can finally implement maps:
functor TreeMap
( structure Key : ORDERED
structure Tree : SEARCH_TREE ) :> MAP where type key = Key.key =
struct
type key = Key.key
type 'a map = (key * 'a) Tree.tree
(* ... *)
end
The same lesson can be applied to hash maps:
signature TABLE =
sig
type 'a table
(* Operations on a fixed size table, including collision resolution.
* The user must know where to start looking for a given element. *)
end
structure LinearProbing :> TABLE = (* ... *)
structure QuadraticProbing :> TABLE = (* ... *)
functor HashMap
( structure Key : HASHABLE
structure Table : TABLE ) :> MUTABLE_MAP where type key = Key.key =
struct
type key = Key.key
type 'a map = (key * 'a ref) Table.table ref
(* ... *)
end
I’m getting a bit confused by they way you contrast ‘equality’ and ‘identity’. To me they mean the same thing, and your article is suggesting === for equality and == for equivalence. This feels in line with your point, because there are many different ways to define equivalence for any particular type.
I really like your series; I’ll update my post to have a reference to it.
It’s not clear to me that having === mean two different things for value type and reference types is an improvement (it’s also not clear to me that it isn’t an improvement, either; I’m not sure). It would be interesting to study this in a human factors evaluation of a programming language (like the Quorum language) to see what makes the most intuitive sense to developers. Certainly what you propose is at least lawful which is an improvement over the current state of things!
My reasoning for not wanting equality on floats is the same as SML’s for not having it, which I cite in the article. A reasonable comparison on a float requires an epsilon value, which doesn’t fit into the == operator usage.
It’s not clear to me that having === mean two different things for value type and reference types is an improvement
My argument is that it stands for the exact same thing in both reference and value types: “is this thing here identical to that thing over there”?. Sure, we know this as “reference equality” on reference types, but it’s just as crucial on value types. Some may call it “ability to find your floats in your collections again equality”.
Here is another article on how == vs. === relates to the various orderings the IEEE754 spec defines: Comparing & Sorting
A reasonable comparison on a float requires an epsilon value, which doesn’t fit into the == operator usage.
I disagree on that. 80% of the comparisons on floating point values are with “magic values” like 0.0, 1.0, NaN etc. that were not exposed to any kind of arithmetic computation before, and therefore can not foil the comparison.
FYI, the Implementation in Dora post seems to be empty.
Yes, I left out the link, because I haven’t written it yet. :-)
Here is a unit test, that might demonstrate the semantics.
I would argue that if you have a comparison which is only good for “magic values” then what you really have is a bunch of useful functions: isNaN, isZero, etc. I will note that == NaN is going to fail anyway!
Bit of a pet peeve for me that people get this wrong. I’ve even seen people call it “exponential notation”. Probably the “E” primes people to think “exponential”.
I think I’m quite happy with the approach Julia takes, and looking at the issue tracker an awful lot of work went into it.
== means structural equality (and will promote types to be comparable if necessary and possible) and does three-value logic with missing.
=== means identical (no program could distinguish these values).
isequal is similar to == but doesn’t do three-value logic with missing; NaN is equal to itself; and -0 and 0 are not equal. This is used for dictionaries because Julia’s hash implementation returns the same hash for numeric types of the same value, even if their types are different!
isapprox and ≈ for inexact equality with three-value logic.
All except === are recursively defined by default for collections and immutable types so you get structural equality. If you’re defining something weird then you have the expressivity to describe what equality means for that type.
All of the above are total functions (i.e. should never throw errors), so comparing incomparables just gives you false. If you want a partial function (throws an error for incomparable types, like some MLs), then you can define a dumb one with strict_equal(a, b) = (typeof(a) == typeof(b) || error()) && a == b or a more sophisticated one with the promotion machinery and by introducing an incomparable or inexact trait for things like floats.
Equality is not hard. What is actually hard is convincing PL designers not to use the word “equality” for something that does not behave like mathematical equality. This is a sociological problem, not a technical one.
A shift in perspective that I enjoy is that it’s not that the world is as it is and equality is broken, but instead that picking an equality tells us what the world is. Your choice of equality nails down the finest distinction you’re allowed to make.
So, practically speaking, tossing away access to reference equality is a necessary part of abstracting away our notion of PLs operating on a computer atop a pool of memory. If we retain it, we can make distinctions which violate that model of the world.
Often the trouble is that IEEE floats are designed such that they cannot be abstracted from their memory representation. On the one hand, NaN != NaN. On the other hand, Floats are supposed to represent Real numbers when you throw away the memory model, but Real numbers don’t support computable equality at all!
So IEEE floating point is pretty incompatible with a language model that tries to hide memory representations. But it’s critical for fast math. Now, the correctness of your language has to do not just with equality but how it allows these two incompatible worlds to live together as harmoniously as possible.
I love this way of putting it!
Wow, this reads as a great list of “reasons why I’m glad I don’t use language X”.
I don’t think this is correct; it’s mutation of data structures which makes structural equality problematic. That’s different from mutation of variables, which doesn’t interfere with equality at all.
Also there are languages like Prolog and Erlang in which = simultaneously binds and asserts equality!
Your point regarding data structures vs. variables is subtle but fair.
Will have to look into Prolog and Erlang; I don’t know either language well.
Thanks for posting; I really enjoyed the article.
To throw in yet another perspective, Baker’s Equal Rights for Functional Objects proposes a refinement of these equality relations for Lisps. Based on this paper, and inheriting E’s operators, I designed an equality operator and a multi-directional comparison operator for Monte. Here’s how our design decisions stack up against your recommendations.
Monte has one equality operator,
==. It is an equivalence relation. There is also a multi-directional comparison operator, using the syntax<,<=,>,>=,<=>which perform the familiar quartet of less-than, less-than-or-equal, greater-than, greater-than-or-equal, and also as-same-as; this is like a generalized signed comparison operator.Equality comparisons are always available. For mutable objects, equality is by identity, as expected; for immutable objects, the programmer can choose, by explicitly choosing whether the object is shared or created many times. For floating-point types, equality obeys the laws. As a consequence,
NaN == NaNis true;NaN <=> NaNis false.Edit: Crucially, in the above paragraph, I should have pointed out that equality cares about representation, because computer programming incorporates details and nuances of representations.
4 == 4.0is false;4 <=> 4.0is true. As a result, integers and floating-point numbers are rarely confused for each other. Similarly, mutable collections are not equal to their immutable variants, nor are unordered collections equal before sorting. Our generalized comparison acts as a comfort operator;[1,2].asSet() == [2,1].asSet()is false;[1,2].asSet() <=> [2,1].asSet()is true.Structural comparison is supported for immutable objects. An object must explicitly opt-in with annotations for being transitively immutable, and it must implement a method which exports its state, “uncalling” the operation which originally built the object. Correctness is enforced by construction; the annotations can prove facts about annotated objects. Note that Monte syntax annotates every local name with
deforvarto indicate whether it is mutable; without this, as you say, “I don’t know of any language which has mutable by default variables which handles structural comparisons in a non-confusing way.”Have you read Bill Kent’s essay on this? I think you’d really like it.
This is incorrect. Algol does not derive from FORTRAN. Additionally, neither Algol nor FORTRAN follow C’s style of equality and assignment. Algal uses
:=for assignment and=for equality, while FORTRAN uses=and.EQ.. C actually gets its style from BCPL, which got its own style from a deliberate simplification of CPL. I wrote a bit more about this here.Also, ML has mutable assignments with
:=.Thanks for the correction; I’ll update the post.
No, I hadn’t seen that essay; thanks!
Edit: This chart indicates otherwise? It’s a minor point in the article, but I’m interested in the truth. Why do you say “Algol does not derive from FORTRAN?”
Oop, I could be completely wrong here! I’d have to go and review all my notes on that. This is all stuff I’m now pulling out of my butt:
In Favor:
Against:
I suspect the truth is somewhere in between. Lots of languages influenced Algol, but a straight line from FORTRAN may be overstating the facts.
Fortran originally just had .EQ., .NE., .GT., etc. Support for = came later.
Fortran and Algol coevolved to some degree, so they cannot be placed in a tree.
I think ALGOL derived from FORTRAN about as much as any other language [edit: ..that existed at the time]. It would depend if we’re talking ALGOL 60 specifically, or 58 (arguably closer to FORTRAN), or the whole “family”.
The last page of The Early Development of Programming Languages sums it up really well.
Also ALGOL is based heavily on mathematics.
I think we need to give you the “Bill Kent Stan Account” hat. Not that I’m complaining; I’ve liked what I’ve read.
This is the nicest thing anyone’s ever said to me
Hey, at least it’s a Twitter display name!
http://www.nhplace.com/kent/PS/EQUAL.html is another Common Lisp focused discussion of this.
This was a pleasant read!
I have thought a while about this, and will (eventually) implement this scheme for equality, mostly inspired by Scheme:
identical?for reference equality (and possibly also primitives),equal?for structural equality (for types that support it),equivalent?as a more general trait which also requires a context within which you are comparing, like hashing or floats within a given epsilon. (The above two are special cases of this.)Hopefully it will be intuitive and obvious, with no gotchas.
(Minor note: F# will let you use
mutableas an adjective forOffspringandjanein case you didn’t want to switch to C# for that example).This reminds me of Ruby & Objective-C cocktail.
I solved this problem a while ago and wrote some notes on it.
“Equality & Identity”: Overview, Problems, Solution, Fixing Haskell, Implementation in Dora
One mistake in the article though:
No, you don’t want this. You want
===to stand for identity, such that it can have a definition that works consistently across all types, reference and value. Both sane handling of floating point values as well as the ability to freely change types from reference types to value types (and back) depend on it.Some minor nipicks:
It’s probably easier to pick sane defaults and stop the runtime from implementing random methods “for convenience”.
Not really seeing the reason for this.
Overall a nice article with an entertaining description of an interesting problem!
Your “fixing Haskell” article does not fix anything. The actual fix is to make
FloatandDoublenot implement theEqtype class, period.One thing Standard ML does right is using different functions for comparing eqtypes (e.g.
int,bool, tuples of eqtypes, etc.) and floating points (i.e.real). When you use the former, you can expect all the usual mathematical properties of equality to hold. When you use the latter, you know what you are getting into.I think the article does a good job to explain why you’re wrong.
Why not just drop floating point values altogether, “language design is hard, let’s go shopping”-style?
That’s exactly what happens – you specify the properties you need:
If you require identity and the guarantees it provides, e. g. for keys of maps, simply demand that the type implements it.
Your article literally asks for the
Eqclass to expose two distinct equality testing functions. What can be more broken than that? I am having a lot of trouble imagining it.Using a type class to constrain the key type of a map is in itself broken. Suppose for the sake of the argument that you have a type that can be totally ordered in two different ways, both useful. (I could have also said “hashed in two different ways, both useful”, but that is less realistic.) It is perfectly reasonable to want to construct two distinct ordered map types, one for each total order. With a type class constraint on the map’s key type, you cannot this, because type classes must have canonical instances. (Or you could destroy canonicity at your own peril, as Scala does.)
The correct solution is to do exactly what ML does:
The map abstraction is not parameterized just by the key type but rather by the whole ordered type structure, of which the naked key type is but one component. This is exactly how things should be.
Applying this lesson to your hash map example, we have
EDIT: Fixed formatting.
As mentioned in the article, you could also introduce a new trait for it.
I think the SML approach is well-known to those who thought about non-canonical instances in Haskell and Scala. (Rust seems to enforce uniqueness of instances, so that’s another interesting data point.)
The core question is whether the price one would pay for this feature is worth the cost – I wouldn’t say so; that’s why I’m approaching this by splitting things into better-defined typeclasses to relieve the pressure on needing multiple instances of the same typeclass even for trivial things.
For instance for numbers, you don’t need to engage in crazy contortions anymore (like in Haskell) to swap behavior between floats that compare nicely in the domain (NaN != NaN) and floats that can be put and retrieved from data structures.
Haskell’s designers know very well the importance of having canonical instances for type classes to work correctly, as well as the inherent conflict between canonicity of instances and modularity.
And yet Haskell has the
-XIncoherentInstancesextension.The payoff is huge. The type checker will stop you immediately if you conflate two structures constructed from different instances on the same type. For example, suppose you have two ordered sets and want to merge them. The obvious O(n) algorithm only works correctly if both ordered sets are ordered using the same total order on the element type. But Scala will silently allow you to use the wrong order on one of the sets, due to the way implicits work when used as type class instances.
The problem with your “better-defined” type classes is that many of them will support similar operations. In fact, similar enough that you will want to define the same algorithms on them. But, since your “better-defined” type classes are not literally the same as each other, as far as the type checker cares, you still need to reimplement the same algorithms over and over, which defeats the point to using type classes in the first place.
Another way to work around this issue is to use newtype wrappers to mediate the conversion between instances. But that is disgusting in its own way. For example, before
Applicativebecame a superclass ofMonad, Haskell used to have aWrappedMonadnewtype as a contrived way to get anApplicativeinstance from aMonadone.This comment was pitched at exactly my level of type knowledge - thanks!
… which you don’t even need. GHC allows defining incoherent instances without it.
Scala supports this with path-dependent types, but the syntactical and mental overhead never felt worth it.
Anyway, I wasn’t aware that SML supported applicative functors (which I think are a requirement to make this work) – when did this change?
A conservative approximation could also be done at the value-level – if typeclass instances were first-class values (but I don’t think that’s worth it).
Agreed. I just think that’s vastly preferable to people using one (or a few) typeclasses as random dumping grounds until these typeclass has no laws left (see
Eq,Ordin Haskell).Ick, that’s way more ugly than the “recommended” approach in Haskell; that is wrapping the data types and reimplementing the typeclass instance (e. g.
TotalDoublewrappingDoubleto implementEqandOrddifferently fromFloat).Scala’s troubles arise from the desire to make everything first-class. “Objects with type members are basically first class modules, right?” It sounds good until you realize it does not interact well with type inference. Knowing what to make second-class is an art.
Standard ML does not have applicative functors. Making applicative functors work correctly requires a notion of “pure functor body”, which no ML dialect has as far as I can tell. (OCaml’s applicative functors create broken abstract data types when their bodies are impure.)
In any case, using applicative functors is not the only way to make this work. Another way is to arrange your code so that you do not need to apply the same functor to the same module twice. Unfortunately, this requires a way of thinking that is not very compatible with how either object-oriented or functional programmers design their libraries.
I have two cardinal rules for library design.
Do not expose higher-order interfaces when first-order ones will do.
As a counterexample, consider the Haskell API for maps:
This is higher-order than necessary. Essentially,
lookup,insertanddeleteare functors that are applied to anOrdstructure every time they are called. Only from the canonicity ofOrdinstances can you argue that the effect of these multiple applications is equivalent to a single application of a functor that produces a map type whose key type is monomorphic.Have you gained anything? Strictly speaking, yes. You have gained the ability to tell your users that the implementation code for inserting into a
Map Int aand into aMap String ais really the same.Is this something the user cares about? IMO, no. If I am working with maps with 64-bit integer keys, I do not care whether the underlying implementation is a generic red-black tree (which would work just as well with any other key type) or a radix tree (which requires lexicographically ordered bit vectors as keys).
The right interface, as previously stated, has an abstract but monomorphic key type:
Do not enforce two unrelated sets of invariants in the same module.
According to most standard libraries, the obvious way to implement ordered maps is something like:
Never mind that you have to reimplement red-black trees from scratch if you want to implement sets as well. This design is bad for a more fundamental reason: you cannot debug the red-black tree implementation without tearing down the map abstraction!
The problem here is that
TreeMapenforces two unrelated sets of invariants:The first invariant actually does not depend on the key type, so it can be factored out into a separate module:
Once we have a working search tree implementation, we can finally implement maps:
The same lesson can be applied to hash maps:
I’m getting a bit confused by they way you contrast ‘equality’ and ‘identity’. To me they mean the same thing, and your article is suggesting
===for equality and==for equivalence. This feels in line with your point, because there are many different ways to define equivalence for any particular type.Yes – the naming is largely driven by the desire to not have two things (where differences are important) behind two names that are quite similar.
I really like your series; I’ll update my post to have a reference to it.
It’s not clear to me that having
===mean two different things for value type and reference types is an improvement (it’s also not clear to me that it isn’t an improvement, either; I’m not sure). It would be interesting to study this in a human factors evaluation of a programming language (like the Quorum language) to see what makes the most intuitive sense to developers. Certainly what you propose is at least lawful which is an improvement over the current state of things!My reasoning for not wanting equality on floats is the same as SML’s for not having it, which I cite in the article. A reasonable comparison on a float requires an epsilon value, which doesn’t fit into the
==operator usage.FYI, the Implementation in Dora post seems to be empty.
Thanks!
Thanks, I appreciate it! :-)
My argument is that it stands for the exact same thing in both reference and value types: “is this thing here identical to that thing over there”?. Sure, we know this as “reference equality” on reference types, but it’s just as crucial on value types. Some may call it “ability to find your floats in your collections again equality”.
Here is another article on how
==vs.===relates to the various orderings the IEEE754 spec defines: Comparing & SortingI disagree on that. 80% of the comparisons on floating point values are with “magic values” like 0.0, 1.0, NaN etc. that were not exposed to any kind of arithmetic computation before, and therefore can not foil the comparison.
Yes, I left out the link, because I haven’t written it yet. :-)
Here is a unit test, that might demonstrate the semantics.
I would argue that if you have a comparison which is only good for “magic values” then what you really have is a bunch of useful functions:
isNaN,isZero, etc. I will note that== NaNis going to fail anyway!Which is exactly where
===comes in. :-)Another great resource on this topic: The Left Hand of Equals by Noble, Black, Bruce, Homer, and Miller
Thank you! I’ve updated the post with a link to the paper.
[Comment removed by author]
You’re right; I’ll update this.
Edit: It’s actually 608 * 10^-4324, FWIW.
Bit of a pet peeve for me that people get this wrong. I’ve even seen people call it “exponential notation”. Probably the “E” primes people to think “exponential”.
Almost nobody seems to understand floats. :-(((
I think I’m quite happy with the approach Julia takes, and looking at the issue tracker an awful lot of work went into it.
==means structural equality (and will promote types to be comparable if necessary and possible) and does three-value logic withmissing.===means identical (no program could distinguish these values).isequalis similar to==but doesn’t do three-value logic withmissing;NaNis equal to itself; and-0and0are not equal. This is used for dictionaries because Julia’s hash implementation returns the same hash for numeric types of the same value, even if their types are different!isapproxand≈for inexact equality with three-value logic.All except
===are recursively defined by default for collections and immutable types so you get structural equality. If you’re defining something weird then you have the expressivity to describe what equality means for that type.All of the above are total functions (i.e. should never throw errors), so comparing incomparables just gives you
false. If you want a partial function (throws an error for incomparable types, like some MLs), then you can define a dumb one withstrict_equal(a, b) = (typeof(a) == typeof(b) || error()) && a == bor a more sophisticated one with the promotion machinery and by introducing anincomparableorinexacttrait for things like floats.Equality is not hard. What is actually hard is convincing PL designers not to use the word “equality” for something that does not behave like mathematical equality. This is a sociological problem, not a technical one.
The only language I know of that provides function structural equality is https://www.unisonweb.org/