Chuangjie Xu, November 2026
\begin{code}
{-# OPTIONS --without-K --safe #-}
module InductiveBars.Sequences where
open import MLTT.Spartan
open import MLTT.List
open import Naturals.Order
length-++-right : {A : 𝓤 ̇} (s t : List A)
→ length t ≤ℕ length (s ++ t)
length-++-right [] t = ≤-refl (length t)
length-++-right (a ∷ s) t
= ≤-trans (length t) (length (s ++ t)) (succ (length (s ++ t)))
(length-++-right s t) (≤-succ (length (s ++ t)))
_extends_ : {A : 𝓤 ̇} → (ℕ → A) → List A → 𝓤 ̇
α extends [] = 𝟙
α extends (a ∷ s) = (α 0 = a) × ((α ∘ succ) extends s)
extends-++ : {A : 𝓤 ̇} (α : ℕ → A) (s t : List A)
→ α extends (s ++ t) → α extends s
extends-++ α [] t e = ⋆
extends-++ α (_ ∷ s) t e = pr₁ e , extends-++ (α ∘ succ) s t (pr₂ e)
extends-next : {A : 𝓤 ̇} (α : ℕ → A) (s : List A)
→ α extends s
→ α extends (s ++ [ α (length s) ])
extends-next α [] e = refl , ⋆
extends-next α (_ ∷ s) (p , q) = p , extends-next (α ∘ succ) s q
infixr 2 _++∞_
_++∞_ : {A : 𝓤 ̇} → List A → (ℕ → A) → (ℕ → A)
([] ++∞ α) i = α i
((a ∷ _) ++∞ α) 0 = a
((_ ∷ s) ++∞ α) (succ i) = (s ++∞ α) i
++∞-extends : {A : 𝓤 ̇} (s : List A) (α : ℕ → A)
→ (s ++∞ α) extends s
++∞-extends [] α = ⋆
++∞-extends (_ ∷ s) α = refl , ++∞-extends s α
pad-with : {A : 𝓤 ̇} → A → List A → ℕ → A
pad-with a s = s ++∞ (λ _ → a)
pad : List ℕ → (ℕ → ℕ)
pad = pad-with 0
pad-extends : {A : 𝓤 ̇} {a : A} → (s : List A) → (pad-with a s) extends s
pad-extends {a = a} s = ++∞-extends s (λ _ → a)
prefix : {A : 𝓤 ̇} → ℕ → (ℕ → A) → List A
prefix 0 α = []
prefix (succ n) α = α 0 ∷ prefix n (α ∘ succ)
extends-prefix : {A : 𝓤 ̇} (α : ℕ → A) (n : ℕ) → α extends (prefix n α)
extends-prefix α 0 = ⋆
extends-prefix α (succ n) = refl , extends-prefix (α ∘ succ) n
extends-prefix-decomposition
: {A : 𝓤 ̇} (α : ℕ → A) (s : List A) (n : ℕ)
→ α extends s
→ n ≤ℕ length s
→ Σ t ꞉ List A , prefix n α ++ t = s
extends-prefix-decomposition α s 0 _ _ = s , refl
extends-prefix-decomposition α [] (succ n) _ ()
extends-prefix-decomposition α (a ∷ s) (succ n) (refl , e) r
using (t , p) ← extends-prefix-decomposition (α ∘ succ) s n e r
= t , ap (α 0 ∷_) p
lookup : {A : 𝓤 ̇} (s : List A) {i : ℕ} → i <ℕ length s → A
lookup [] ()
lookup (a ∷ s) {0} ⋆ = a
lookup (a ∷ s) {succ i} r = lookup s r
extends-lookup : {A : 𝓤 ̇} (s : List A) (i : ℕ) (r : i <ℕ length s)
→ (α : ℕ → A) → α extends s
→ α i = lookup s r
extends-lookup [] _ ()
extends-lookup (n ∷ s) 0 r α e = pr₁ e
extends-lookup (n ∷ s) (succ i) r α e
= extends-lookup s i r (α ∘ succ) (pr₂ e)
finite-upper-bound : (α : ℕ → ℕ) (k : ℕ)
→ Σ M ꞉ ℕ , ((i : ℕ) → i ≤ℕ k → α i ≤ℕ M)
finite-upper-bound α 0 = α 0 , upper
where
upper : (i : ℕ) → i ≤ℕ 0 → α i ≤ℕ α 0
upper 0 r = ≤-refl (α 0)
upper (succ i) ()
finite-upper-bound α (succ k)
using (M , upper) ← finite-upper-bound (α ∘ succ) k
= M' , upper'
where
M' : ℕ
M' = max M (α 0)
upper' : (i : ℕ) → i ≤ℕ succ k → α i ≤ℕ M'
upper' 0 r = max-≤-upper-bound' (α 0) M
upper' (succ i) r = ≤-trans (α (succ i)) M M'
(upper i r)
(max-≤-upper-bound M (α 0))
infix 30 _≤¹_
_≤¹_ : (ℕ → ℕ) → (ℕ → ℕ) → 𝓤₀ ̇
α ≤¹ δ = (i : ℕ) → α i ≤ℕ δ i
_=⦅_⦆_ : {A : 𝓤 ̇} → (ℕ → A) → ℕ → (ℕ → A) → 𝓤 ̇
α =⦅ 0 ⦆ β = 𝟙
α =⦅ succ n ⦆ β = (α 0 = β 0) × (α ∘ succ) =⦅ n ⦆ (β ∘ succ)
=⦅⦆-≤ : {A : 𝓤 ̇} (α β : ℕ → A) {m n : ℕ} → m ≤ℕ n
→ α =⦅ n ⦆ β → α =⦅ m ⦆ β
=⦅⦆-≤ α β {0} {n} ⋆ _ = ⋆
=⦅⦆-≤ α β {succ m} {0} ()
=⦅⦆-≤ α β {succ m} {succ n} r e
= pr₁ e , =⦅⦆-≤ (α ∘ succ) (β ∘ succ) r (pr₂ e)
agreement-preserves-extension
: {A : 𝓤 ̇} (α β : ℕ → A) (s : List A)
→ α extends s
→ α =⦅ length s ⦆ β
→ β extends s
agreement-preserves-extension α β [] eαs es = ⋆
agreement-preserves-extension α β (n ∷ s) (refl , p) (e , q) = e' , IH
where
e' : β 0 = α 0
e' = e ⁻¹
IH : (β ∘ succ) extends s
IH = agreement-preserves-extension (α ∘ succ) (β ∘ succ) s p q
agreement-implies-extends-prefix
: {A : 𝓤 ̇} (α β : ℕ → A) (n : ℕ)
→ α =⦅ n ⦆ β
→ β extends (prefix n α)
agreement-implies-extends-prefix α β 0 e = ⋆
agreement-implies-extends-prefix α β (succ n) (p , q)
= (p ⁻¹) , agreement-implies-extends-prefix (α ∘ succ) (β ∘ succ) n q
extends-prefix-implies-agreement
: {A : 𝓤 ̇} (α β : ℕ → A) (n : ℕ)
→ β extends (prefix n α)
→ α =⦅ n ⦆ β
extends-prefix-implies-agreement α β 0 e = ⋆
extends-prefix-implies-agreement α β (succ n) (p , q)
= (p ⁻¹) , extends-prefix-implies-agreement (α ∘ succ) (β ∘ succ) n q
\end{code}