2.3 equality
include equality
import equality as ...
2.3.1 Types of Equality
Pyret has three notions of equality. Two values can be equal now, always equal, and/or identical. The following table summarizes the functions and operators that test for these relationships, and how they compare to some other languages’ operators:
Name  Operator  Partial Predicate  Total Predicate  Similar To 
Equal Now  =~  equalnow  equalnow3  equal? (Racket) == (Python, Ruby) 
Always Equal  ==  equalalways  equalalways3  = (Ocaml) 
Identical  <=>  identical  identical3  eq? (Scheme) == (Ocaml) === (JavaScript) is (Python) == (Java) 
In most programs, you should use always equal, or ==, to compare values that you want to check for sameness. If you are working with mutable data, you may want to consider the special behavior of equal now. For some optimizations, defensive code, and capability patterns, you may have a reason to use identical.
2.3.2 Equal Now
Checks if the two values are equal now (they may not be later). Corresponds to the =~ operator.
2.3.2.1 Equal Now and Primitives
equalnow checks primitive equality on numbers, strings, and booleans:
check: 5 is%(equalnow) 5 5 isnot%(equalnow) 6 "abc" is%(equalnow) "abc" "a" isnot%(equalnow) "b" "a" isnot%(equalnow) 5 end
2.3.2.2 Equal Now and Structured Data
For instances of data (including, for example, instances of List), and objects, equalnow traverses their members and checks for pairwise equality. So, for example, lists will recursively check that their contents are the same, including the case where their contents are objects:
check: l1 = [list: 1, 2, 3] l2 = [list: 1, 2, 3] l1 is%(equalnow) l2 link(1, l1) isnot%(equalnow) l2 l3 = [list: {x: 5}] l4 = [list: {x: 5}] l5 = [list: {x: 6}] l3 is%(equalnow) l4 l3 isnot%(equalnow) l5 end
2.3.2.3 Equal Now and References
Equal Now checks the contents of mutable data it reaches. This gives it its name: since it only checks the current values, and those fields might change, it is not true that if e1 =~ e2, then later e1 =~ e2 will hold again. For example:
data MyBox:  mybox(ref x) end check: b1 = mybox(1) b2 = mybox(1) b1 is%(equalnow) b2 b1!{x : 2} b1 isnot%(equalnow) b2 end
Equal Now will recognize when references form a cycle, and cycles of the same shape are recognized as equal (even though the references might change their contents later):
data InfiniteList:  ilink(first, ref rest)  iempty end check: l1 = ilink(1, iempty) l2 = ilink(1, iempty) l3 = ilink(1, ilink(2, iempty)) l1!{rest : l1} l2!{rest : l2} l3!rest!{rest : l3} l1 is%(equalnow) l2 l1 isnot%(equalnow) l3 end
2.3.3 Identical
2.3.3.1 Identical and Primitives
Identical has the same behavior on primitives as Equal Now (Equal Now and Primitives).
2.3.3.2 Identical and Structural Equality
Identical does not visit members of objects or data instances. Instead, it checks if the values are actually the same exact value (the operator is meant to indicate that the values are interchangable). So objects with the same fields are not identical to anything but themselves:
check: o = { x: 5 } o2 = { x: 5 } o isnot%(identical) o2 o is%(identical) o o2 is%(identical) o2 end
2.3.3.3 Identical and Mutable Data
Identical does not inspect the contents of mutable data, either. It can be used to tell if two references are aliases for the same underlying state, or if they are in fact different (even though they may be equal right now).
data InfiniteList:  ilink(first, ref rest)  iempty end check: l1 = ilink(1, iempty) l2 = ilink(1, iempty) l1!{rest : l1} l2!{rest : l2} l1 is%(identical) l1 l1!rest is%(identical) l1 l1 isnot%(identical) l2 l1!rest isnot%(identical) l2 l2 is%(identical) l2 l2!rest is%(identical) l2 l2 isnot%(identical) l1 l2!rest isnot%(identical) l1 end
2.3.4 Always Equal
Checks if the two values will always be equal, and corresponds to the == operator.
equalalways checks for primitive and structural equality like equalnow, with the exception that it stops at mutable data and only checks that the mutable values are identical. Stopping at mutable boundaries ensures that if two values were equalalways at any point, they will still be equalalways later.
2.3.4.1 Always Equal and Mutable Data
Here are some examples of equalalways stopping at mutable data, but checking immutable data, contrasted with equalnow
data MyBox:  mybox(ref x) end check: b1 = mybox(1) b2 = mybox(1) b1 isnot%(equalalways) b2 b1 is%(equalnow) b2 b2!{x : 2} b1 isnot%(equalalways) b2 b1 isnot%(equalnow) b2 b3 = mybox(2) # remember that b2 currently contains 2 l1 = [list: b1, b2] l2 = [list: b1, b2] l3 = [list: b1, b3] l1 is%(equalnow) l2 l1 is%(equalalways) l2 l1 isnot%(identical) l2 l1 is%(equalnow) l3 l1 isnot%(equalalways) l3 l1 isnot%(identical) l3 b2!{x: 5} l1 is%(equalnow) l2 l1 is%(equalalways) l2 l1 isnot%(identical) l2 l1 isnot%(equalnow) l3 l1 isnot%(equalalways) l3 l1 isnot%(identical) l3 end
2.3.5 Properties of Equality Functions
The discussion above hints at a relationship between the three functions. In particular, if two values are Identical, they ought to be Always Equal, and if they are Always Equal, they ought to be Equal Now. The following table summarizes this relationship, which in fact does hold:
If ↓, then →  v1 <=> v2 could be...  v1 == v2 could be...  v1 =~ v2 could be... 
v1 <=> v2 is true    true only  true only 
v1 == v2 is true  true or false    true only 
v1 =~ v2 is true  true or false  true or false   
This table doesn’t have all the false cases in it, because we need to complete the story for a few values that haven’t been discussed before we can give the whole picture.
2.3.6 Bounded Equalities
When comparing numbers, it’s often useful to be able to compare within a range. For example, if we write an algorithm that computes an answer to within a given tolerance, we may want to check if the answer is within that tolerance.
check: sqrt5 = numsqrt(5) (sqrt5 < 2.23) is true (sqrt5 > 2.22) is true end
Pyret has a family of builtin functions for cases like this, and the default is within:
It takes an argument representing the relative error, and returns a function that can be used to check equality up to that relative error. For example, we can check if an answer is within 10% of a desired result:
check: within10percent = within(0.1) within10percent(9.5, 10.5) end
Relative difference is defined by multiplying the mean of the two numbers by tol, and checking that the result is less than the difference between them. That is, in the expression above, within checks:
(((9.5 + 10.5) / 2) * 0.1) < (10.5  9.5)
Converting to exact numbers first avoids overflows on computing the mean. Put yet another way, aside from some slight differences in bounds checking for errors, we could implement the numeric comparison of within as:
fun mywithin(tol): lam(left, right): (((numexact(left) + numexact(right)) / 2) * numexact(tol)) < numabs(numexact(left)  numexact(right)) end end
The tol argument must be between 0 and 1.
It’s common to use within along with is% to define the binary predicate inline with the test:
check: numsqrt(10) is%(within(0.1)) 3.2 numsqrt(10) isnot%(within(0.1)) 5 end
Finally, within accepts any two values, not just numbers. On nonnumeric arguments, within traverses the structures just as in equalalways, but deferring to the boundschecking equality when a pair of numbers is encountered. All other values are compared with equalalways.
check: l7 = [list: 1] l8 = [list: ~1.2] l7 is%(withinrel(0.5)) l8 l7 isnot%(withinrel(0.1)) l8 l7 is%(withinrel(~0.5)) l8 l7 isnot%(withinrel(~0.1)) l8 end
An alias for within.
Like withinrel, but compares with absolute tolerance rather than relative. The definition is equivalent to:
fun mywithinabs(tol): lam(left, right): numabs(numexact(left)  numexact(right)) <= tol end end
check: la = [list: 10] lb = [list: ~12] la is%(withinabs(2)) lb la isnot%(withinabs(1)) lb la is%(withinabs(~5.5)) lb la isnot%(withinabs(~1.9999)) lb end
Like withinrel and withinabs, but they traverse mutable structures as in equalnow.
check: aa = [array: 10] ab = [array: ~12] aa is%(withinrelnow(~0.2)) ab aa isnot%(withinrel(~0.2)) ab aa is%(withinabsnow(2)) ab aa isnot%(withinabs(2)) ab end
2.3.7 Undefined Equalities
For some values, Pyret refuses to report true or false for any equality predicate, and raises an error instead. For example:
check: (~3 == ~3) raises "equalityfailure" (1 == ~1) raises "equalityfailure" (lam(x): x end == lam(y): y end) raises "equalityfailure" end
This section discusses why this is the case.
2.3.7.1 Roughnums and Equality
How to Design Programs describes this design space well. Numbers’ representations in programs reflect a number of tradeoffs, but the upshot is that numbers have finite, approximate representations for performance reasons. Numbers like e, π, and √2 are only represented up to some approximation of their true (irrational) value. When such a result is used in a computation, it represents a rough approximation of the true value.
Pyret calls these numbers Roughnums, and they have special rules related to equality. In particular, they cannot be directly compared for equality, even if it seems like they ought to be equal:
check: (~3 == ~3) raises "equalityfailure" end
In addition, Roughnums cannot be compared for equality with Exactnums, either.
check: (~0.1 == 0.1) raises "equalityfailure" end
This example is not Pyretspecific, but matches the behavior of IEEE floating point. Returning either true or false in this case would be misleading, as because of unavoidable inaccuracies, both of the following expressions evaluate to ~0.1:
(~1  ~0.9) + 0.00000000000000003 ~0.2  ~0.1
So in the following check block, if we chose either true or false for the result of ~0.1 == 0.1, one of the tests would have a misleading failure:
check: ((~1  ~0.9) + 0.00000000000000003) is 0.1 (~0.2  ~0.1) is 0.1 end
For example, if Pyret answered true for the rough equivalent, ~0.1 == ~0.1, then this test would pass:
check: ((~1  ~0.9) + 0.00000000000000003) is (~0.2  ~0.1) end
To avoid giving misleading answers in cases like these, Pyret triggers an error on any numbertonumber comparison that involves a Roughnum, which looks like:
These two values cannot be compared for direct equality: 

