Zulip Chat Archive
Stream: lean4
Topic: simp? creates wrong proof with user defined let-value
Johannes Tantow (Mar 17 2025 at 18:37):
Hi,
simp? adds user defined let-values to the simp set, if they occur in a hypothesis (I guess). Here is an example:
example : [].filter (fun _ => true) = ([] : List String) := by
let t := 1+1+1
have ht: t = 1 + 1 +1 := by simp [t]
simp
Here it proposes to add t
to the simp set, which is useless. If I remove the have, this no longer happens. This is not problematic in this example, but in a real use case I used this technique to mask some term in which I cant rewrite (see below) and therefore get there an error when using this directly to replace simp
with simp only
.
import Std.Data.Internal.List.Associative
import Std.Data.Internal.List.Defs
@[inline] def Option.pfilter (o : Option α) (p : (a : α) → a ∈ o → Bool) : Option α :=
match o with
| none => none
| some a => bif p a rfl then o else none
theorem Option.pfilter_eq_none {α : Type _} {o : Option α} {p : (a : α) → a ∈ o → Bool} :
o.pfilter p = none ↔ o = none ∨ ∃ (a : α) (ha : a ∈ o), p a ha = false := by
sorry
theorem Option.pfilter_eq_some {α : Type _} {o : Option α} {p : (a : α) → a ∈ o → Bool}
{a : α} (ha : a ∈ o) :
o.pfilter p = some a ↔ p a ha = true := by
sorry
@[congr]
theorem pfilter_congr {α : Type u} {o o' : Option α} (ho : o = o')
{f : (a : α) → a ∈ o → Bool} {g : (a : α) → a ∈ o' → Bool}
(hf : ∀ a ha, f a (ho.trans ha) = g a ha) :
o.pfilter f = o'.pfilter g := by
sorry
namespace Std.Internal.List
variable {α : Type u} {β : α → Type v} {γ : α → Type w}
theorem containsKey_of_getKey?_eq_some [BEq α] [EquivBEq α] {l : List ((a : α) × β a)} {a a' : α}
(h : getKey? a l = some a') :
containsKey a' l = true := by sorry
theorem getEntry?_filterMap [BEq α] [EquivBEq α]
{f : (a : α) → β a → Option (γ a)}
{l : List ((a : α) × β a)} {k : α} (hl : DistinctKeys l) :
getEntry? k (l.filterMap fun p => (f p.1 p.2).map (⟨p.1, ·⟩)) =
(getEntry? k l).bind fun p => (f p.1 p.2).map (⟨p.1, ·⟩) := by
sorry
theorem List.getKey?_filterMap [BEq α] [LawfulBEq α]
{f : (a : α) → β a→ Option (γ a)}
{l : List ((a : α) × β a)} {k : α} (hl : DistinctKeys l) :
getKey? k (l.filterMap fun p => (f p.1 p.2).map (fun x => (⟨p.1, x⟩ : (a : α) × γ a))) =
(getKey? k l).pfilter (fun x h =>
(f x (getValueCast x l (containsKey_of_getKey?_eq_some (Option.mem_iff.mp h)))).isSome) := by
apply Eq.symm
let t := ((getKey? k l).pfilter fun x h =>
(f x (getValueCast x l (containsKey_of_getKey?_eq_some (Option.mem_iff.mp h)))).isSome)
have ht: t = ((getKey? k l).pfilter fun x h =>
(f x (getValueCast x l (containsKey_of_getKey?_eq_some (Option.mem_iff.mp h)))).isSome) := by
simp [t]
rw [← ht]
simp [getKey?_eq_getEntry?, getEntry?_filterMap hl, Option.map_bind] --here the problem occurs.
cases h : getEntry? k l with
| none =>
rw [ht]
simp [Option.pfilter_eq_none, h, getKey?_eq_getEntry?]
| some x =>
rw [ht]
have contains : containsKey k l = true := by
simp [containsKey_eq_isSome_getEntry?, h]
have := getKey?_eq_some contains
rw [getEntry?_eq_getValueCast?, Option.map_eq_some'] at h
rcases h with ⟨v, hv, hx⟩
simp [← hx]
cases h' : f k v with
| none =>
simp [Option.pfilter_eq_none, this]
exists k
exists rfl
simp [getValueCast, hv, h']
| some y =>
simp
rw [Option.pfilter_eq_some]
simp [getValueCast, hv, h']
apply this
Bhavik Mehta (Mar 18 2025 at 00:15):
I believe this is lean4#6655
Jovan Gerbscheid (Mar 18 2025 at 00:20):
I started an attempt to fix this at lean#7539
Last updated: May 02 2025 at 03:31 UTC