Skip to content

ベクター

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))