init::prelude

init/src/prelude.mo

typeAny#
pub type Any {
    any {A : Type} (value : A)
}
classFunctor#
pub class Functor (F : Type -> Type) {
    def map (f : A -> B) : (F A) -> F B
}
classFromListLiteral#
pub class FromListLiteral (L : Type -> Type := List) {
    def cons (a : A) (L A) : L A
    def empty : L A
}
classHAdd#
pub class HAdd A B C {
    def add : A -> B -> C
}

Heterogeneous addition

classAdd#
pub class Add A {
    def add : A -> A -> A
}

Homogeneous addition

instance_#
pub instance [Add A] HAdd A A A {
    def add (a b : A) : A := Add.add a b
}
classHSub#
pub class HSub A B C {
    def sub : A -> B -> C
}

Heterogeneous subtraction

classSub#
pub class Sub A {
    def sub : A -> A -> A
}

Homogeneous subtraction

instance_#
pub instance [Sub A] HSub A A A {
    def sub (a b : A) : A := Sub.sub a b
}
classHMul#
pub class HMul A B C {
    def mul : A -> B -> C
}

Heterogeneous multiplication

classMul#
pub class Mul A {
    def mul : A -> A -> A
}

Homogeneous multiplication

instance_#
pub instance [Mul A] HMul A A A {
    def mul (a b : A) : A := Mul.mul a b
}
classHDiv#
pub class HDiv A B C {
    def div : A -> B -> C
}

Heterogeneous division

classDiv#
pub class Div A {
    def div : A -> A -> A
}

Homogeneous division

instance_#
pub instance [Div A] HDiv A A A {
    def div (a b : A) : A := Div.div a b
}
infixHAdd.add#
pub infix (+)
infixHDiv.div#
pub infix (/)
infixHMul.mul#
pub infix (*)
infixHSub.sub#
pub infix (-)
classApplicative#
pub class [Functor F] Applicative (F : Type -> Type) {
    def pure : A -> F A
    def apply : F (A -> B) -> F A -> F B
}
classMonad#
pub class [Applicative M] Monad (M : Type -> Type) {
    def bind (a : M A) (f : A -> M B) : M B
    def pure : A -> M A
}
infixMonad.bind#
pub infix (>>=)
classComonad#
pub class Comonad (W : Type -> Type) {
    def extract (W A) : A
    def duplicate (W A) : W (W A)
    def extend (f : W A -> B) (W A) : W B
}

Dual of Monad: extract pulls the value out of a context; duplicate and extend push the context inwards. All three are required -- the usual extend f = map f . duplicate default would need a Functor superclass constraint, and a superclass constraint gets no slot in the dictionary.

classMonadState#
pub class MonadState (M : Type -> Type) (S : Type) {
    def get : M S
    def set (s : S) : M Unit
    def modify_get (f : S -> Pair S A) : M A

    /// Modify the state and return unit
    def modify (f : S -> S) : M Unit :=
        modify_get (fn s => Pair.pair (f s) unit)

    /// Get the state, apply a function, and return the result
    def get_map (f : S -> A) : M A :=
        modify_get (fn s => Pair.pair s (f s))
}

State monad: thread state S through a monad M. S is a class parameter because each instance fixes it (instance MonadState (State I64) I64); M stays first so KnownInstances keys on the monad's concrete head.

classMonadLift#
pub class MonadLift (m : Type -> Type) (n : Type -> Type) {
    def monad_lift (a : m A) : n A
}

Lift computations from monad m into monad n

classMonadLiftT#
pub class MonadLiftT (m : Type -> Type) (n : Type -> Type) {
    def monad_lift_t (a : m A) : n A
}

Transitive monad lift. The reflexive instance (lifting from m to m) is the identity below; for other pairs, provide an instance that delegates to MonadLift.

instance_#
pub instance MonadLiftT m m {
    def monad_lift_t (a : m A) : m A := a
}

Reflexive: lifting from m to m is the identity

typeVoid#
pub type Void {}

Void is the deliberate exception to the witness rule: it IS the empty type (False). Nothing may inhabit it, and matching on it is the absurd eliminator. It is not an opaque VALUE type, so it carries no witness.

classInhabited#
pub class Inhabited {u : Universe} (a : Sort u) : Sort (max 1 u) {
    def default : a
}

Inhabited a — a has a canonical value. A class (instance-resolved), so generic code can require one implicitly.

The class's own result sort is Sort (max 1 u): the dictionary type lives one universe above its carrier at least. The class head now carries that clause for real (Class.sort), and check_class_with_scope rejects a non-sort kind.

