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 nth 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 := _}