Why can't I compare reals in Standard ML?

3.5k views Asked by At
  1. Why doesn't 1.0 = 2.0 work? Isn't real an equality type?

    It gives the error:

    Error: operator and operand don't agree [equality type required]
      operator domain: ''Z * ''Z
      operand:         real * real
      in expression:
        1.0 = 2.0
    
  2. Why won't reals in patterns work like so?

    fun fact 0.0 = 1.0
      | fact x = x * fact (x - 1.0)
    

    It gives the error:

    Error: syntax error: inserting  EQUALOP
    
1

There are 1 answers

0
sshine On BEST ANSWER

Why doesn't 1.0 = 2.0 work? Isn't real an equality type?

No. The type variable ''Z indicates that the operands of = must have equality types.

Why won't reals in patterns work [...]?

Pattern matching relies implicitly on testing for equality. The cryptic error message syntax error: inserting EQUALOP indicates that the SML/NJ parser does not allow for floating-point literals where a pattern is expected, and so the programmer is prevented from receiving a more meaningful type error.

To elaborate,

From http://www.smlnj.org/doc/FAQ/faq.txt:

Q: Is real an equality type?

A: It was in SML '90 and SML/NJ 0.93, but it is not in SML '97 and SML/NJ 110. So 1.0 = 1.0 will cause a type error because "=" demands arguments that have an equality type. Also, real literals cannot be used in patterns.

From http://mlton.org/PolymorphicEquality:

The one ground type that can not be compared is real. So, 13.0 = 14.0 is not type correct. One can use Real.== to compare reals for equality, but beware that this has different algebraic properties than polymorphic equality.

For example, Real.== (0.1 + 0.2, 0.3) is false.

From http://sml-family.org/Basis/real.html:

Deciding if real should be an equality type, and if so, what should equality mean, was also problematic. IEEE specifies that the sign of zeros be ignored in comparisons, and that equality evaluate to false if either argument is NaN.

These constraints are disturbing to the SML programmer. The former implies that 0 = ~0 is true while r/0 = r/~0 is false. The latter implies such anomalies as r = r is false, or that, for a ref cell rr, we could have rr = rr but not have !rr = !rr. We accepted the unsigned comparison of zeros, but felt that the reflexive property of equality, structural equality, and the equivalence of <> and not o = ought to be preserved.

The short version: Don't compare reals using equality. Perform an epsilon test. I would recommend reading the article on http://floating-point-gui.de/errors/comparison. In summary:

  • Don't check if reals are the same, but if the difference is very small.

  • The error margin that the difference (delta) is compared to is often called epsilon.

  • Don't compare the difference against a fixed epsilon:

    fun nearlyEqual (a, b, eps) = Real.abs (a-b) < eps
    
  • Don't just compare the relative difference against epsilon:

    fun nearlyEqual (a, b, eps) = abs ((a-b)/b) < eps
    
  • Look out for edge cases:

    • When b = 0.0 it raises Div. (Switching a and b provides a symmetric edge case.)

    • When a and b are on opposite sides of zero it returns false even when they’re the smallest possible non-zero numbers.

    • The result is not commutative. There are cases where nearlyEqual (a, b, eps) does not give the same result as nearlyEqual (b, a, eps).

The guide provides a generic solution; translated to Standard ML this looks like:

fun nearlyEqual (a, b, eps) =
    let val absA = Real.abs a
        val absB = Real.abs b
        val diff = Real.abs (a - b)
    in Real.== (a, b) orelse
     ( if Real.== (a, 0.0) orelse
          Real.== (b, 0.0) orelse
          diff < Real.minNormalPos
       then diff < eps * Real.minNormalPos
       else diff / Real.min (absA + absB, Real.maxFinite) < eps )
    end

And it continues to warn of some edge cases:

There are some cases where the method above still produces unexpected results (in particular, it’s much stricter when one value is nearly zero than when it is exactly zero), and some of the tests it was developed to pass probably specify behaviour that is not appropriate for some applications. Before using it, make sure it’s appropriate for your application!