Compare commits

...

2 Commits

Author SHA1 Message Date
Kim Morrison
a653f9688c fixes 2025-04-03 20:57:21 +11:00
Kim Morrison
0bfe7b7ecb chore: more failing test cases for grind 2025-04-03 20:25:33 +11:00
5 changed files with 50 additions and 11 deletions

View File

@@ -105,7 +105,7 @@ abbrev length_eq_zero := @length_eq_zero_iff
theorem eq_nil_iff_length_eq_zero : l = [] length l = 0 :=
length_eq_zero_iff.symm
theorem length_pos_of_mem {a : α} : {l : List α}, a l 0 < length l
@[grind] theorem length_pos_of_mem {a : α} : {l : List α}, a l 0 < length l
| _::_, _ => Nat.zero_lt_succ _
theorem exists_mem_of_length_pos : {l : List α}, 0 < length l a, a l
@@ -185,7 +185,8 @@ theorem singleton_inj {α : Type _} {a b : α} : [a] = [b] ↔ a = b := by
We simplify `l.get i` to `l[i.1]'i.2` and `l.get? i` to `l[i]?`.
-/
@[simp] theorem get_eq_getElem {l : List α} {i : Fin l.length} : l.get i = l[i.1]'i.2 := rfl
@[simp, grind]
theorem get_eq_getElem {l : List α} {i : Fin l.length} : l.get i = l[i.1]'i.2 := rfl
set_option linter.deprecated false in
@[deprecated "Use `a[i]?` instead." (since := "2025-02-12")]
@@ -224,7 +225,8 @@ theorem get?_eq_getElem? {l : List α} {i : Nat} : l.get? i = l[i]? := by
We simplify `l[i]!` to `(l[i]?).getD default`.
-/
@[simp] theorem getElem!_eq_getElem?_getD [Inhabited α] {l : List α} {i : Nat} :
@[simp, grind]
theorem getElem!_eq_getElem?_getD [Inhabited α] {l : List α} {i : Nat} :
l[i]! = (l[i]?).getD (default : α) := by
simp only [getElem!_def]
match l[i]? with
@@ -233,16 +235,16 @@ We simplify `l[i]!` to `(l[i]?).getD default`.
/-! ### getElem? and getElem -/
@[simp] theorem getElem?_nil {i : Nat} : ([] : List α)[i]? = none := rfl
@[simp, grind] theorem getElem?_nil {i : Nat} : ([] : List α)[i]? = none := rfl
theorem getElem_cons {l : List α} (w : i < (a :: l).length) :
(a :: l)[i] =
if h : i = 0 then a else l[i-1]'(match i, h with | i+1, _ => succ_lt_succ_iff.mp w) := by
cases i <;> simp
theorem getElem?_cons_zero {l : List α} : (a::l)[0]? = some a := rfl
@[grind] theorem getElem?_cons_zero {l : List α} : (a::l)[0]? = some a := rfl
@[simp] theorem getElem?_cons_succ {l : List α} : (a::l)[i+1]? = l[i]? := rfl
@[simp, grind] theorem getElem?_cons_succ {l : List α} : (a::l)[i+1]? = l[i]? := rfl
theorem getElem?_cons : (a :: l)[i]? = if i = 0 then some a else l[i-1]? := by
cases i <;> simp [getElem?_cons_zero]
@@ -335,7 +337,8 @@ We simplify away `getD`, replacing `getD l n a` with `(l[n]?).getD a`.
Because of this, there is only minimal API for `getD`.
-/
@[simp] theorem getD_eq_getElem?_getD {l : List α} {i : Nat} {a : α} : getD l i a = (l[i]?).getD a := by
@[simp, grind]
theorem getD_eq_getElem?_getD {l : List α} {i : Nat} {a : α} : getD l i a = (l[i]?).getD a := by
simp [getD]
theorem getD_cons_zero : getD (x :: xs) 0 d = x := by simp
@@ -362,7 +365,7 @@ theorem get!_eq_getElem! [Inhabited α] (l : List α) (i) : l.get! i = l[i]! :=
@[simp] theorem not_mem_nil {a : α} : ¬ a [] := nofun
@[simp] theorem mem_cons : a (b :: l) a = b a l :=
@[simp] theorem mem_cons : a b :: l a = b a l :=
fun h => by cases h <;> simp [Membership.mem, *],
fun | Or.inl rfl => by constructor | Or.inr h => by constructor; assumption
@@ -683,7 +686,7 @@ theorem set_eq_of_length_le {l : List α} {i : Nat} (h : l.length ≤ i) {a : α
induction l generalizing i with
| nil => simp_all
| cons a l ih =>
induction i
cases i
· simp_all
· simp only [set_cons_succ, cons.injEq, true_and]
rw [ih]

View File

@@ -236,10 +236,12 @@ namespace List
instance : GetElem (List α) Nat α fun as i => i < as.length where
getElem as i h := as.get i, h
@[simp] theorem getElem_cons_zero (a : α) (as : List α) (h : 0 < (a :: as).length) : getElem (a :: as) 0 h = a := by
@[simp, grind]
theorem getElem_cons_zero (a : α) (as : List α) (h : 0 < (a :: as).length) : getElem (a :: as) 0 h = a := by
rfl
@[simp] theorem getElem_cons_succ (a : α) (as : List α) (i : Nat) (h : i + 1 < (a :: as).length) : getElem (a :: as) (i+1) h = getElem as i (Nat.lt_of_succ_lt_succ h) := by
@[simp, grind]
theorem getElem_cons_succ (a : α) (as : List α) (i : Nat) (h : i + 1 < (a :: as).length) : getElem (a :: as) (i+1) h = getElem as i (Nat.lt_of_succ_lt_succ h) := by
rfl
@[simp] theorem getElem_mem : {l : List α} {n} (h : n < l.length), l[n]'h l

View File

@@ -0,0 +1,30 @@
theorem getElem?_eq_some_iff {l : List α} : l[i]? = some a h : i < l.length, l[i] = a := by
induction l
· grind
· cases i
· -- Fails because of the issue:
-- [issue] failed to create E-match local theorem for
-- ∀ (x : 1 ≤ tail.length), ¬tail[0] = a
-- despite having asserted `1 ≤ tail.length `.
grind
· -- Similarly
grind
attribute [grind] List.getElem_append_left List.getElem_append_right
@[simp] theorem getElem_concat_length {l : List α} {a : α} {i : Nat} (h : i = l.length) (w) :
(l ++ [a])[i]'w = a := by
subst h; grind
-- [issue] failed to create E-match local theorem for
-- ∀ (h₁ : True), (l ++ [a])[l.length] = [a][l.length - l.length]
attribute [grind] List.map_nil List.map_cons
attribute [grind] List.any_nil List.any_cons
attribute [grind] List.all_nil List.all_cons
@[simp] theorem any_map {l : List α} {p : β Bool} : (l.map f).any p = l.any (p f) := by
induction l <;> grind -- Seems to have trouble with the Boolean `||`
@[simp] theorem all_map {l : List α} {p : β Bool} : (l.map f).all p = l.all (p f) := by
induction l <;> grind -- Seems to have trouble with the Boolean `&&`

View File

@@ -1,3 +1,5 @@
reset_grind_attrs%
set_option trace.grind.ematch.pattern true
attribute [grind =] Array.size_set

View File

@@ -1,3 +1,5 @@
reset_grind_attrs%
attribute [grind =] Array.size_set Array.getElem_set_self Array.getElem_set_ne
set_option grind.debug true