Skip to main content

Structural equality

Overview​

Equality (==) — and by extension inequality (!=) — is structural. Two values, a and b, are equal, a == b. They have equal contents regardless of the physical representation or identity of those values in memory.

For example, the strings "hello world" and "hello " # "world" are equal, even though they are most likely represented by different objects in memory.

Equality is defined only on shared types or on types that don’t contain:

  • Mutable fields.

  • Mutable arrays.

  • Non-shared functions.

  • Components of generic type.

For example, we can compare arrays of objects:

let a = [ { x = 10 }, { x = 20 } ];
let b = [ { x = 10 }, { x = 20 } ];
a == b;

Importantly, this does not compare by reference, but by value.

Subtyping​

Equality respects subtyping, so { x = 10 } == { x = 10; y = 20 } returns true.

To accommodate subtyping, two values of different types are equal if they are equal at their most specific, common supertype, meaning they agree on their common structure. The compiler will warn in cases where this might lead to subtle unwanted behavior.

For example: { x = 10 } == { y = 20 } will return true because the two values get compared at the empty record type. That’s unlikely the intention, so the compiler will emit a warning here.

{ x = 10 } == { y = 20 };

Generic types​

It is not possible to declare that a generic type variable is shared, so equality can only be used on non-generic types. For example, the following expression generates a warning:

func eq<A>(a : A, b : A) : Bool = a == b;

Comparing these two at the Any type means this comparison will return true no matter its arguments, so this doesn’t work as one might hope.

If you run into this limitation in your code, you should accept a comparison function of type (A, A) -> Bool as an argument and use that to compare the values instead.

Let’s look at a list membership test for example. This first implementation does not work:

import List "mo:base/List";

func contains<A>(element : A, list : List.List<A>) : Bool {
  switch list {
    case (?(head, tail))
      element == head or contains(element, tail);
    case null false;
  }
};

assert(not contains(1, ?(0, null)));

This assertion will trap because the compiler compares the type A at Any which is always true. As long as the list has at least one element, this version of contains will always return true.

This second implementation shows how to accept the comparison function explicitly instead:

import List "mo:base/List";
import Nat "mo:base/Nat";

func contains<A>(eqA : (A, A) -> Bool, element : A, list : List.List<A>) : Bool {
  switch list {
    case (?(head, tail))
      eqA(element, head) or contains(eqA, element, tail);
    case null false;
  }
};

assert(not contains(Nat.equal, 1, ?(0, null)));