~0.1 
~0.1 

Approximations of numbers (Roughnums) cannot be compared for equality. The 
program may need to use within(). 
If you see this error, it’s a hint that the program should be using an equality from the within family of functions to do a relative comparison, rather than a direct equality comparison. So in this case, we could check that the answer is equal up to an relative error of 0.001:
check: ((~1  ~0.9) + 0.00000000000000003) is%(within(0.001)) (~0.2  ~0.1) end
It can be useful to check that two Roughnums are actually indistinguishable, even though they may be approximating different values. This can be expressed by checking that the numbers are within a tolerance of ~0:
check: ((~1  ~0.9) + 0.00000000000000003) is%(within(~0)) (~0.2  ~0.1) end
Note that the same won’t work for a tolerance of 0, the exact zero, which will give an error if used to compare two Roughnums.
2.3.7.2 Functions and Equality
When comparing two functions or two methods, all the equality operators raise an exception. Why? Well, the traditional way to compare functions for equality (short of solving the halting problem), is to use reference equality (or identical) on the functions’ representations, the same way as mutable data works. For a hint of why this can be a misleading definition of equality, consider this data definition:
data Stream<a>:  stream(first :: a, rest :: (> Stream<a>)) end check: fun mkones(): stream(1, mkones) end ones = mkones() ones is ones # Should this succeed? ones is mkones() # What about this? ones.rest() is mkones() # Or this...? end
All of these values (ones, mkones(), etc.) have the same behavior, so we could argue that is (which uses == behind the scenes) ought to succeed on these. And indeed, if we used reference equality, it would succeed. But consider this small tweak to the program:
check: fun mkones(): stream(1, lam(): mkones() end) # < changed this line end ones = mkones() ones is ones # Should this succeed? ones is mkones() # What about this? ones.rest() is mkones() # Or this...? end
If we used reference equality on these functions, all of these tests would now fail, and ones has the exact same behavior. Here’s the situation:
In fact, a famous result in theoretical computer science is that it is impossible to figure out out if two functions do the same thing in general, even if it is possible in certain special cases (like reference equality).
When reference equality returns true, we know that the two functions must have the same behavior. But when it returns false, we know nothing. The functions may behave exactly the same, or they might be completely different, and the equality predicate can’t tell us either way.
Pyret takes the following stance: You probably should rethink your program if it relies on comparing functions for equality, since Pyret cannot give reliable answers (no language can). So, all the examples above (with one notable exception) actually raise errors:
check: fun mkones(): stream(1, lam(): mkones() end) # < changed this line end ones = mkones() ones == ones is true ones == mkones() raises "Attempted to compare functions" ones.rest() == mkones() raises "Attempted to compare functions" end
The first test is true because two identical values are considered equalalways. This is an interesting point in this design space that Pyret may explore more in the future – it isn’t clear if the benefits of this relationship between identical and equalalways are worth the slight brittleness in the above example.
Note 1: Functions can be compared with nonfunction values and return false. That is, the equality operators only throw the error if actual function values need to be compared to one another, not if a function value is compared to another type of value:
check: f = lam(): "noop" end g = lam(): "also noop" end f == f raises "Attempted to compare functions" f == g raises "Attempted to compare functions" g == f raises "Attempted to compare functions" 5 isnot%(equalalways) f { x: 5 } isnot%(equalalways) { x: f } end
Note 2: This rule about functions interacts with structural equality. When comparing two values, it seems at first unclear whether the result should be false or an error for this test:
check: { x: 5, f: lam(): "noop" end } is%(equalalways) { x: 6, f: lam(): "noop" end } end
This comparison will return false. The rule is that if the equality algorithm can find values that differ without comparing functions, it will report the difference and return false. However, if all of the nonfunction comparisons are true, and some functions were compared, then an error is raised. A few more examples:
check: o = { x: 5, y: { z: 6 }, lam(): "noop" end } o2 = { x: 5, y: { z: 7 }, lam(): "noop" end } (o == o) raises "Attempted to compare functions" o isnot%(equalalways) o2 # Test succeeds, because z fields differ end
2.3.8 Total Equality Functions (Avoiding Incomparability Errors)
Most Pyret programs should be written using equalalways, equalnow, and identical, which guarantee that an error will be raised if functions are compared. Some programs, however, need to be able to compare arbitrary values, and it’s convenient to have the ability to compare values without raising an exception. Since the equality of functions is unknown, we define the result of a total equality check with a new datatype:
We define three parallel functions to the equality predicates that return EqualityResult values. They return Equal and NotEqual whenever the corresponding function would, and Unknown whenever the corresponding function would throw an error:
check: f = lam(): 5 end equalalways3(f, f) is Unknown equalalways3(f, 5) satisfies isNotEqual equalnow3(f, f) is Unknown equalnow3("a", f) satisfies isNotEqual identical3("a", f) satisfies isNotEqual identical3(f, f) is Unknown identical3("a", f) satisfies isNotEqual end
We can now modify our table from above to be more complete:
If ↓, then →  identical(v1, v2) could be...  equalalways(v1, v2) could be...  equalnow(v1, v2) could be... 
identical(v1, v2) is Equal    Equal only  Equal only 
equalalways(v1, v2) is Equal  Equal or NotEqual    Equal only 
equalnow(v1, v2) is Equal  Equal or NotEqual  Equal or NotEqual   
identical(v1, v2) is NotEqual    Equal or NotEqual or Unknown  Equal or NotEqual or Unknown 
equalalways(v1, v2) is NotEqual  NotEqual only    Equal or NotEqual or Unknown 
equalnow(v1, v2) is NotEqual  NotEqual only  NotEqual only   
identical(v1, v2) is Unknown    Unknown only  Unknown only 
equalalways(v1, v2) is Unknown  Unknown or NotEqual    Unknown only 
equalnow(v1, v2) is Unknown  Unknown or NotEqual  Unknown or NotEqual   
There are corresponding total functions defined for within as well:
2.3.9 Datatypedefined Equality
The functions equalnow and equalalways are defined to work over values created with data by comparing fields in the same position. However, sometimes userdefined values need a more sophisticated notion of equality than this simple definition provides.
For consider implementing an unordered set of values in Pyret. We might choose to implement it as a function that creates an object closing over the implementation of the set itself:
fun makeemptyset<a>(): { add(self, element :: a): ... end, member(self, element :: a) > Boolean: ... end, equaltootherset(self, other) > Boolean: ... end } end
We could fill in the bodies of the methods to have this implementation let clients create sets and add elements to them, but it won’t work well with testing:
check: s = makeemptyset().add(5) s2 = makeemptyset().add(5) s.member(5) is true s2.member(5) is true s.equaltootherset(s2) is true s == s2 raises "Attempted to compare functions" end
The final test raises an exception because it traverses the structure of the object, and the only visible values are the three methods, which cannot be compared. We might just say that users of custom datatypes have to use custom predicates for testing, for example they could write:
check: # as before ... fun equalsets(set1, set2): set1.equaltootherset(set2) end s is%(equalsets) s2 end
This works for sets on their own, but the builtin testing and equality operators will not work with nested userdefined data structures. For example, since lists are a dataype that checks builtin equality on their members, a list of sets as defined above will not use the equaltootherset method when comparing elements, and give an "Attempted to compare functions" error:
check: # as before ... ([list: s] == [list: s2]) raises "Attempted to compare functions" end
To help make this use case more pleasant, Pyret picks a method name to call, if it is present, on userdefined objects when checking equality. The method name is _equals, and it has the following signature:
 ._equals :: (
 other :: a,
 equalrec :: (Any, Any > EqualityResult)
 )
 > EqualityResult