typeNonEmpty#
pub type NonEmpty {u : Universe} (a : Sort u) : Pred {
    nonempty (witness : a),
}

NonEmpty a — the proposition that a has SOME value. Proof-level (Pred is the Prop alias), so it is erased and proof-irrelevant. Use it where only existence matters; use Inhabited when a default value is wanted.

typeString#
pub type String {
    of_bytes (List U8)
}

UTF8 string

typeChar#
pub type Char {
    of_bytes (List U8)
}

UTF8 code point

classToString#
pub class ToString A {
    def to_string (a : A) : String
}
typeI64#
pub type I64 { i64_witness }

Primitive number types.

Each is an OPAQUE native-backed type: an inductive with exactly one nullary WITNESS constructor. A type with no constructors is the empty type (False), and a native returning one would be asserting an inhabitant of False — so every opaque value type declares a witness. #[opaque] makes the witness unreferenceable: it may be neither constructed nor matched, which is what keeps the type abstract and its representation native. Values come only from the native operations.

typeI32#
pub type I32 { i32_witness }
typeI16#
pub type I16 { i16_witness }
typeI8#
pub type I8 { i8_witness }
typeU64#
pub type U64 { u64_witness }
typeU32#
pub type U32 { u32_witness }
typeU16#
pub type U16 { u16_witness }
typeU8#
pub type U8 { u8_witness }
typeF64#
pub type F64 { f64_witness }
typeF32#
pub type F32 { f32_witness }
typePtr#
pub type Ptr { ptr_witness }

Opaque C pointer for the #[extern "c"] FFI. A Ptr value is the raw machine word under every backend; never match, compare or print one (the FdStream convention, std/src/stream.mo). The witness keeps the type inhabited; #[opaque] keeps it abstract.

defPtr.null#
pub def Ptr.null : Ptr

The NULL pointer — SSL_set_verify's callback argument is the first caller (motes/tls).

defPtr.minus_one#
pub def Ptr.minus_one : Ptr

