Landin library reference source

core/cmp

Shared: available on every enabled target.

Equality, hashing and ordering evidence, apart from the containers and algorithms that consume it.

equatable, hashable and ordered ship for the ten integer scalars, bool (equality and hashing) and []u8 (equality and hashing); core/text adds all three for utf8. There is one register and no override: another reading of a shipped type goes on a distinct wrapper with its own evidence. A hashable key declares its equatable conformance as well. The compiler does not prove the laws: equality must be an equivalence, equal keys must hash alike, and less must be a strict weak ordering. Floating-point types have no shipped evidence.

Items

Executable example

This complete program is maintained in the repository runtime tests. View source.

import core/cmp

--  The shipped evidence answers through the concepts alone, without a map
--  or a sort to carry it.
same: (item: type is cmp.equatable, left: item, right: item) -> (yes: bool) =
    yes = item.equal(left, right)
end same

digest: (item: type is cmp.hashable, value: item) -> (result: u64) =
    result = item.hash(value)
end digest

before: (item: type is cmp.ordered, left: item, right: item) -> (yes: bool) =
    yes = item.less(left, right)
end before

exercise: () -> (ok: bool) =
    ok = false
    bytes: []u8 = "ab"
    copy: []u8 = "ab"
    other: []u8 = "ba"
    return when not same(u32(7), u32(7)) or same(true, false)
    return when not same(bytes, copy) or same(bytes, other)
    return when digest(u16(9)) <> 9 or digest(bytes) == digest(other)
    ok = before(i32(-1), i32(0)) and not before(u8(2), u8(2))
end exercise

public main: () -> (code: i32) =
    code = 1
    ok := exercise()
    if ok then
        code = 42
    end if
end main

equatable concept

public equatable: type = concept (item: type)
    --- Report whether two items are equal under a stable equivalence.
    equal: (left: item, right: item) -> (yes: bool)
end equatable

core/cmp/cmp.ldn:7

Equality evidence. equal must be an equivalence relation, and stay one while an item is stored, for example as a map key.

hashable concept

public hashable: type = concept (item: type) is equatable
    --- Return a stable hash; items `equal` to each other hash equally.
    hash: (value: item) -> (result: u64)
end hashable

core/cmp/cmp.ldn:18

Hash evidence composing equatable. Items that are equal must have equal hashes, and both must stay stable while an item is stored. Hashes are not cryptographic.

A hashable conformance composes equatable, but [1340] still requires a concrete type to declare both conformances explicitly.

ordered concept

public ordered: type = concept (item: type)
    --- Return true exactly when left precedes right under the strict weak
    --- ordering.
    less: (left: item, right: item) -> (yes: bool)
end ordered

core/cmp/cmp.ldn:171

Strict ordering evidence. less must be irreflexive and transitive, with consistent equivalence classes, for the duration of a sort.