Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

YukonModule.CompPoly.Data.Array.Lemmas.part0

Definition
Yukon_4ab5b1359edc58b62f9d3fd7

by yukon · Sep 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

better-codes

Source module CompPoly.Data.Array.Lemmas.

Definition code
/-
Copyright (c) 2025 CompPoly. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Quang Dao, Gregor Mitscha-Baude
-/
module

public import Definitions.Def_Yukon_a12f6836cf69dff850789d62

public import Mathlib.Algebra.Order.Ring.Nat
public import Mathlib.Algebra.Order.Star.Basic
public import Mathlib.Data.Nat.Log


public import Mathlib.Tactic.Cases
public import Mathlib.Order.Lattice.Nat
public import Mathlib.Data.List.GetD
public import Mathlib.Algebra.GroupWithZero.Nat
public import Init
meta import Definitions.Def_Yukon_a12f6836cf69dff850789d62
set_option backward.isDefEq.respectTransparency.types false
/-!
# Auxiliary lemmas for `Array`
-/

@[expose] public section
universe u

namespace Array

variable {α : Type*} {unit : α}

/-- Remove duplicates from an array while preserving first occurrences. -/
def eraseDups [BEq α] (xs : Array α) : Array α :=
  xs.foldl
    (fun out x ↦
      if out.contains x then
        out
      else
        out.push x)
    #[]

/-- Checks if an array of elements from a type `R` is a boolean array, i.e., if every element is
  either `0` or `1`. -/
def isBoolean {R : Type _} [Zero R] [One R] (a : Array R) : Prop :=
    ∀ i : Fin a.size, (a[i] = 0) ∨ (a[i] = 1)

/-- Interpret an array as the binary representation of a number, sending `0` to `0` and `≠ 0` to
  `1`. -/
def toNum {R : Type _} [Zero R] [DecidableEq R] (a : Array R) : ℕ :=
  (a.map (fun r => if r = 0 then 0 else 1)).reverse.foldl (fun acc elem => (acc * 2) + elem) 0

lemma leftpad_toList {a : Array α} {n : Nat} {unit : α} :
    a.leftpad n unit = mk (a.toList.leftpad n unit) := by
  cases a
  simp

lemma rightpad_toList {a : Array α} {n : Nat} {unit : α} :
    a.rightpad n unit = mk (a.toList.rightpad n unit) := by
  cases a
  simp

lemma rightpad_getElem_eq_getD {a : Array α} {n : Nat} {unit : α} {i : Nat}
    (h : i < (a.rightpad n unit).size) : (a.rightpad n unit)[i] = a.getD i unit := by
  simp_rw [rightpad_toList] at h ⊢
  -- By definition of `rightpad`, the element at position `i` in the right-padded array is
  -- the same as the element at position `i` in the original list `a` if `i` is within
  -- the bounds of `a`.
  have h_rightpad_getElem_eq_getD : (a.toList.rightpad n unit)[i] = a.toList.getD i unit := by
    grind
  cases a
  aesop

/-- `Array` version of `List.matchSize`, which rightpads the arrays to the same length. -/
@[reducible]
def matchSize (a b : Array α) (unit : α) : Array α × Array α :=
  (a.rightpad (b.size) unit, b.rightpad (a.size) unit)

lemma matchSize_toList {a b : Array α} {unit : α} :
    matchSize a b unit =
      let (a', b') := List.matchSize a.toList b.toList unit
      (mk a', mk b') := by
  simp [matchSize, List.matchSize, rightpad_toList]

lemma getElem?_eq_toList {a : Array α} {i : ℕ} : a.toList[i]? = a[i]? := by
  rw (occs := .pos [2]) [← Array.toArray_toList (xs := a)]
  rw [List.getElem?_toArray]

/-- `Array.map` and `getD` agree with indexed access on in-bounds indices. -/
theorem getD_map_of_lt {β : Type*} (xs : Array α) (f : α → β)
    (d : β) {i : Nat} (hi : i < xs.size) :
    (xs.map f).getD i d = f xs[i] := by
  rw [Array.getD_eq_getD_getElem?, Array.getElem?_map, Array.getElem?_eq_getElem hi]
  simp

theorem foldl_zipIdx_eq_foldl_toList_zipIdx {β : Type*}
    (f : β → α × Nat → β) (init : β) (a : Array α) :
    a.zipIdx.foldl f init = a.toList.zipIdx.foldl f init := by
  cases a
  simp

theorem foldl_zipIdx_eq_foldl_toList_zipIdx_size {β : Type*}
    (f : β → α × Nat → β) (init : β) (a : Array α) :
    Array.foldl f init a.zipIdx 0 a.size = a.toList.zipIdx.foldl f init := by
  cases a
  simp