The fixed (void*)-1 sentinel (SQLite's SQLITE_TRANSIENT is one user). It takes no input, so unlike a general I64-to-Ptr conversion it cannot produce an arbitrary address.

typeUnit#
pub type Unit {
    unit
}
typeBool#
pub type Bool {
    true,
    false
}
typeTrue#
pub type True : Prop {
    trivial
}

Trivially true proposition (unit in Prop)

typeEq#
pub type Eq (A : Sort 1) (a : A) (b : A) : Prop {
    refl : Eq A a a
}

Propositional equality: Eq A a b lives in Prop (Sort 0)

defEq.rec#
pub def Eq.rec (A : Sort 1) (a : A) (P : (b : A) -> Eq A a b -> Sort 1)
    (h : P a (Eq.refl a)) (b : A) (e : Eq A a b) : P b e

Native J eliminator for propositional equality

classBEq#
pub class BEq A {
    def beq : A -> A -> Bool

    /// Logical negation of `beq`, as a class DEFAULT: an instance only
    /// implements `beq`. The self-hosted compiler splices this body into an
    /// instance that omits it (`promote_methods`).
    def not_beq (a : A) (b : A) : Bool := Bool.not (BEq.beq a b)
}

Equals

instance_#
pub instance BEq Bool {
    def beq (a b : Bool) : Bool :=
        if a then b
        else (Bool.not b)
}
infixBEq.beq#
pub infix (==)
infixBEq.not_beq#
pub infix (!=)
classBOrd#
pub class BOrd A {
    def lt (a b : A) : Bool
    def gt (a b : A) : Bool
    def lte (a b : A) : Bool
    def gte (a b : A) : Bool
}

Ordered comparison.

lte/gte are required methods rather than class defaults: the Rust host's checked dictionary path refuses an instance that omits a declared method whose implementation is a default (check_one_instance_new in rust/core/src/core_check_module.rs), falling back to an unchecked path. Every instance therefore states both. They mean not gt / not lt, the total-order reading BOrd already assumes.

infixBOrd.lt#
pub infix (<)
infixBOrd.lte#
pub infix (<=)

a <= b, i.e. not (a > b).

infixBOrd.gte#
pub infix (>=)

a >= b, i.e. not (a < b).

infixBOrd.gt#
pub infix (>)
instance_#
pub instance BOrd Bool {
    def lt (a b : Bool) : Bool :=
        if a then false
        else b

    def gt (a b : Bool) : Bool :=
        if a then Bool.not b
        else false

    // false <= anything; true <= b exactly when b is true.
    def lte (a b : Bool) : Bool :=
        if a then b
        else true

    // true >= anything; false >= b exactly when b is false.
    def gte (a b : Bool) : Bool :=
        if a then true
        else Bool.not b
}
classHashable#
pub class Hashable A {
    def hash (a : A) : U64
}

Hashable: produce a hash value for an element.

typeDefaultValue#
pub type DefaultValue (A : Type) (default : A) {
    default
}
defBool.not#
pub def Bool.not (b : Bool) : Bool
defBool.and#
pub def Bool.and (a b : Bool) : Bool
infixBool.and#
pub infix (&&)
defBool.or#
pub def Bool.or (a b : Bool) : Bool
infixBool.or#
pub infix (||)
typeResult#
pub type Result E A {
    ok (a : A),
    err (e : E)
}
defResult.is_ok#
pub def Result.is_ok {E A : Type} (r : Result E A) : Bool

Whether r is Result.ok -- for a caller that checks an effect's outcome (a test asserting a write landed) without needing its value.

instance_#
pub instance Functor (Result E) {
    def map (f : A -> B) (r : Result E A) : Result E B :=
        match r {
            Result.ok a => Result.ok (f a),
            Result.err e => Result.err e
        }
}

Result E is the error monad: bind threads an ok value and stops at the first err, which it passes through unchanged. This is what a do block over a Result E A runs on.

instance_#
pub instance Applicative (Result E) {
    def pure (a : A) : Result E A := Result.ok a

    def apply (f : Result E (A -> B)) (r : Result E A) : Result E B :=
        match f {
            Result.ok g =>
                match r {
                    Result.ok a => Result.ok (g a),
                    Result.err e => Result.err e
                },
            Result.err e => Result.err e
        }
}
instance_#
pub instance Monad (Result E) {
    def pure (a : A) : Result E A := Result.ok a

    def bind (r : Result E A) (f : A -> Result E B) : Result E B :=
        match r {
            Result.ok a => f a,
            Result.err e => Result.err e
        }
}
typePair#
pub type Pair A B {
    pair (first : A) (second : B)
}
typeSigma#
pub type Sigma (A : Sort u) (B : A -> Sort v) : Sort w {
    dpair (fst : A) (snd : B fst)
}

Dependent pair: the second component's TYPE may depend on the first component's VALUE -- e.g. Sigma Nat (fn n => Vec n A) pairs a length with a vector of exactly that length.

The non-dependent Pair A B above is the special case Sigma A (fn _ => B). Both are kept: recovering fn _ => B at every tuple literal would need higher-order unification, so Pair remains what the tuple syntax desugars to.

snd's declared type applies B to the EARLIER field fst. That shape was unrepresentable until constructor parameter lists were made to bind; before that the mention dangled and was silently generalized into an unrelated implicit. Dependent pairs. The result universe is a FREE level w, so the same inductive serves both a data Sigma (instantiated at Sort (max u v)) and the propositional Exists below (instantiated at Sort 0, where Prop's impredicativity lets a Type-level first component sit inside a Prop pair).

The level clauses are deliberately OMITTED (type Sigma (A : Sort u) … rather than {u} {v} {w}): levels are name-keyed and survive by mention in Sort u/Sort v/Sort w, and one name per {...} clause is the grammar both compilers share. The Rust host has no level variables; it approximates a bare symbolic result sort to the bottom universe.

defExists#
pub def Exists (A : Type) (P : A -> Prop) : Prop

Existential quantification -- Sigma instantiated at Prop.

This is now a def alias: Sigma A P is a dependent pair whose result level is solved by the expected Prop, so the pair itself lands in Sort 0. One constructor (Sigma.dpair) and one set of projections serve both Sigma and Exists.

defSigma.fst#
pub def Sigma.fst {A : Type} {B : A -> Type} (p : Sigma A B) : A

First projection. Non-dependent, so ordinary match typing suffices.

The second projection is the dependent one: snd's declared field type is B fst, so checking match p { Sigma.dpair a b => b } needs the arm's expected type to see the scrutinee refined to Sigma.dpair a b, and Sigma.fst (Sigma.dpair a b) reduced to a. Both compilers do that now: the self-hosted checker's dependent-match rule, and the Rust host's arm refinement plus a narrow beta/delta/iota normalizer (core_check::whnf_core).

