blob: 7e226c242c4bb30a01cfb5086735442f4a7b24ae [file]
/-
Copyright (c) 2025 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/
prelude
import Init.Data.Vector.Lemmas
import Init.Data.Vector.Attach
import Init.Data.Vector.Range
import Init.Data.Array.Find
/-!
# Lemmas about `Vector.findSome?`, `Vector.find?`, `Vector.findFinIdx?`.
We are still missing results about `idxOf?`, `findIdx`, and `findIdx?`.
-/
set_option linter.listVariables true -- Enforce naming conventions for `List`/`Array`/`Vector` variables.
set_option linter.indexVariables true -- Enforce naming conventions for index variables.
namespace Vector
open Nat
/-! ### findSome? -/
@[simp] theorem findSomeRev?_push_of_isSome {xs : Vector α n} {h : (f a).isSome} : (xs.push a).findSomeRev? f = f a := by
rcases xs with ⟨xs, rfl⟩
simp only [push_mk, findSomeRev?_mk, Array.findSomeRev?_push_of_isSome, h]
@[simp] theorem findSomeRev?_push_of_isNone {xs : Vector α n} {h : (f a).isNone} : (xs.push a).findSomeRev? f = xs.findSomeRev? f := by
rcases xs with ⟨xs, rfl⟩
simp only [push_mk, findSomeRev?_mk, Array.findSomeRev?_push_of_isNone, h]
theorem exists_of_findSome?_eq_some {f : α → Option β} {xs : Vector α n} (w : xs.findSome? f = some b) :
∃ a, a ∈ xs ∧ f a = b := by
rcases xs with ⟨xs, rfl⟩
simpa using Array.exists_of_findSome?_eq_some (by simpa using w)
@[simp] theorem findSome?_eq_none_iff {f : α → Option β} {xs : Vector α n} :
xs.findSome? f = none ↔ ∀ x ∈ xs, f x = none := by
rcases xs with ⟨xs, rfl⟩
simp
@[simp] theorem findSome?_isSome_iff {f : α → Option β} {xs : Vector α n} :
(xs.findSome? f).isSome ↔ ∃ x, x ∈ xs ∧ (f x).isSome := by
rcases xs with ⟨xs, rfl⟩
simp
theorem findSome?_eq_some_iff {f : α → Option β} {xs : Vector α n} {b : β} :
xs.findSome? f = some b ↔
∃ (k₁ k₂ : Nat) (w : n = k₁ + 1 + k₂) (ys : Vector α k₁) (a : α) (zs : Vector α k₂),
xs = (ys.push a ++ zs).cast w.symm ∧ f a = some b ∧ ∀ x ∈ ys, f x = none := by
rcases xs with ⟨xs, rfl⟩
simp only [findSome?_mk, mk_eq]
rw [Array.findSome?_eq_some_iff]
constructor
· rintro ⟨ys, a, zs, rfl, h₁, h₂⟩
exact ⟨ys.size, zs.size, by simp, ⟨ys, rfl⟩, a, ⟨zs, rfl⟩, by simp, h₁, by simpa using h₂⟩
· rintro ⟨k₁, k₂, h, ys, a, zs, w, h₁, h₂⟩
exact ⟨ys.toArray, a, zs.toArray, by simp [w], h₁, by simpa using h₂⟩
@[simp] theorem findSome?_guard {xs : Vector α n} : findSome? (Option.guard fun x => p x) xs = find? p xs := by
rcases xs with ⟨xs, rfl⟩
simp
theorem find?_eq_findSome?_guard {xs : Vector α n} : find? p xs = findSome? (Option.guard fun x => p x) xs :=
findSome?_guard.symm
@[simp] theorem map_findSome? {f : α → Option β} {g : β → γ} {xs : Vector α n} :
(xs.findSome? f).map g = xs.findSome? (Option.map g ∘ f) := by
cases xs; simp
theorem findSome?_map {f : β → γ} {xs : Vector β n} : findSome? p (xs.map f) = xs.findSome? (p ∘ f) := by
rcases xs with ⟨xs, rfl⟩
simp [Array.findSome?_map]
theorem findSome?_append {xs : Vector α n₁} {ys : Vector α n₂} : (xs ++ ys).findSome? f = (xs.findSome? f).or (ys.findSome? f) := by
cases xs; cases ys; simp [Array.findSome?_append]
theorem getElem?_zero_flatten {xss : Vector (Vector α m) n} :
(flatten xss)[0]? = xss.findSome? fun xs => xs[0]? := by
cases xss using vector₂_induction
simp [Array.getElem?_zero_flatten, Array.findSome?_map, Function.comp_def]
theorem getElem_zero_flatten.proof {xss : Vector (Vector α m) n} (h : 0 < n * m) :
(xss.findSome? fun xs => xs[0]?).isSome := by
cases xss using vector₂_induction with
| of xss h₁ h₂ =>
have hn : 0 < n := Nat.pos_of_mul_pos_right h
have hm : 0 < m := Nat.pos_of_mul_pos_left h
simp only [hm, getElem?_eq_getElem, findSome?_mk, Array.findSome?_isSome_iff, Array.mem_map,
Array.mem_attach, mk_eq, true_and, Subtype.exists, exists_prop, exists_eq_right,
Option.isSome_some, and_true]
exact ⟨⟨xss[0], h₂ _ (by simp)⟩, by simp⟩
theorem getElem_zero_flatten {xss : Vector (Vector α m) n} (h : 0 < n * m) :
(flatten xss)[0] = (xss.findSome? fun xs => xs[0]?).get (getElem_zero_flatten.proof h) := by
have t := getElem?_zero_flatten (xss := xss)
simp [getElem?_eq_getElem, h] at t
simp [← t]
theorem findSome?_replicate : findSome? f (replicate n a) = if n = 0 then none else f a := by
rw [replicate_eq_mk_replicate, findSome?_mk, Array.findSome?_replicate]
@[deprecated findSome?_replicate (since := "2025-03-18")]
abbrev findSome?_mkVector := @findSome?_replicate
@[simp] theorem findSome?_replicate_of_pos (h : 0 < n) : findSome? f (replicate n a) = f a := by
simp [findSome?_replicate, Nat.ne_of_gt h]
@[deprecated findSome?_replicate_of_pos (since := "2025-03-18")]
abbrev findSome?_mkVector_of_pos := @findSome?_replicate_of_pos
-- Argument is unused, but used to decide whether `simp` should unfold.
@[simp] theorem findSome?_replicate_of_isSome (_ : (f a).isSome) :
findSome? f (replicate n a) = if n = 0 then none else f a := by
simp [findSome?_replicate]
@[deprecated findSome?_replicate_of_isSome (since := "2025-03-18")]
abbrev findSome?_mkVector_of_isSome := @findSome?_replicate_of_isSome
@[simp] theorem findSome?_replicate_of_isNone (h : (f a).isNone) :
findSome? f (replicate n a) = none := by
rw [Option.isNone_iff_eq_none] at h
simp [findSome?_replicate, h]
@[deprecated findSome?_replicate_of_isNone (since := "2025-03-18")]
abbrev findSome?_mkVector_of_isNone := @findSome?_replicate_of_isNone
/-! ### find? -/
@[simp] theorem find?_singleton {a : α} {p : α → Bool} :
#v[a].find? p = if p a then some a else none := by
simp
@[simp] theorem findRev?_push_of_pos {xs : Vector α n} (h : p a) :
findRev? p (xs.push a) = some a := by
cases xs; simp [h]
@[simp] theorem findRev?_cons_of_neg {xs : Vector α n} (h : ¬p a) :
findRev? p (xs.push a) = findRev? p xs := by
cases xs; simp [h]
@[simp] theorem find?_eq_none : find? p l = none ↔ ∀ x ∈ l, ¬ p x := by
cases l; simp
theorem find?_eq_some_iff_append {xs : Vector α n} :
xs.find? p = some b ↔
p b ∧ ∃ (k₁ k₂ : Nat) (w : n = k₁ + 1 + k₂) (as : Vector α k₁) (bs : Vector α k₂),
xs = (as.push b ++ bs).cast w.symm ∧ ∀ a ∈ as, !p a := by
rcases xs with ⟨xs, rfl⟩
simp only [find?_mk, Array.find?_eq_some_iff_append,
mk_eq, toArray_cast, toArray_append, toArray_push]
constructor
· rintro ⟨h, as, bs, rfl, w⟩
exact ⟨h, as.size, bs.size, by simp, ⟨as, rfl⟩, ⟨bs, rfl⟩, by simp, by simpa using w⟩
· rintro ⟨h, k₁, k₂, w, as, bs, h', w'⟩
exact ⟨h, as.toArray, bs.toArray, by simp [h'], by simpa using w'⟩
@[simp]
theorem find?_push_eq_some {xs : Vector α n} :
(xs.push a).find? p = some b ↔ xs.find? p = some b ∨ (xs.find? p = none ∧ (p a ∧ a = b)) := by
cases xs; simp
@[simp] theorem find?_isSome {xs : Vector α n} {p : α → Bool} : (xs.find? p).isSome ↔ ∃ x, x ∈ xs ∧ p x := by
cases xs; simp
theorem find?_some {xs : Vector α n} (h : find? p xs = some a) : p a := by
rcases xs with ⟨xs, rfl⟩
simp at h
exact Array.find?_some h
theorem mem_of_find?_eq_some {xs : Vector α n} (h : find? p xs = some a) : a ∈ xs := by
cases xs
simp at h
simpa using Array.mem_of_find?_eq_some h
theorem get_find?_mem {xs : Vector α n} (h) : (xs.find? p).get h ∈ xs := by
cases xs
simp [Array.get_find?_mem]
@[simp] theorem find?_filter {xs : Vector α n} (p q : α → Bool) :
(xs.filter p).find? q = xs.find? (fun a => p a ∧ q a) := by
cases xs; simp
@[simp] theorem getElem?_zero_filter {p : α → Bool} {xs : Vector α n} :
(xs.filter p)[0]? = xs.find? p := by
cases xs; simp [← List.head?_eq_getElem?]
@[simp] theorem getElem_zero_filter {p : α → Bool} {xs : Vector α n} (h) :
(xs.filter p)[0] =
(xs.find? p).get (by cases xs; simpa [← Array.countP_eq_size_filter] using h) := by
cases xs
simp [List.getElem_zero_eq_head]
@[simp] theorem find?_map {f : β → α} {xs : Vector β n} :
find? p (xs.map f) = (xs.find? (p ∘ f)).map f := by
cases xs; simp
@[simp] theorem find?_append {xs : Vector α n₁} {ys : Vector α n₂} :
(xs ++ ys).find? p = (xs.find? p).or (ys.find? p) := by
cases xs
cases ys
simp
@[simp] theorem find?_flatten {xs : Vector (Vector α m) n} {p : α → Bool} :
xs.flatten.find? p = xs.findSome? (·.find? p) := by
cases xs using vector₂_induction
simp [Array.findSome?_map, Function.comp_def]
theorem find?_flatten_eq_none_iff {xs : Vector (Vector α m) n} {p : α → Bool} :
xs.flatten.find? p = none ↔ ∀ ys ∈ xs, ∀ x ∈ ys, !p x := by
simp
@[simp] theorem find?_flatMap {xs : Vector α n} {f : α → Vector β m} {p : β → Bool} :
(xs.flatMap f).find? p = xs.findSome? (fun x => (f x).find? p) := by
cases xs
simp [Array.find?_flatMap, Array.flatMap_toArray]
theorem find?_flatMap_eq_none_iff {xs : Vector α n} {f : α → Vector β m} {p : β → Bool} :
(xs.flatMap f).find? p = none ↔ ∀ x ∈ xs, ∀ y ∈ f x, !p y := by
simp
theorem find?_replicate :
find? p (replicate n a) = if n = 0 then none else if p a then some a else none := by
rw [replicate_eq_mk_replicate, find?_mk, Array.find?_replicate]
@[deprecated find?_replicate (since := "2025-03-18")]
abbrev find?_mkVector := @find?_replicate
@[simp] theorem find?_replicate_of_size_pos (h : 0 < n) :
find? p (replicate n a) = if p a then some a else none := by
simp [find?_replicate, Nat.ne_of_gt h]
@[deprecated find?_replicate_of_size_pos (since := "2025-03-18")]
abbrev find?_mkVector_of_length_pos := @find?_replicate_of_size_pos
@[simp] theorem find?_replicate_of_pos (h : p a) :
find? p (replicate n a) = if n = 0 then none else some a := by
simp [find?_replicate, h]
@[deprecated find?_replicate_of_pos (since := "2025-03-18")]
abbrev find?_mkVector_of_pos := @find?_replicate_of_pos
@[simp] theorem find?_replicate_of_neg (h : ¬ p a) : find? p (replicate n a) = none := by
simp [find?_replicate, h]
@[deprecated find?_replicate_of_neg (since := "2025-03-18")]
abbrev find?_mkVector_of_neg := @find?_replicate_of_neg
-- This isn't a `@[simp]` lemma since there is already a lemma for `l.find? p = none` for any `l`.
theorem find?_replicate_eq_none_iff {n : Nat} {a : α} {p : α → Bool} :
(replicate n a).find? p = none ↔ n = 0 ∨ !p a := by
simp [Classical.or_iff_not_imp_left]
@[deprecated find?_replicate_eq_none_iff (since := "2025-03-18")]
abbrev find?_mkVector_eq_none_iff := @find?_replicate_eq_none_iff
@[simp] theorem find?_replicate_eq_some_iff {n : Nat} {a b : α} {p : α → Bool} :
(replicate n a).find? p = some b ↔ n ≠ 0 ∧ p a ∧ a = b := by
rw [replicate_eq_mk_replicate, find?_mk]
simp
@[deprecated find?_replicate_eq_some_iff (since := "2025-03-18")]
abbrev find?_mkVector_eq_some_iff := @find?_replicate_eq_some_iff
@[simp] theorem get_find?_replicate {n : Nat} {a : α} {p : α → Bool} (h) :
((replicate n a).find? p).get h = a := by
simp only [replicate_eq_mk_replicate, find?_mk]
simp
@[deprecated get_find?_replicate (since := "2025-03-18")]
abbrev get_find?_mkVector := @get_find?_replicate
theorem find?_pmap {P : α → Prop} {f : (a : α) → P a → β} {xs : Vector α n}
(H : ∀ (a : α), a ∈ xs → P a) {p : β → Bool} :
(xs.pmap f H).find? p = (xs.attach.find? (fun ⟨a, m⟩ => p (f a (H a m)))).map fun ⟨a, m⟩ => f a (H a m) := by
simp only [pmap_eq_map_attach, find?_map]
rfl
theorem find?_eq_some_iff_getElem {xs : Vector α n} {p : α → Bool} {b : α} :
xs.find? p = some b ↔ p b ∧ ∃ i h, xs[i] = b ∧ ∀ j : Nat, (hj : j < i) → !p xs[j] := by
rcases xs with ⟨xs, rfl⟩
simp [Array.find?_eq_some_iff_getElem]
/-! ### findFinIdx? -/
@[simp] theorem findFinIdx?_empty {p : α → Bool} : findFinIdx? p (#v[] : Vector α 0) = none := by simp
@[congr] theorem findFinIdx?_congr {p : α → Bool} {xs : Vector α n} {ys : Vector α n} (w : xs = ys) :
findFinIdx? p xs = findFinIdx? p ys := by
subst w
simp
@[simp]
theorem isSome_findFinIdx? {xs : Vector α n} {p : α → Bool} :
(xs.findFinIdx? p).isSome = xs.any p := by
rcases xs with ⟨xs, rfl⟩
simp
@[simp]
theorem isNone_findFinIdx? {xs : Vector α n} {p : α → Bool} :
(xs.findFinIdx? p).isNone = xs.all (fun x => ¬ p x) := by
rcases xs with ⟨xs, rfl⟩
simp
@[simp] theorem findFinIdx?_subtype {p : α → Prop} {xs : Vector { x // p x } n}
{f : { x // p x } → Bool} {g : α → Bool} (hf : ∀ x h, f ⟨x, h⟩ = g x) :
xs.findFinIdx? f = xs.unattach.findFinIdx? g := by
rcases xs with ⟨xs, rfl⟩
simp [hf, Function.comp_def]
end Vector