Where a is the type of the object itself (so for sets, other would be annotated with Set<a>).
The _equals method is called in the equality algorithm when:
The two values are either both data values or both objects, AND
If they are data values, the two values are of the same data type and variant, AND
If they are objects not created by data, they have the same set of Brands
So, for example, an object with an _equals method that always returns Equal is not considered equal to values that aren’t also objects:
import Equal from equality check: eqall = { _equals(self, other, eq): Equal end } eqall isnot== f eqall isnot== m eqall isnot== 0 eqall isnot== "a" eqall is== {} end
The last argument to _equals is the recursive equality callback to use for checking equality of any members. When checking for equality of members (say in our set implementation above), we would use this callback rather than one of equalalways3 or equalnow3. The reasons for this are threefold:
In order to check for equality of cyclic values, Pyret needs to do internal bookkeeping of visited references. This information is stored within the callback, and calling e.g. equalnow3 directly would not take previously visted references into account.
To avoid requiring datatypes to implement two equality methods, the callback also knows whether this equality call was started by equalnow or by equalalways. Any recursive calls should use the original semantics for comparing references, so using the callback ensures that equality checks on elements have the right semantics (even in deeply nested data structures).
The recursive equality predicate closes over and remembers the tolerance for withinfamily functions, and whether or not the tolerance is absolute or relative.
2.3.10 Inequalities
The inequality operators and functions in Pyret follow different rules than those for equality. In particular:
There are no 3valued forms for the inequality functions, because...
All the inequalities (even nonstrict inequality like <=) are defined on Roughnums.
Comparing approximate numbers with inequalities is technically a bit fraught. If x < y and x and y are both approximations, it may be that the approximation error causes the comparison to return true rather than false. The same argument holds for the other inequality operators. However, the inequality operators can be a part of correct use of approximations, for example by using a test like x < (y + tolerance), (where tolerance could be usefully specified as either positive or negative), in applications that closely track approximation error. Since in common cases inequality comparison of approximation is quite useful, and it is quite onerous to program with an analog of within for inequalities as well, Pyret chooses to allow the inequality operators to work on approximations.
The inequality operators all work on either:
Pairs of numbers (whether exact or approximate)
Pairs of strings
Lefthandside objects with an appropriatelynamed method (for example, for the < operator, the object must have a _lessthan method.)
Numbers are compared in their standard mathematical order. Strings are compared lexicographically (examples below). For objects with overloaded methods, the method should return a Boolean and that return value is used as the result.
check "strings": "a" < "b" is true "b" > "a" is true "a" < "a" is false "a" > "a" is false "a" <= "a" is true "a" >= "a" is true "A" < "a" is true "a" > "A" is true "a" < "A" is false "A" > "a" is false "a" < "aa" is true "a" > "aa" is false "a" < "baa" is true "a" > "baa" is false "abb" < "b" is true "abb" > "b" is false "ab" < "aa" is false "ab" > "aa" is true "aa" < "ab" is true "aa" > "ab" is false end
check "numbers": ~5 < 5 is false ~5 > 5 is false ~5 <= 5 is true ~5 >= 5 is true ~5 < ~5 is false ~4.9 < ~5 is true ~5 <= ~5 is true ~5 >= ~5 is true end