defSigma.snd#
pub def Sigma.snd {A : Type} {B : A -> Type} (p : Sigma A B) : B (Sigma.fst p)

Second projection. The arm's expected type B (Sigma.fst p) is refined with p := Sigma.dpair a b; Sigma.fst's own body then reduces to a, so the field b : B a checks.

typeOption#
pub type Option A {
    some (a : A),
    none
}
defOption.get_or_default#
pub def Option.get_or_default (default : A) (self : Option A) : A
defOption.is_none#
pub def Option.is_none (self : Option A) : Bool

Absent? The question every match o { none => true, _ => false } asks; generic over the payload so it works on any Option A.

defOption.map#
pub def Option.map (f : A -> B) (self : Option A) : Option B
defOption.bind#
pub def Option.bind (self : Option A) (f : A -> Option B) : Option B

Sequence an optional computation: none short-circuits.

instance_#
pub instance Functor Option {
    def map (f : A -> B) (o : Option A) : Option B := Option.map f o
}

Option is the failure monad: a do block over Option A stops at the first none.

instance_#
pub instance Applicative Option {
    def pure (a : A) : Option A := some a

    def apply (f : Option (A -> B)) (o : Option A) : Option B :=
        match f {
            some g => Option.map g o,
            none => none
        }
}
instance_#
pub instance Monad Option {
    def pure (a : A) : Option A := some a

    def bind (o : Option A) (f : A -> Option B) : Option B := Option.bind o f
}
typeNat#
pub type Nat {
    zero,
    succ (n : Nat)
}
defNat.add#
pub def Nat.add (a b : Nat) : Nat
defNat.sub#
pub def Nat.sub (a b : Nat) : Nat
defNat.mul#
pub def Nat.mul (a b : Nat) : Nat
defNat.eq#
pub def Nat.eq (a b : Nat) : Bool
instance_#
pub instance BEq Nat {
    def beq (a b : Nat) : Bool := Nat.eq a b
}
instance_#
pub instance Add Nat {
    def add (a b : Nat) : Nat := Nat.add a b
}
instance_#
pub instance Sub Nat {
    def sub (a b : Nat) : Nat := Nat.sub a b
}
instance_#
pub instance Mul Nat {
    def mul (a b : Nat) : Nat := Nat.mul a b
}
defNat.le#
pub def Nat.le (a b : Nat) : Bool

a <= b, by structural descent on both.

defNat.lt#
pub def Nat.lt (a b : Nat) : Bool

a < b: succ a <= b.

instance_#
pub instance BOrd Nat {
    def lt (a b : Nat) : Bool := Nat.lt a b
    def gt (a b : Nat) : Bool := Nat.lt b a
    def lte (a b : Nat) : Bool := Nat.le a b
    def gte (a b : Nat) : Bool := Nat.le b a
}
defLens#
pub def Lens [Functor F] {F : Type -> Type} (S : Type) (T : Type) (A : Type) (B : Type) : Type
typeList#
pub type List A {
    empty,
    cons (a : A) (List A) : List A
}
instance_#
pub instance FromListLiteral List {
    def cons (a : A) (l : List A) : List A := List.cons a l
    def empty : List A := List.empty
}
defList.is_empty#
pub def List.is_empty (self : List A) : Bool
defList.append#
pub def List.append (a b : List A) : List A
classAppend#
pub class Append A {
    def append (a b : A) : A
}

Append b to value a

infixAppend.append#
pub infix (++)
defList.first#
pub def List.first (self : List A) : Option A
defList.last#
pub def List.last (self : List A) : Option A
defList.flatten#
pub def List.flatten (self : List (List A)) : List A
defList.tail#
pub def List.tail (l : List A) : List A
defList.map#
pub def List.map (f : A -> B) (self : List A) : List B
instance_#
pub instance Functor List {
    // `List.map` (not the recursive `Functor.map`) -- a match-arm PATTERN-
    // bound variable (`tail`, from `cons a tail => ...`) is never added to
    // `env` by `resolve_class_call_term`'s term walker (`lang/scope.mo`,
    // only `Term.lam`-introduced bindings are, see its own doc comment) --
    // a distinct gap from the bare-local-var one already fixed, caught by
    // the new fail-fast check (`no instance found for 'Functor.map'`) this
    // instance's own recursive call had been silently hitting. `List.map`
    // (just above) is the identical concrete implementation, already
    // correct and non-generic -- reuse it instead of chasing this gap here.
    def map (f : A -> B) (self : List A) : List B :=
        match self {
            empty => List.empty,
            cons a tail => List.cons (f a) (List.map f tail),
            _ => List.empty
        }
}
defList.flat_map#
pub def List.flat_map (f : A -> List B) (self : List A) : List B

