Additional theorems and definitions about the vector
type #
This file introduces the infix notation ::ᵥ
for vector.cons
.
Equations
- vector.inhabited = {default := vector.of_fn (λ (_x : fin n), default)}
The empty vector
is a subsingleton
.
The natural equivalence between length-n
vectors and functions from fin n
.
Equations
- equiv.vector_equiv_fin α n = {to_fun := vector.nth n, inv_fun := vector.of_fn n, left_inv := _, right_inv := _}
The tail
of a nil
vector is nil
.
The tail
of a vector made up of one element is nil
.
Mapping under id
does not change a vector.
Accessing the nth
element of a vector made up
of one element x : α
is x
itself.
Construct a vector β (n + 1)
from a vector α n
by scanning f : β → α → β
from the "left", that is, from 0 to fin.last n
, using b : β
as the starting value.
Equations
- vector.scanl f b v = ⟨list.scanl f b v.to_list, _⟩
Providing an empty vector to scanl
gives the starting value b : β
.
The recursive step of scanl
splits a vector x ::ᵥ v : vector α (n + 1)
into the provided starting value b : β
and the recursed scanl
f b x : β
as the starting value.
This lemma is the cons
version of scanl_nth
.
The underlying list
of a vector
after a scanl
is the list.scanl
of the underlying list
of the original vector
.
The to_list
of a vector
after a scanl
is the list.scanl
of the to_list
of the original vector
.
The recursive step of scanl
splits a vector made up of a single element
x ::ᵥ nil : vector α 1
into a vector
of the provided starting value b : β
and the mapped f b x : β
as the last value.
The first element of scanl
of a vector v : vector α n
,
retrieved via head
, is the starting value b : β
.
For an index i : fin n
, the nth
element of scanl
of a
vector v : vector α n
at i.succ
, is equal to the application
function f : β → α → β
of the i.cast_succ
element of
scanl f b v
and nth v i
.
This lemma is the nth
version of scanl_cons
.
Monadic analog of vector.of_fn
.
Given a monadic function on fin n
, return a vector α n
inside the monad.
Equations
- vector.m_of_fn f = f 0 >>= λ (a : α), vector.m_of_fn (λ (i : fin n), f i.succ) >>= λ (v : vector α n), pure (a::ᵥv)
- vector.m_of_fn f = pure vector.nil
Apply a monadic function to each component of a vector, returning a vector inside the monad.
Equations
- vector.mmap f xs = f xs.head >>= λ (h' : β), vector.mmap f xs.tail >>= λ (t' : vector β n), pure (h'::ᵥt')
- vector.mmap f xs = pure vector.nil
Define C v
by induction on v : vector α n
.
This function has two arguments: h_nil
handles the base case on C nil
,
and h_cons
defines the inductive step using ∀ x : α, C w → C (x ::ᵥ w)
.
Equations
- v.induction_on h_nil h_cons = nat.rec (λ (v : vector α 0), subtype.cases_on v (λ (v_val : list α) (v_property : v_val.length = 0), v_val.cases_on (λ (v_property : list.nil.length = 0), v_property.dcases_on (λ (a : 0 = 0) (H_2 : v_property == vector.induction_on._proof_1), h_nil) _ _) (λ (v_val_hd : α) (v_val_tl : list α) (v_property : (v_val_hd :: v_val_tl).length = 0), v_property.dcases_on (λ (a : 0 = (v_val_tl.length.add 0).succ), nat.no_confusion a) _ _) v_property)) (λ (n : ℕ) (ih : Π (v : vector α n), C v) (v : vector α n.succ), subtype.cases_on v (λ (v_val : list α) (v_property : v_val.length = n.succ), v_val.cases_on (λ (v_property : list.nil.length = n.succ), v_property.dcases_on (λ (a : n.succ = 0), nat.no_confusion a) _ _) (λ (a : α) (v : list α) (v_property : (a :: v).length = n.succ), h_cons (ih ⟨v, _⟩)) v_property)) n v
Define C v w
by induction on a pair of vectors v : vector α n
and w : vector β n
.
Equations
- v.induction_on₂ w h_nil h_cons = nat.rec (λ (v : vector α 0) (w : vector β 0), subtype.cases_on v (λ (v_val : list α) (v_property : v_val.length = 0), v_val.cases_on (λ (v_property : list.nil.length = 0), v_property.dcases_on (λ (a : 0 = 0) (H_2 : v_property == vector.induction_on₂._proof_1), subtype.cases_on w (λ (w_val : list β) (w_property : w_val.length = 0), w_val.cases_on (λ (w_property : list.nil.length = 0), w_property.dcases_on (λ (a : 0 = 0) (H_2 : w_property == vector.induction_on₂._proof_2), h_nil) _ _) (λ (w_val_hd : β) (w_val_tl : list β) (w_property : (w_val_hd :: w_val_tl).length = 0), w_property.dcases_on (λ (a : 0 = (w_val_tl.length.add 0).succ), nat.no_confusion a) _ _) w_property)) _ _) (λ (v_val_hd : α) (v_val_tl : list α) (v_property : (v_val_hd :: v_val_tl).length = 0), v_property.dcases_on (λ (a : 0 = (v_val_tl.length.add 0).succ), nat.no_confusion a) _ _) v_property)) (λ (n : ℕ) (ih : Π (v : vector α n) (w : vector β n), C v w) (v : vector α n.succ) (w : vector β n.succ), subtype.cases_on v (λ (v_val : list α) (v_property : v_val.length = n.succ), v_val.cases_on (λ (v_property : list.nil.length = n.succ), v_property.dcases_on (λ (a : n.succ = 0), nat.no_confusion a) _ _) (λ (a : α) (v : list α) (v_property : (a :: v).length = n.succ), subtype.cases_on w (λ (w_val : list β) (w_property : w_val.length = n.succ), w_val.cases_on (λ (w_property : list.nil.length = n.succ), w_property.dcases_on (λ (a_1 : n.succ = 0), nat.no_confusion a_1) _ _) (λ (b : β) (w : list β) (w_property : (b :: w).length = n.succ), h_cons (ih ⟨v, _⟩ ⟨w, _⟩)) w_property)) v_property)) n v w
Define C u v w
by induction on a triplet of vectors
u : vector α n
, v : vector β n
, and w : vector γ b
.
Equations
- u.induction_on₃ v w h_nil h_cons = nat.rec (λ (u : vector α 0) (v : vector β 0) (w : vector γ 0), subtype.cases_on u (λ (u_val : list α) (u_property : u_val.length = 0), u_val.cases_on (λ (u_property : list.nil.length = 0), u_property.dcases_on (λ (a : 0 = 0) (H_2 : u_property == vector.induction_on₃._proof_1), subtype.cases_on v (λ (v_val : list β) (v_property : v_val.length = 0), v_val.cases_on (λ (v_property : list.nil.length = 0), v_property.dcases_on (λ (a : 0 = 0) (H_2 : v_property == vector.induction_on₃._proof_2), subtype.cases_on w (λ (w_val : list γ) (w_property : w_val.length = 0), w_val.cases_on (λ (w_property : list.nil.length = 0), w_property.dcases_on (λ (a : 0 = 0) (H_2 : w_property == vector.induction_on₃._proof_3), h_nil) _ _) (λ (w_val_hd : γ) (w_val_tl : list γ) (w_property : (w_val_hd :: w_val_tl).length = 0), w_property.dcases_on (λ (a : 0 = (w_val_tl.length.add 0).succ), nat.no_confusion a) _ _) w_property)) _ _) (λ (v_val_hd : β) (v_val_tl : list β) (v_property : (v_val_hd :: v_val_tl).length = 0), v_property.dcases_on (λ (a : 0 = (v_val_tl.length.add 0).succ), nat.no_confusion a) _ _) v_property)) _ _) (λ (u_val_hd : α) (u_val_tl : list α) (u_property : (u_val_hd :: u_val_tl).length = 0), u_property.dcases_on (λ (a : 0 = (u_val_tl.length.add 0).succ), nat.no_confusion a) _ _) u_property)) (λ (n : ℕ) (ih : Π (u : vector α n) (v : vector β n) (w : vector γ n), C u v w) (u : vector α n.succ) (v : vector β n.succ) (w : vector γ n.succ), subtype.cases_on u (λ (u_val : list α) (u_property : u_val.length = n.succ), u_val.cases_on (λ (u_property : list.nil.length = n.succ), u_property.dcases_on (λ (a : n.succ = 0), nat.no_confusion a) _ _) (λ (a : α) (u : list α) (u_property : (a :: u).length = n.succ), subtype.cases_on v (λ (v_val : list β) (v_property : v_val.length = n.succ), v_val.cases_on (λ (v_property : list.nil.length = n.succ), v_property.dcases_on (λ (a_1 : n.succ = 0), nat.no_confusion a_1) _ _) (λ (b : β) (v : list β) (v_property : (b :: v).length = n.succ), subtype.cases_on w (λ (w_val : list γ) (w_property : w_val.length = n.succ), w_val.cases_on (λ (w_property : list.nil.length = n.succ), w_property.dcases_on (λ (a_1 : n.succ = 0), nat.no_confusion a_1) _ _) (λ (c : γ) (w : list γ) (w_property : (c :: w).length = n.succ), h_cons (ih ⟨u, _⟩ ⟨v, _⟩ ⟨w, _⟩)) w_property)) v_property)) u_property)) n u v w
Cast a vector to an array.
Equations
- vector.to_array ⟨xs, h⟩ = cast _ xs.to_array
v.insert_nth a i
inserts a
into the vector v
at position i
(and shifting later components to the right).
Equations
- vector.insert_nth a i v = ⟨list.insert_nth ↑i a v.val, _⟩
update_nth v n a
replaces the n
th element of v
with a
Equations
- v.update_nth i a = ⟨v.val.update_nth i.val a, _⟩
Apply an applicative function to each component of a vector.
Equations
- vector.traverse f ⟨v, Hv⟩ = cast _ (traverse_aux f v)
Equations
- vector.flip.traversable = {to_functor := {map := λ (α β : Type u), vector.map, map_const := λ (α β : Type u), vector.map ∘ function.const β}, traverse := vector.traverse n}
Equations
- vector.flip.is_lawful_traversable = {to_is_lawful_functor := _, id_traverse := _, comp_traverse := _, traverse_eq_map_id := _, naturality := _}