ベクター
module vector where open import bottom-type open import fin open import identity-type open import list hiding (singleton; append) open import natural-number
infixr 50 _∷_ data Vec (X : Set) : ℕ → Set where [] : Vec X zero _∷_ : ∀ {n} → X → Vec X n → Vec X (suc n) private variable X : Set m n : ℕ Vec0-[] : (xs : Vec X zero) → xs = [] Vec0-[] [] = refl singleton : X → Vec X (suc zero) singleton x = x ∷ [] append : Vec X m → Vec X n → Vec X (m +ℕ n) append [] ys = ys append (x ∷ xs) ys = x ∷ append xs ys Vec→List : Vec X n → List X Vec→List [] = [] Vec→List (x ∷ xs) = x ∷ Vec→List xs
lookup′ : Fin n → X → Vec X (predℕ n) → X lookup′ zero x xs = x lookup′ (suc p) _ (y ∷ xs) = lookup′ p y xs lookup : Fin n → Vec X n → X lookup p [] = absurd (¬Fin0 p) lookup p (x ∷ xs) = lookup′ p x xs
lookup-zero : ∀ x (xs : Vec X n) → lookup zero (x ∷ xs) = x lookup-zero x xs = refl lookup-suc : ∀ p x (xs : Vec X n) → lookup (suc p) (x ∷ xs) = lookup p xs lookup-suc p x (y ∷ xs) = refl
function→Vec : (Fin n → X) → Vec X n function→Vec {n = zero} f = [] function→Vec {n = suc n} f = f zero ∷ function→Vec {n = n} λ p → f (suc p) lookup-function→Vec : ∀ p (f : Fin n → X) → lookup p (function→Vec f) = f p lookup-function→Vec zero f = refl lookup-function→Vec (suc p) f = k1 ∙ k2 where k1 : lookup (suc p) (function→Vec f) = lookup p (function→Vec λ p → f (suc p)) k1 = lookup-suc p (f zero) (function→Vec λ p → f (suc p)) k2 : lookup p (function→Vec λ p → f (suc p)) = f (suc p) k2 = lookup-function→Vec p (λ q → f (suc q)) function→Vec-pres-pointwise-equality : ∀ {n f g} → (∀ (p : Fin n) → f p = g p) → function→Vec {X = X} f = function→Vec g function→Vec-pres-pointwise-equality {n = zero} H = refl function→Vec-pres-pointwise-equality {n = suc n} H = cong₂ _∷_ (H zero) (function→Vec-pres-pointwise-equality {n = n} (λ p → H (suc p))) function→Vec-lookup : ∀ (xs : Vec X n) → function→Vec (λ p → lookup p xs) = xs function→Vec-lookup [] = refl function→Vec-lookup {X = X} {n = n} (x ∷ xs) = r ∙ q where p1 : function→Vec (λ p → lookup p xs) = xs p1 = function→Vec-lookup xs q : x ∷ function→Vec (λ p → lookup p xs) = x ∷ xs q = cong (x ∷_) p1 r : Id (Vec X n) (x ∷ function→Vec (λ p → lookup (suc p) (x ∷ xs))) (x ∷ function→Vec (λ p → lookup p xs)) r = cong (x ∷_) (function→Vec-pres-pointwise-equality (λ p → lookup-suc p x xs))