Documentation

Mathlib.Data.Fin.VecNotation

Matrix and vector notation #

This file defines notation for vectors and matrices. Given a b c d : α, the notation allows us to write ![a, b, c, d] : Fin 4 → α. Nesting vectors gives coefficients of a matrix, so ![![a, b], ![c, d]] : Fin 2 → Fin 2 → α. In later files we introduce !![a, b; c, d] as notation for Matrix.of ![![a, b], ![c, d]].

Main definitions #

Implementation notes #

The simp lemmas require that one of the arguments is of the form vecCons _ _. This ensures simp works with entries only when (some) entries are already given. In other words, this notation will only appear in the output of simp if it already appears in the input.

Notations #

The main new notation is ![a, b], which gets expanded to vecCons a (vecCons b vecEmpty).

Examples #

Examples of usage can be found in the MathlibTest/matrix.lean file.

def Matrix.vecEmpty {α : Type u} :
Fin 0α

![] is the vector with no entries.

Equations
    Instances For
      def Matrix.vecCons {α : Type u} {n : } (h : α) (t : Fin nα) :
      Fin n.succα

      vecCons h t prepends an entry h to a vector t.

      The inverse functions are vecHead and vecTail. The notation ![a, b, ...] expands to vecCons a (vecCons b ...).

      Equations
        Instances For

          ![...] notation is used to construct a vector Fin n → α using Matrix.vecEmpty and Matrix.vecCons.

          For instance, ![a, b, c] : Fin 3 is syntax for vecCons a (vecCons b (vecCons c vecEmpty)).

          Note that this should not be used as syntax for Matrix as it generates a term with the wrong type. The !![a, b; c, d] syntax (provided by Matrix.matrixNotation) should be used instead.

          Equations
            Instances For

              Unexpander for the ![x, y, ...] notation.

              Equations
                Instances For

                  Unexpander for the ![] notation.

                  Equations
                    Instances For
                      def Matrix.vecHead {α : Type u} {n : } (v : Fin n.succα) :
                      α

                      vecHead v gives the first entry of the vector v

                      Equations
                        Instances For
                          def Matrix.vecTail {α : Type u} {n : } (v : Fin n.succα) :
                          Fin nα

                          vecTail v gives a vector consisting of all entries of v except the first

                          Equations
                            Instances For
                              instance PiFin.hasRepr {α : Type u} {n : } [Repr α] :
                              Repr (Fin nα)

                              Use ![...] notation for displaying a vector Fin n → α, for example:

                              #eval ![1, 2] + ![3, 4] -- ![4, 6]
                              
                              Equations
                                theorem Matrix.empty_eq {α : Type u} (v : Fin 0α) :
                                v = ![]
                                @[simp]
                                theorem Matrix.head_fin_const {α : Type u} {n : } (a : α) :
                                (vecHead fun (x : Fin (n + 1)) => a) = a
                                @[simp]
                                theorem Matrix.cons_val_zero {α : Type u} {m : } (x : α) (u : Fin mα) :
                                vecCons x u 0 = x
                                theorem Matrix.cons_val_zero' {α : Type u} {m : } (h : 0 < m.succ) (x : α) (u : Fin mα) :
                                vecCons x u 0, h = x
                                @[simp]
                                theorem Matrix.cons_val_succ {α : Type u} {m : } (x : α) (u : Fin mα) (i : Fin m) :
                                vecCons x u i.succ = u i
                                @[simp]
                                theorem Matrix.cons_val_succ' {α : Type u} {m i : } (h : i.succ < m.succ) (x : α) (u : Fin mα) :
                                vecCons x u i.succ, h = u i,

                                Parses a chain of Matrix.vecCons calls into elements, leaving everything else in the tail.

                                let ⟨xs, tailn, tail⟩ ← matchVecConsPrefix n e decomposes e : Fin n → _ in the form vecCons x₀ <| ... <| vecCons xₙ <| tail where tail : Fin tailn → _.

                                A simproc that handles terms of the form Matrix.vecCons a f i where i is a numeric literal.

                                In practice, this is most effective at handling ![a, b, c] i-style terms.

                                Equations
                                  Instances For
                                    @[simp]
                                    theorem Matrix.head_cons {α : Type u} {m : } (x : α) (u : Fin mα) :
                                    vecHead (vecCons x u) = x
                                    @[simp]
                                    theorem Matrix.tail_cons {α : Type u} {m : } (x : α) (u : Fin mα) :
                                    vecTail (vecCons x u) = u
                                    theorem Matrix.empty_val' {α : Type u} {n' : Type u_1} (j : n') :
                                    (fun (i : Fin 0) => ![] i j) = ![]
                                    @[simp]
                                    theorem Matrix.cons_head_tail {α : Type u} {m : } (u : Fin m.succα) :
                                    @[simp]
                                    theorem Matrix.range_cons {α : Type u} {n : } (x : α) (u : Fin nα) :
                                    @[simp]
                                    theorem Matrix.range_empty {α : Type u} (u : Fin 0α) :
                                    theorem Matrix.range_cons_empty {α : Type u} (x : α) (u : Fin 0α) :
                                    theorem Matrix.range_cons_cons_empty {α : Type u} (x y : α) (u : Fin 0α) :
                                    theorem Matrix.vecCons_const {α : Type u} {n : } (a : α) :
                                    (vecCons a fun (x : Fin n) => a) = fun (x : Fin n.succ) => a
                                    theorem Matrix.vec_single_eq_const {α : Type u} (a : α) :
                                    ![a] = fun (x : Fin (Nat.succ 0)) => a
                                    @[simp]
                                    theorem Matrix.cons_val_one {α : Type u} {m : } (x : α) (u : Fin m.succα) :
                                    vecCons x u 1 = u 0

                                    ![a, b, ...] 1 is equal to b.

                                    The simplifier needs a special lemma for length ≥ 2, in addition to cons_val_succ, because 1 : Fin 1 = 0 : Fin 1.

                                    theorem Matrix.cons_val_two {α : Type u} {m : } (x : α) (u : Fin m.succ.succα) :
                                    theorem Matrix.cons_val_three {α : Type u} {m : } (x : α) (u : Fin m.succ.succ.succα) :
                                    theorem Matrix.cons_val_four {α : Type u} {m : } (x : α) (u : Fin m.succ.succ.succ.succα) :
                                    @[simp]
                                    theorem Matrix.cons_val_fin_one {α : Type u} (x : α) (u : Fin 0α) (i : Fin 1) :
                                    vecCons x u i = x
                                    theorem Matrix.cons_fin_one {α : Type u} (x : α) (u : Fin 0α) :
                                    vecCons x u = fun (x_1 : Fin (Nat.succ 0)) => x
                                    def PiFin.mkLiteralQ {u : Lean.Level} {α : Q(Type u)} {n : } (elems : Fin nQ(«$α»)) :
                                    Q(Fin «$n»«$α»)

                                    mkVecLiteralQ ![x, y, z] produces the term q(![$x, $y, $z]).

                                    Equations
                                      Instances For
                                        @[irreducible]
                                        def PiFin.mkLiteralQ.loop {u : Lean.Level} {α : Q(Type u)} {n : } (elems : Fin nQ(«$α»)) (i : ) (hi : i n) (rest : Q(Fin «$i»«$α»)) :
                                        let i' := i + 1; Q(Fin «$i'»«$α»)
                                        Equations
                                          Instances For
                                            instance PiFin.toExpr {α : Type u} [Lean.ToLevel] [Lean.ToExpr α] (n : ) :
                                            Lean.ToExpr (Fin nα)
                                            Equations

                                              bit0 and bit1 indices #

                                              The following definitions and simp lemmas are used to allow numeral-indexed element of a vector given with matrix notation to be extracted by simp in Lean 3 (even when the numeral is larger than the number of elements in the vector, which is taken modulo that number of elements by virtue of the semantics of bit0 and bit1 and of addition on Fin n).

                                              def Matrix.vecAppend {m n : } {α : Type u_1} {o : } (ho : o = m + n) (u : Fin mα) (v : Fin nα) :
                                              Fin oα

                                              vecAppend ho u v appends two vectors of lengths m and n to produce one of length o = m + n. This is a variant of Fin.append with an additional ho argument, which provides control of definitional equality for the vector length.

                                              This turns out to be helpful when providing simp lemmas to reduce ![a, b, c] n, and also means that vecAppend ho u v 0 is valid. Fin.append u v 0 is not valid in this case because there is no Zero (Fin (m + n)) instance.

                                              Equations
                                                Instances For
                                                  theorem Matrix.vecAppend_eq_ite {m n : } {α : Type u_1} {o : } (ho : o = m + n) (u : Fin mα) (v : Fin nα) :
                                                  vecAppend ho u v = fun (i : Fin o) => if h : i < m then u i, h else v i - m,
                                                  @[simp]
                                                  theorem Matrix.vecAppend_apply_zero {m n : } {α : Type u_1} {o : } (ho : o + 1 = m + 1 + n) (u : Fin (m + 1)α) (v : Fin nα) :
                                                  vecAppend ho u v 0 = u 0
                                                  @[simp]
                                                  theorem Matrix.empty_vecAppend {α : Type u} {n : } (v : Fin nα) :
                                                  vecAppend ![] v = v
                                                  @[simp]
                                                  theorem Matrix.cons_vecAppend {α : Type u} {m n o : } (ho : o + 1 = m + 1 + n) (x : α) (u : Fin mα) (v : Fin nα) :
                                                  vecAppend ho (vecCons x u) v = vecCons x (vecAppend u v)
                                                  def Matrix.vecAlt0 {α : Type u} {m n : } (hm : m = n + n) (v : Fin mα) (k : Fin n) :
                                                  α

                                                  vecAlt0 v gives a vector with half the length of v, with only alternate elements (even-numbered).

                                                  Equations
                                                    Instances For
                                                      def Matrix.vecAlt1 {α : Type u} {m n : } (hm : m = n + n) (v : Fin mα) (k : Fin n) :
                                                      α

                                                      vecAlt1 v gives a vector with half the length of v, with only alternate elements (odd-numbered).

                                                      Equations
                                                        Instances For
                                                          theorem Matrix.vecAlt0_vecAppend {α : Type u} {n : } (v : Fin nα) :
                                                          vecAlt0 (vecAppend v v) = v fun (n_1 : Fin n) => n_1 + n_1
                                                          theorem Matrix.vecAlt1_vecAppend {α : Type u} {n : } (v : Fin (n + 1)α) :
                                                          vecAlt1 (vecAppend v v) = v fun (n_1 : Fin (n + 1)) => n_1 + n_1 + 1
                                                          @[simp]
                                                          theorem Matrix.vecHead_vecAlt0 {α : Type u} {m n : } (hm : m + 2 = n + 1 + (n + 1)) (v : Fin (m + 2)α) :
                                                          vecHead (vecAlt0 hm v) = v 0
                                                          @[simp]
                                                          theorem Matrix.vecHead_vecAlt1 {α : Type u} {m n : } (hm : m + 2 = n + 1 + (n + 1)) (v : Fin (m + 2)α) :
                                                          vecHead (vecAlt1 hm v) = v 1
                                                          theorem Matrix.cons_vec_bit0_eq_alt0 {α : Type u} {n : } (x : α) (u : Fin nα) (i : Fin (n + 1)) :
                                                          vecCons x u (i + i) = vecAlt0 (vecAppend (vecCons x u) (vecCons x u)) i
                                                          theorem Matrix.cons_vec_bit1_eq_alt1 {α : Type u} {n : } (x : α) (u : Fin nα) (i : Fin (n + 1)) :
                                                          vecCons x u (i + i + 1) = vecAlt1 (vecAppend (vecCons x u) (vecCons x u)) i
                                                          @[simp]
                                                          theorem Matrix.cons_vecAlt0 {α : Type u} {m n : } (h : m + 1 + 1 = n + 1 + (n + 1)) (x y : α) (u : Fin mα) :
                                                          vecAlt0 h (vecCons x (vecCons y u)) = vecCons x (vecAlt0 u)
                                                          @[simp]
                                                          theorem Matrix.empty_vecAlt0 (α : Type u_1) {h : 0 = 0 + 0} :
                                                          @[simp]
                                                          theorem Matrix.cons_vecAlt1 {α : Type u} {m n : } (h : m + 1 + 1 = n + 1 + (n + 1)) (x y : α) (u : Fin mα) :
                                                          vecAlt1 h (vecCons x (vecCons y u)) = vecCons y (vecAlt1 u)
                                                          @[simp]
                                                          theorem Matrix.empty_vecAlt1 (α : Type u_1) {h : 0 = 0 + 0} :
                                                          theorem Matrix.const_fin1_eq {α : Type u} (x : α) :
                                                          (fun (x_1 : Fin 1) => x) = ![x]