eqhash

Eq and Hash: the prelude traits behind `==` and hashing.

examples/traits/eqhash.dawn

# Eq and Hash: the prelude traits behind `==` and hashing.
#
# The point of making them traits is dispatch a backend without a universal
# `equals`/`hashCode` can implement -- a forwarded dictionary. That is what a
# `[T: Eq]` bound is: the subject is rigid inside the function, so the caller
# hands the comparison in.
#
# Where the subject is statically known, no dictionary is built: `eq` on a
# scalar lowers to the same primitive comparison `==` emits.
#
# Run: dawn run examples/traits/eqhash.dawn
use std/io
use std/list

## Rigid `T`, so both the comparison and the hash arrive from the caller.
fn contains[T: Eq](xs: List[T], x: T) -> Bool = {
  for y in xs {
    if eq(y, x) { return true }
  }
  false
}

fn digest[T: Hash](xs: List[T]) -> Int = {
  var h = 1
  for x in xs { h = h * 31 + hash(x) }
  h
}

## No `impl Eq` here: structural equality is already the default for every
## type, so a bound over Color is satisfied without writing anything.
type Color = | Red | Green | Blue

## An override is only ever worth writing to be *non*-structural: here only
## `x` counts, so two points differing in `y` are equal.
##
## Note what the body may not say. `a == b` would be this very function --
## overriding `==` makes the structural default unreachable from inside the
## override, exactly as `fn f(x) = f(x)` is unreachable from inside itself.
## Compare fields, not values.
type P = { x: Int, y: Int }

impl Eq[P] {
  fn eq(a: P, b: P) -> Bool = a.x == b.x
}

impl Hash[P] {
  fn hash(p: P) -> Int = p.x * 31
}

pub fn main() -> Unit !io = {
  println("-- forwarded dictionaries --")
  println("contains([1, 2, 3], 2)   = ${contains([1, 2, 3], 2)}")
  println("contains([\"a\", \"b\"], \"b\") = ${contains(["a", "b"], "b")}")
  println("contains([Red, Blue], Blue) = ${contains([Red, Blue], Blue)}")
  println("digest([1, 2, 3])        = ${digest([1, 2, 3])}")

  println("-- an overriding impl --")
  let a = P { x: 1, y: 2 }
  let b = P { x: 1, y: 99 }
  println("eq(a, b) = ${eq(a, b)}    (only x counts)")
  println("a == b   = ${a == b}    (the operator now means the impl too)")
  println("hash(a)  = ${hash(a)}")
}

test "a rigid T takes its comparison from the caller" {
  assert contains([1, 2, 3], 2)
  assert not contains([1, 2, 3], 9)
  assert contains(["a", "b"], "b")
  assert contains([Red, Blue], Blue)
}

test "an overriding impl is what `==` means from then on" {
  let a = P { x: 1, y: 2 }
  let b = P { x: 1, y: 99 }
  assert eq(a, b)
  assert a == b
  assert hash(a) == hash(b)
}

test "structural equality needs no impl at all" {
  assert Red == Red
  assert not (Red == Blue)
}