theorem mem_foldl_append_of_mem {β : Type*}
    (xs : Array α) (f : α → Array β) {x : α} {y : β}
    (hx : x ∈ xs.toList) (hy : y ∈ (f x).toList) :
    y ∈ (xs.foldl (fun out x ↦ out ++ f x) #[]).toList := by
  cases xs with
  | mk data =>
      simp at hx ⊢
      have haux : ∀ (data : List α) (acc : Array β),
          y ∈ acc.toList ∨ (∃ x, x ∈ data ∧ y ∈ (f x).toList) →
            y ∈ (data.foldl (fun out x ↦ out ++ f x) acc).toList := by
        intro data
        induction data with
        | nil =>
            intro acc h
            simp at h ⊢
            exact h
        | cons z zs ih =>
            intro acc h
            simp only [List.foldl_cons]
            apply ih
            rcases h with hacc | ⟨x, hx, hyx⟩
            · left
              simp [hacc]
            · simp only [List.mem_cons] at hx
              cases hx with
              | inl hxz =>
                  subst x
                  left
                  simp [hyx]
              | inr hxzs =>
                  right
                  exact ⟨x, hxzs, hyx⟩
      simpa using haux data #[] (Or.inr ⟨x, hx, hy⟩)

theorem mem_flatten_map_of_mem {β : Type*}
    (xs : Array α) (f : α → Array β) {x : α} {y : β}
    (hx : x ∈ xs.toList) (hy : y ∈ (f x).toList) :
    y ∈ (xs.map f).flatten := by
  cases xs with
  | mk data =>
      simp at hx hy ⊢
      exact ⟨x, hx, hy⟩

attribute [simp] Array.getElem?_eq_getElem

-- @[simp] theorem matchSize_comm (a : Array α) (b : Array α) (unit : α) :
--     matchSize a b unit = (matchSize b a unit).swap := by
--   simp [matchSize, List.matchSize]

/-- find index from the end of an array -/
def findIdxRev? (cond : α → Bool) (as : Array α) : Option (Fin as.size) :=
  find ⟨ as.size, Nat.lt_succ_self _ ⟩
where
  find : Fin (as.size + 1) → Option (Fin as.size)
    | 0 => none
    | ⟨ i+1, h ⟩ =>
      if (cond as[i]) then
        some ⟨ i, Nat.lt_of_succ_lt_succ h ⟩
      else
        find ⟨ i, Nat.lt_of_succ_lt h ⟩

/-- if findIdxRev? finds an index, the condition is satisfied on that element -/
lemma findIdxRev?_def {cond} {as : Array α} {k : Fin as.size} :
    findIdxRev? cond as = some k → cond as[k] := by
  suffices aux : ∀ i, findIdxRev?.find cond as i = some k → cond as[k] by apply aux
  intro i
  unfold findIdxRev?.find
  induction i using findIdxRev?.find.induct cond as with
  | case1 => simp
  | case2 => simp [*]; rintro rfl; assumption
  | case3 => unfold findIdxRev?.find; simp [*]; assumption

/-- if findIdxRev? finds an index, then for every greater index the condition doesn't hold -/
lemma findIdxRev?_maximal {cond} {as : Array α} {k : Fin as.size} :
    findIdxRev? cond as = some k → ∀ j : Fin as.size, j > k → ¬ cond as[j] := by
  suffices aux : ∀ i, findIdxRev?.find cond as i = some k →
    ∀ j : Fin as.size, j > k → j.val < i → ¬ cond as[j] by
    intro h j j_gt_k
    exact aux ⟨ as.size, Nat.lt_succ_self _ ⟩ h j j_gt_k j.is_lt
  intro i
  unfold findIdxRev?.find
  induction i using findIdxRev?.find.induct cond as with
  | case1 => simp
  | case2 i =>
    simp [*]
    rintro rfl j (_: j > i) (_: j < i + 1) -- contradiction
    omega
  | case3 i _ not_true ih =>
    simp [*]
    unfold findIdxRev?.find
    intro h j j_gt_k j_lt_isucc
    specialize ih h j j_gt_k
    rcases (Nat.lt_or_eq_of_le (Nat.le_of_lt_succ j_lt_isucc): j < i ∨ j = i) with (j_lt_i | rfl)
    · specialize ih j_lt_i
      rwa [Bool.not_eq_true] at ih
    · simp only [not_true]

/-- if the condition is false on all elements, then findIdxRev? finds nothing -/
lemma findIdxRev?_eq_none {cond} {as : Array α} (h : ∀ i, (hi : i < as.size) → ¬ cond as[i]) :
    findIdxRev? cond as = none := by
  apply aux
where
  aux i : findIdxRev?.find cond as i = none := by
    unfold findIdxRev?.find
    split
    next => tauto
    next _ j _ =>
      split -- then/else cases inside .find
      next cond_true =>
        have cond_false : ¬ cond as[j] := h j _
        have : False := cond_false cond_true
        contradiction
      -- recursively invoke the theorem we are proving!
      apply aux

lemma findIdxRev?_empty_none {cond} {as : Array α} (h : as = #[]) :
    findIdxRev? cond as = none := by
  rw [h]
  apply findIdxRev?_eq_none
  simp

/-- if the condition is true on some element, then findIdxRev? finds something -/
lemma findIdxRev?_eq_some {cond} {as : Array α} (h : ∃ i, ∃ hi : i < as.size, cond as[i]) :
    ∃ k : Fin as.size, findIdxRev? cond as = some k := by
  obtain ⟨ i, hi, hcond ⟩ := h
  apply aux ⟨ as.size, Nat.lt_succ_self _ ⟩ ⟨ .mk i hi, hi, hcond ⟩
where
  aux (i : Fin (as.size + 1)) (h': ∃ i' : Fin as.size, i' < i.val ∧ cond as[i']) :
    ∃ k, findIdxRev?.find cond as i = some k := by
    unfold findIdxRev?.find
    split
    next => tauto
    next _ j hj =>
      split -- then/else cases inside .find
      · use .mk j (by omega)
      · obtain ⟨ k, hk : k < j + 1, hcond ⟩ := h'
        apply aux -- recursively invoke the theorem we are proving!
        have : k.val ≠ j := by rintro rfl; contradiction
        have : k.val < j := by omega
        use k

/-- Right-pads an array with `unit` elements until its length is a power of two. Returns the padded
  array and the number of elements added. -/
def rightpadPowerOfTwo (unit : α) (a : Array α) : Array α :=
  a.rightpad (2 ^ (Nat.clog 2 a.size)) unit

@[simp] lemma rightpadPowerOfTwo_size (unit : α) (a : Array α) :
  (a.rightpadPowerOfTwo unit).size = 2 ^ (Nat.clog 2 a.size) := by
  have h_le : a.size ≤ 2 ^ Nat.clog 2 a.size := by
    exact (Nat.clog_le_iff_le_pow (b := 2) (by decide)).1 le_rfl
  simp only [rightpadPowerOfTwo, Array.size_rightpad]
  omega

/-- Get the last element of an array, assuming the array is non-empty. -/
def getLast (a : Array α) (h : a.size > 0) : α := a[a.size - 1]

/-- Get the last element of an array, or `v₀` if the array is empty. -/
def getLastD (a : Array α) (v₀ : α) : α := a.getD (a.size - 1) v₀

lemma popWhile_nil_or_last_false (p : α → Bool) (as : Array α)
    (h : (as.popWhile p).size > 0) : ¬ (p <| (as.popWhile p).getLast h) := by
  -- By definition of `popWhile`, if the array is empty, then `popWhile` returns an empty array.
  induction' as using Array.recOn with as ih
  induction' as using List.reverseRecOn with as ih
  · -- In the base case, when the array is empty, `popWhile` returns an empty array.
    -- Therefore, the size is zero, which contradicts `h`.
    simp at h
  · by_cases h' : p ih <;> simp_all +decide
    · aesop
    · simp_all +decide [ Array.getLast ]

end Array


Source
https://github.com/zksecurity/CompPoly/blob/641694629e4557520a1539b272ec338c9f3044c7/CompPoly/Data/Array/Lemmas.lean yukon-proof-operation:7672a0fea268f2f0e74d972aaa7f3f625d919bb4c5271ecd6a63656e9d17e081 [yukon-proof-receipt:eyJ2IjoxLCJtYXJrZXIiOiJ5dWtvbi1wcm9vZi1vcGVyYXRpb246NzY3MmEwZmVhMjY4ZjJmMGU3NGQ5NzJhYWE3ZjNmNjI1ZDkxOWJiNGM1MjcxZWNkNmE2MzY1NmU5ZDE3ZTA4MSIsImhhc2giOiIzYzFmNzA0ZDlhYjZhMmFkOGNlMmNhOWZhODEwNjUxOWY3NTU4MTAwNzA4MmYwMzI4NDAwYjUzNjMyZmZhZTJkIiwia2luZCI6ImRlZmluaXRpb24iLCJ0YXJnZXQiOiJZdWtvbl80YWI1YjEzNTllZGM1OGI2MmY5ZDNmZDciLCJlbnZpcm9ubWVudCI6eyJtYXRobGliUmV2IjoiMGRmNDQ0YTM2MGVhYTYwYWI4YzExZGNhNTFhODZhZjY5Mjk1NTQ3NCIsInRvb2xjaGFpbiI6ImxlYW5wcm92ZXIvbGVhbjQ6djQuMzMuMSJ9LCJ0YWciOiJiZXR0ZXItY29kZXMifQ]

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me