Zulip Chat Archive
Stream: lean4
Topic: Can't get lean to unify equality
Sebastian Widua (Jan 09 2023 at 12:16):
I'm starting to think I'm crazy.
When I do this
def log2_rem (x : Nat) : Nat × Nat :=
if h_zero : x = 0 then
(0, 0)
else if 2 ∣ x then
have : x / 2 < x := Nat.half_lt_self h_zero
let (exp, rest) := log2_rem (x / 2)
(exp+1, rest)
else (0, x)
theorem log2_rem_eq (x : Nat) : log2_rem x =
(if h_zero : x = 0 then
(0, 0)
else if 2 ∣ x then
have : x / 2 < x := Nat.half_lt_self h_zero
let (exp, rest) := log2_rem (x / 2)
(exp+1, rest)
else (0, x)) := rfl
I get the error
type mismatch
rfl
has type
log2_rem x = log2_rem x : Prop
but is expected to have type
log2_rem x =
if h_zero : x = 0 then (0, 0)
else
if 2 ∣ x then
let_fun this := (_ : x / 2 < x);
match log2_rem (x / 2) with
| (exp, rest) => (exp + 1, rest)
else (0, x) : Prop
even though it's literally just the code copy-pasted
Eric Wieser (Jan 09 2023 at 12:20):
It's not the same code copy-pasted, because log2_rem
in the first example is a self-reference to a thing that doesn't exist yet
Eric Wieser (Jan 09 2023 at 12:21):
The proof of log2_rem_eq
should be rw [log2_rem]
, because Lean generates an unfolding lemma that does what you want
Sebastian Widua (Jan 09 2023 at 12:26):
Eric Wieser said:
It's not the same code copy-pasted, because
log2_rem
in the first example is a self-reference to a thing that doesn't exist yet
oh is this because I used well-founded recursion here? Good to know
Eric Wieser (Jan 09 2023 at 12:26):
Exactly!
Last updated: Dec 20 2023 at 11:08 UTC