Map each element to a list and concatenate the results.

instance_#
pub instance Applicative List {
    def pure (a : A) : List A := [a]

    def apply (fs : List (A -> B)) (xs : List A) : List B :=
        List.flat_map (fn g => List.map g xs) fs
}

List is the nondeterminism monad: bind runs the continuation on every element and concatenates, so apply is the cartesian product in order.

instance_#
pub instance Monad List {
    def pure (a : A) : List A := [a]

    def bind (xs : List A) (f : A -> List B) : List B := List.flat_map f xs
}
typeVec#
pub type Vec (len : Nat) A {
    nil : Vec Nat.zero A,
    cons (head : A) (tail : Vec len A) : Vec (Nat.succ len) A
}

A length-indexed vector: Vec len A is a list of exactly len elements of type A

deffun_apply#
pub def fun_apply (f : A -> B) (a : A) : B
infixfun_apply#
pub infix (<|)
defapply_fun#
pub def apply_fun (a : A) (f : A -> B) : B
infixapply_fun#
pub infix (|>)
classIndexedMonad#
pub class IndexedMonad (M : Type -> Type -> Type -> Type) {
    def pure (a : A) : M I I A
    def bind (a : M I J A) (f : A -> M J K B) : M I K B

    /// Map across the value (preserving indices)
    def map (f : A -> B) (ma : M I J A) : M I J B :=
        bind ma (fn a => pure (f a))

    /// Sequence two actions, discarding the first value
    def and_then (first : M I J A) (second : M J K B) : M I K B :=
        bind first (fn _ => second)

    /// Lift a pure value into the indexed monad at any index
    def lift (a : A) : M I I A := pure a
}

Indexed monad: M I J A I = initial index, J = final index, A = value

instance_#
pub instance {I : Type} [IndexedMonad M] Monad (M I I) {
    def pure (a : A) : M I I A := IndexedMonad.pure a
    def bind (a : M I I A) (f : A -> M I I B) : M I I B := IndexedMonad.bind a f
}

Any IndexedMonad M at equal indices (M I I) is a regular Monad. This bridge instance provides Monad (M I I) for every IndexedMonad M, enabling do-notation for indexed monads without type-checker changes.

classIndexedMonadState#
pub class IndexedMonadState (M : Type -> Type -> Type -> Type) {
    def get : M I I S
    def set (s : S) : M I I Unit
    def modify_get (f : S -> Pair S A) : M I I A
}

Indexed state monad: thread state S through an indexed monad M. State operations preserve the index (M I I), so they can be sequenced in any position without changing the protocol state. Single-param class (M only) — S is implicit forall, same as MonadState above.

classIndexedMonadLift#
pub class IndexedMonadLift (m : Type -> Type -> Type -> Type) (n : Type -> Type -> Type -> Type) {
    def monad_lift (a : m I J A) : n I J A
}

Lift computations from indexed monad m into indexed monad n

instance_#
pub instance Inhabited I64 { def default : I64 := 0 }
instance_#
pub instance Inhabited I32 { def default : I32 := 0i32 }
instance_#
pub instance Inhabited I16 { def default : I16 := 0i16 }
instance_#
pub instance Inhabited I8 { def default : I8 := 0i8 }
instance_#
pub instance Inhabited U64 { def default : U64 := 0u64 }
instance_#
pub instance Inhabited U32 { def default : U32 := 0u32 }
instance_#
pub instance Inhabited U16 { def default : U16 := 0u16 }
instance_#
pub instance Inhabited U8 { def default : U8 := 0u8 }
instance_#
pub instance Inhabited F64 { def default : F64 := 0.0 }
instance_#
pub instance Inhabited F32 { def default : F32 := 0.0f32 }
instance_#
pub instance Inhabited Bool { def default : Bool := Bool.false }
instance_#
pub instance Inhabited Unit { def default : Unit := Unit.unit }
instance_#
pub instance Inhabited String { def default : String := "" }
instance_#
pub instance Inhabited Ptr { def default : Ptr := Ptr.null }
instance_#
pub instance Inhabited Nat { def default : Nat := Nat.zero }
instance_#
pub instance {A : Type} Inhabited (List A) { def default : List A := List.empty }
instance_#
pub instance {A : Type} Inhabited (Option A) { def default : Option A := Option.none }