Derived terms
Lax149335.DerivedTerms · concepts/Lax149335/DerivedTerms.lean · lax-149335
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
The following terms are derived from the atomic functions and combinators of Definition 3.1. They are used to state the axioms of Section 4 and the results of the completeness proof.
- The unique term , co-pairing , commutativity and associativity of co-products.
- The list notation of Section 4.6: the empty list , , , , , the homomorphism combinator , and the concatenation of two terms with list outputs.
- The inverses of distributivity, and (Section 4.4).
- Definition 5.1 (Value). A value is a term of type . For a list value , the terms and prepend or append the output of to the output of (Section 5.2), and returns the first element of a list, or the output of for the empty list.
- Concatenation maps (Section 5.1). For a type constructor with one parameter, built from the parameter, , , and , the concatenation map lists all the elements of occurring in the input, from left to right. Similarly for type constructors with two parameters, with outputs in . In particular, is a concatenation map.
- The terms and of Table 1.
- The inverse of group prefix multiplication (Section 4.4), which maps to , where is the group identity.
Concept map
Lean source view on GitHub
| 1 | import Lax149335.Terms |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Derived terms |
| 6 | type: definition |
| 7 | --- |
| 8 | The following terms are derived from the atomic functions and combinators of |
| 9 | Definition 3.1. They are used to state the axioms of Section 4 and the results of the |
| 10 | completeness proof. |
| 11 | |
| 12 | - The unique term , co-pairing |
| 13 | , commutativity and associativity of co-products. |
| 14 | - The list notation of Section 4.6: the empty list , |
| 15 | , , |
| 16 | , , the homomorphism combinator |
| 17 | , and the concatenation |
| 18 | of two terms with list outputs. |
| 19 | - The inverses of distributivity, and (Section 4.4). |
| 20 | - **Definition 5.1 (Value).** A *value* is a term of type . For a list value , |
| 21 | the terms and prepend or append the output of to the output |
| 22 | of (Section 5.2), and returns the first element of a |
| 23 | list, or the output of for the empty list. |
| 24 | - *Concatenation maps* (Section 5.1). For a type constructor with one parameter, built |
| 25 | from the parameter, , , and , the concatenation map |
| 26 | lists all the elements of occurring in the input, from left |
| 27 | to right. Similarly for type constructors with two parameters, with outputs in |
| 28 | . In particular, |
| 29 | is a concatenation map. |
| 30 | - The terms and |
| 31 | of Table 1. |
| 32 | - The inverse of group prefix multiplication (Section 4.4), which maps |
| 33 | to , |
| 34 | where is the group identity. |
| 35 | |
| 36 | # Formalization notes |
| 37 | |
| 38 | The paper only asserts that a term for exists. Here it is defined |
| 39 | explicitly, following the appendix, by case analysis on the letters of the finite alphabet |
| 40 | that carries the group (`caseL`, `caseR`, `constFin`). |
| 41 | -/ |
| 42 | |
| 43 | namespace Lax149335.DerivedTerms |
| 44 | |
| 45 | open Lax149335.Types Lax149335.Terms |
| 46 | |
| 47 | namespace Term |
| 48 | |
| 49 | open Lax149335.Terms.Term |
| 50 | |
| 51 | /-- The unique function into the unit type, `A → 1`. -/ |
| 52 | def toUnit (A : Ty) : Term A Ty.unit := unitL A ⨟ fst Ty.unit A |
| 53 | |
| 54 | /-- Co-pairing, a derived combinator: `either f₁ f₂ = (f₁ + f₂); codiag`. -/ |
| 55 | def either {A₁ A₂ B : Ty} (f₁ : Term A₁ B) (f₂ : Term A₂ B) : Term (A₁ ⊕' A₂) B := |
| 56 | sumF f₁ f₂ ⨟ codiag B |
| 57 | |
| 58 | /-- Commutativity of the co-product, a derived term. -/ |
| 59 | def comm (A B : Ty) : Term (A ⊕' B) (B ⊕' A) := either (inr B A) (inl B A) |
| 60 | |
| 61 | /-- Associativity of the co-product, from left to right. -/ |
| 62 | def sumAssocR (A B C : Ty) : Term ((A ⊕' B) ⊕' C) (A ⊕' (B ⊕' C)) := |
| 63 | either (either (inl A (B ⊕' C)) (inl B C ⨟ inr A (B ⊕' C))) (inr B C ⨟ inr A (B ⊕' C)) |
| 64 | |
| 65 | /-- Associativity of the co-product, from right to left. -/ |
| 66 | def sumAssocL (A B C : Ty) : Term (A ⊕' (B ⊕' C)) ((A ⊕' B) ⊕' C) := |
| 67 | either (inl A B ⨟ inl (A ⊕' B) C) |
| 68 | (either (inr A B ⨟ inl (A ⊕' B) C) (inr (A ⊕' B) C)) |
| 69 | |
| 70 | /-- The empty list `[] : 1 → A*`, defined as `Left; cons`. -/ |
| 71 | def nilT (A : Ty) : Term Ty.unit A⋆ := inl Ty.unit (A ⊗ A⋆) ⨟ cons A |
| 72 | |
| 73 | /-- `prepend : A × A* → A*`, defined as `Right; cons`. -/ |
| 74 | def prepend (A : Ty) : Term (A ⊗ A⋆) A⋆ := inr Ty.unit (A ⊗ A⋆) ⨟ cons A |
| 75 | |
| 76 | /-- `append : A* × A → A*`, defined as `Right; snoc`. -/ |
| 77 | def append (A : Ty) : Term (A⋆ ⊗ A) A⋆ := inr Ty.unit (A⋆ ⊗ A) ⨟ snoc A |
| 78 | |
| 79 | /-- `pure : A → A*`, defined as `(id,1); id × []; prepend`. -/ |
| 80 | def pureT (A : Ty) : Term A A⋆ := |
| 81 | unitR A ⨟ prodF (Term.id A) (nilT A) ⨟ prepend A |
| 82 | |
| 83 | /-- `binconcat : A* × A* → A*`, defined as `(id × pure); prepend; concat`. -/ |
| 84 | def binconcat (A : Ty) : Term (A⋆ ⊗ A⋆) A⋆ := |
| 85 | prodF (Term.id A⋆) (pureT A⋆) ⨟ prepend A⋆ ⨟ concat A |
| 86 | |
| 87 | /-- The homomorphism combinator `hom f = f*; concat`. -/ |
| 88 | def homT {A B : Ty} (f : Term A B⋆) : Term A⋆ B⋆ := listF f ⨟ concat B |
| 89 | |
| 90 | /-- Concatenation of two functions with list outputs, `f ⊙ g = (f × g); binconcat`. -/ |
| 91 | def fdot {A₁ A₂ B : Ty} (f : Term A₁ B⋆) (g : Term A₂ B⋆) : Term (A₁ ⊗ A₂) B⋆ := |
| 92 | prodF f g ⨟ binconcat B |
| 93 | |
| 94 | /-- Notation `f ⊙ g` for the concatenation of two terms with list outputs. -/ |
| 95 | infixl:65 " ⊙ " => Term.fdot |
| 96 | |
| 97 | /-- The inverse of distributivity on the right, |
| 98 | `undistR = either (id × Left) (id × Right)`. -/ |
| 99 | def undistR (A B C : Ty) : Term ((A ⊗ B) ⊕' (A ⊗ C)) (A ⊗ (B ⊕' C)) := |
| 100 | either (prodF (Term.id A) (inl B C)) (prodF (Term.id A) (inr B C)) |
| 101 | |
| 102 | /-- The inverse of distributivity on the left. -/ |
| 103 | def undistL (A B C : Ty) : Term ((A ⊗ C) ⊕' (B ⊗ C)) ((A ⊕' B) ⊗ C) := |
| 104 | either (prodF (inl A B) (Term.id C)) (prodF (inr A B) (Term.id C)) |
| 105 | |
| 106 | -- Values and concatenation with values (Section 5.2) |
| 107 | |
| 108 | /-- **Definition 5.1 (Value).** A value is a term of type `1 → A`. -/ |
| 109 | abbrev Value (A : Ty) : Type := Term Ty.unit A |
| 110 | |
| 111 | /-- Pairing a value on the left with an arbitrary term: `(v,f) = (1,id); (v × f)`. -/ |
| 112 | def pairL {A B C : Ty} (v : Value C) (f : Term A B) : Term A (C ⊗ B) := |
| 113 | unitL A ⨟ prodF v f |
| 114 | |
| 115 | /-- Pairing a value on the right with an arbitrary term: `(f,v) = (id,1); (f × v)`. -/ |
| 116 | def pairR {A B C : Ty} (f : Term A B) (v : Value C) : Term A (B ⊗ C) := |
| 117 | unitR A ⨟ prodF f v |
| 118 | |
| 119 | /-- Concatenation of a list value on the left with a term with list outputs, `w · f`. -/ |
| 120 | def dotL {A B : Ty} (w : Value B⋆) (f : Term A B⋆) : Term A B⋆ := |
| 121 | pairL w f ⨟ binconcat B |
| 122 | |
| 123 | /-- Concatenation of a term with list outputs with a list value on the right, `f · w`. -/ |
| 124 | def dotR {A B : Ty} (f : Term A B⋆) (w : Value B⋆) : Term A B⋆ := |
| 125 | pairR f w ⨟ binconcat B |
| 126 | |
| 127 | /-- The singleton list value `[v] = v; pure`. -/ |
| 128 | def sing {A : Ty} (v : Value A) : Value A⋆ := v ⨟ pureT A |
| 129 | |
| 130 | /-- The *head term for `w`*: the first element of a list, or the value `w` if the list is |
| 131 | empty. -/ |
| 132 | def headT {A : Ty} (w : Value A) : Term A⋆ A := |
| 133 | uncons A ⨟ either w (fst A A⋆) |
| 134 | |
| 135 | -- Concatenation maps (Section 5.1) |
| 136 | |
| 137 | /-- Type constructors with one parameter, used to define concatenation maps. -/ |
| 138 | inductive TyF : Type |
| 139 | /-- The parameter itself. -/ |
| 140 | | param : TyF |
| 141 | /-- The unit type. -/ |
| 142 | | unit : TyF |
| 143 | /-- Product of two type constructors. -/ |
| 144 | | prod : TyF → TyF → TyF |
| 145 | /-- Co-product of two type constructors. -/ |
| 146 | | sum : TyF → TyF → TyF |
| 147 | /-- List of a type constructor. -/ |
| 148 | | list : TyF → TyF |
| 149 | |
| 150 | /-- The type `F(A)` obtained by substituting the type `A` for the parameter of `F`. -/ |
| 151 | def TyF.app : TyF → Ty → Ty |
| 152 | | .param, A => A |
| 153 | | .unit, _ => Ty.unit |
| 154 | | .prod F G, A => (F.app A) ⊗ (G.app A) |
| 155 | | .sum F G, A => (F.app A) ⊕' (G.app A) |
| 156 | | .list F, A => (F.app A)⋆ |
| 157 | |
| 158 | /-- **Concatenation maps** (Section 5.1): the term `F(A) ↣ A*` that concatenates all the |
| 159 | elements of the input into a single list, defined by induction on `F`. -/ |
| 160 | def TyF.concatMap : (F : TyF) → (A : Ty) → Term (F.app A) A⋆ |
| 161 | | .param, A => pureT A |
| 162 | | .unit, A => nilT A |
| 163 | | .prod F G, A => (F.concatMap A) ⊙ (G.concatMap A) |
| 164 | | .sum F G, A => either (F.concatMap A) (G.concatMap A) |
| 165 | | .list F, A => homT (F.concatMap A) |
| 166 | |
| 167 | /-- The type constructor `A ↦ Aᵏ`, the `k`-fold product of the parameter with itself. -/ |
| 168 | def TyF.pow : ℕ → TyF |
| 169 | | 0 => .unit |
| 170 | | (k + 1) => .prod .param (TyF.pow k) |
| 171 | |
| 172 | /-- The type constructor `A ↦ A⁰ + A¹ + ⋯ + Aᵏ`, i.e. `A^{<k+1}` in the notation of the |
| 173 | paper. -/ |
| 174 | def TyF.lt : ℕ → TyF |
| 175 | | 0 => TyF.pow 0 |
| 176 | | (k + 1) => .sum (TyF.lt k) (TyF.pow (k + 1)) |
| 177 | |
| 178 | /-- Type constructors with two parameters, used for the concatenation maps with values in |
| 179 | `(A + B)*` that occur in Axiom 15 and in the definition of `unsplit`. -/ |
| 180 | inductive TyF2 : Type |
| 181 | /-- The first parameter. -/ |
| 182 | | p1 : TyF2 |
| 183 | /-- The second parameter. -/ |
| 184 | | p2 : TyF2 |
| 185 | /-- The unit type. -/ |
| 186 | | unit : TyF2 |
| 187 | /-- Product of two type constructors. -/ |
| 188 | | prod : TyF2 → TyF2 → TyF2 |
| 189 | /-- Co-product of two type constructors. -/ |
| 190 | | sum : TyF2 → TyF2 → TyF2 |
| 191 | /-- List of a type constructor. -/ |
| 192 | | list : TyF2 → TyF2 |
| 193 | |
| 194 | /-- The type `F(A,B)`. -/ |
| 195 | def TyF2.app : TyF2 → Ty → Ty → Ty |
| 196 | | .p1, A, _ => A |
| 197 | | .p2, _, B => B |
| 198 | | .unit, _, _ => Ty.unit |
| 199 | | .prod F G, A, B => (F.app A B) ⊗ (G.app A B) |
| 200 | | .sum F G, A, B => (F.app A B) ⊕' (G.app A B) |
| 201 | | .list F, A, B => (F.app A B)⋆ |
| 202 | |
| 203 | /-- The concatenation map `F(A,B) ↣ (A+B)*`, which injects the elements of `A` and of `B` |
| 204 | into the co-product `A + B` and concatenates all of them. -/ |
| 205 | def TyF2.concatMap : (F : TyF2) → (A B : Ty) → Term (F.app A B) (A ⊕' B)⋆ |
| 206 | | .p1, A, B => inl A B ⨟ pureT (A ⊕' B) |
| 207 | | .p2, A, B => inr A B ⨟ pureT (A ⊕' B) |
| 208 | | .unit, A, B => nilT (A ⊕' B) |
| 209 | | .prod F G, A, B => (F.concatMap A B) ⊙ (G.concatMap A B) |
| 210 | | .sum F G, A, B => either (F.concatMap A B) (G.concatMap A B) |
| 211 | | .list F, A, B => homT (F.concatMap A B) |
| 212 | |
| 213 | /-- The inverse of `split`: it injects `A` and `B` into the co-product `A + B` and then |
| 214 | concatenates all resulting lists. -/ |
| 215 | def unsplit (A B : Ty) : Term (A⋆ ⊗ (B ⊗ A⋆)⋆) (A ⊕' B)⋆ := |
| 216 | TyF2.concatMap (.prod (.list .p1) (.list (.prod .p2 (.list .p1)))) A B |
| 217 | |
| 218 | -- The terms `shift` and `unshift` of Table 1 |
| 219 | |
| 220 | /-- The lift `shift : (A × B)* ⊸ 1 + A × (B × A)* × B`, obtained by composing `uncons`, |
| 221 | `assocR` and `shiftL`. -/ |
| 222 | def shift (A B : Ty) : Term ((A ⊗ B)⋆) (Ty.unit ⊕' (A ⊗ ((B ⊗ A)⋆ ⊗ B))) := |
| 223 | uncons (A ⊗ B) ⨟ |
| 224 | sumF (Term.id Ty.unit) (assocR A B ((A ⊗ B)⋆) ⨟ prodF (Term.id A) (shiftL B A)) |
| 225 | |
| 226 | /-- The drop `unshift : 1 + A × (B × A)* × B ⇒ (A × B)*`, the inverse of `shift`. -/ |
| 227 | def unshift (A B : Ty) : Term (Ty.unit ⊕' (A ⊗ ((B ⊗ A)⋆ ⊗ B))) ((A ⊗ B)⋆) := |
| 228 | sumF (Term.id Ty.unit) (prodF (Term.id A) (shiftR B A) ⨟ assocL A B ((A ⊗ B)⋆)) ⨟ cons (A ⊗ B) |
| 229 | |
| 230 | -- Terms for finite alphabets and the inverse of the group prefix operation |
| 231 | |
| 232 | /-- The value `1 → 1 + ⋯ + 1` that picks out a given letter of a finite alphabet. -/ |
| 233 | def constFin : {n : ℕ} → ⟦Ty.finAlph n⟧ → Value (Ty.finAlph n) |
| 234 | | 0, _ => Term.id Ty.unit |
| 235 | | (_ + 1), .inl _ => inl Ty.unit _ |
| 236 | | (_ + 1), .inr g => constFin g ⨟ inr Ty.unit _ |
| 237 | |
| 238 | /-- Case analysis on a letter of a finite alphabet that appears as the right component of a |
| 239 | product; it is derived using distributivity and co-pairing. -/ |
| 240 | def caseR : {n : ℕ} → {A B : Ty} → (⟦Ty.finAlph n⟧ → Term A B) → Term (A ⊗ Ty.finAlph n) B |
| 241 | | 0, A, _, t => fst A Ty.unit ⨟ t () |
| 242 | | (n + 1), A, _, t => |
| 243 | distR A Ty.unit (Ty.finAlph n) ⨟ |
| 244 | either (fst A Ty.unit ⨟ t (.inl ())) (caseR (fun g => t (.inr g))) |
| 245 | |
| 246 | /-- Case analysis on a letter of a finite alphabet that appears as the left component of a |
| 247 | product. -/ |
| 248 | def caseL : {n : ℕ} → {A B : Ty} → (⟦Ty.finAlph n⟧ → Term A B) → Term (Ty.finAlph n ⊗ A) B |
| 249 | | 0, A, _, t => snd Ty.unit A ⨟ t () |
| 250 | | (n + 1), A, _, t => |
| 251 | distL Ty.unit (Ty.finAlph n) A ⨟ |
| 252 | either (snd Ty.unit A ⨟ t (.inl ())) (caseL (fun g => t (.inr g))) |
| 253 | |
| 254 | /-- The term `(a,g) ↦ (g,(a,g))`, admissible because the group is a finite alphabet. -/ |
| 255 | def grepeat (A : Ty) (n : ℕ) : Term (A ⊗ Ty.finAlph n) (Ty.finAlph n ⊗ (A ⊗ Ty.finAlph n)) := |
| 256 | caseR (fun g => pairL (constFin g) (pairR (Term.id A) (constFin g))) |
| 257 | |
| 258 | /-- The term `(h,(g,a)) ↦ (a, h⁻¹ · g)`, admissible because the group is a finite |
| 259 | alphabet. -/ |
| 260 | def gdiv (A : Ty) {n : ℕ} (G : Group ⟦Ty.finAlph n⟧) : |
| 261 | Term (Ty.finAlph n ⊗ (Ty.finAlph n ⊗ A)) (A ⊗ Ty.finAlph n) := |
| 262 | caseL (fun h => caseL (fun g => pairR (Term.id A) (constFin (letI := G; h⁻¹ * g)))) |
| 263 | |
| 264 | /-- The unprefixing operation, the inverse of the group prefix multiplication: |
| 265 | `[(a₁,g₁),…,(aₙ,gₙ)] ↦ [(a₁,g₀⁻¹g₁),(a₂,g₁⁻¹g₂),…,(aₙ,gₙ₋₁⁻¹gₙ)]`, where `g₀` is the group |
| 266 | identity. -/ |
| 267 | def unpref (A : Ty) {n : ℕ} (G : Group ⟦Ty.finAlph n⟧) : |
| 268 | Term ((A ⊗ Ty.finAlph n)⋆) ((A ⊗ Ty.finAlph n)⋆) := |
| 269 | listF (grepeat A n) ⨟ |
| 270 | listF (assocL (Ty.finAlph n) A (Ty.finAlph n)) ⨟ |
| 271 | pairL (constFin (letI := G; (1 : ⟦Ty.finAlph n⟧))) (Term.id _) ⨟ |
| 272 | shiftL (Ty.finAlph n) (Ty.finAlph n ⊗ A) ⨟ |
| 273 | fst _ _ ⨟ listF (gdiv A G) |
| 274 | |
| 275 | end Term |
| 276 | |
| 277 | end Lax149335.DerivedTerms |
| 278 |
Formalization notes
The paper only asserts that a term for exists. Here it is defined explicitly, following the appendix, by case analysis on the letters of the finite alphabet that carries the group (, , ).
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments