Tuples, relations, and databases #
This file defines the basic relational model used throughout the library.
Main definitions #
Dependency graph
Equations
- t.repr x✝ = Std.Format.bracket "[" (Std.Format.joinSep (List.map (fun (i : Fin n) => reprArg (t i)) (List.finRange n)) (Std.Format.text ", ")) "]"
Instances For
Dependency graph
Equations
- Tuple.cast heq t = heq ▸ t
Instances For
Dependency graph
Dependency graph
Equations
- instReprTuple = { reprPrec := Tuple.repr }
Dependency graph
Equations
- instZeroTuple = { zero := fun (x : Fin n) => 0 }
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Instances For
Dependency graph
Equations
- Relation.cast heq r = heq ▸ r
Instances For
Dependency graph
Equations
- instAddRelation = { add := instAddRelation._aux_1 }
Dependency graph
Equations
- instSubRelation = { sub := instSubRelation._aux_1 }
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Equations
- instZeroRelation = { zero := ∅ }
Dependency graph
Dependency graph
Instances For
Dependency graph
Equations
- Database.find n s d = Database.find.f n s d
Instances For
Dependency graph
Equations
Instances For
Dependency graph
Binding a relation name, the I[R ↦ M] of a recursion's rounds.
A database is searched front to back, so a binding is a cons: it shadows
whatever the name had, and nothing else moves.
Instances For
Dependency graph
Equations
- sortedInsert x l = ⟨List.orderedIns (fun (x1 x2 : α) => x1 ≤ x2) x ↑l, ⋯⟩
Instances For
Dependency graph
Dependency graph
A multiset as a sorted list: the canonical reading of a relation as a
sequence. It is computable, where a choice through Multiset.toList is
not, and it is determined by the multiset, which is what lets two
sequences built from the same rows be recognized as the same sequence.
It is an insertion sort rather than Multiset.sort, which is defined by
well-founded recursion and does not reduce in the kernel: the evaluators
read a relation as a sequence through this, and a decide-checked
equation about a computed relation needs every step of it to reduce.
Equations
- sortList M = ↑(Multiset.foldr sortedInsert ⟨[], ⋯⟩ M)
Instances For
Dependency graph
Equations
- instToStringRelation = { toString := fun (r : Relation T n) => "\n".intercalate (List.map toString ↑(Multiset.foldr sortedInsert ⟨[], ⋯⟩ r)) ++ "\n" }