Zulip Chat Archive

Stream: lean4

Topic: temporary unamed variable before induction


Alexandre Rademaker (Apr 17 2025 at 22:57):

Given the definitions below (almost identical to the ones provided by Lean):

def foldr {a b : Type} (f : a  b  b) (e : b) : List a  b
| []      => e
| x :: xs => f x (foldr f e xs)

def foldl {a b : Type} (f : b  a  b) (e : b) : List a  b
| []      => e
| x :: xs => foldl f (f e x) xs

def foldl₁ {a b : Type} (f : b  a  b) (e : b) (xs : List a) : b :=
  foldr (flip f) e xs.reverse

I was able to prove that an alternative definition of foldl is equivalent to the original definition:

example {a b : Type} (f : b  a  b) (e : b) (xs : List a)
 : foldl f e xs = foldl₁ f e xs := by
 unfold foldl₁
 induction xs generalizing e with
 | nil =>
   rw [List.reverse, foldl]; simp
   rw [foldr]
 | cons r rs ih₁ =>
   rw [List.reverse]
   simp
   rw [foldl]
   rw [ih₁ (f e r)]
   induction rs.reverse with
   | nil =>
     simp [foldr, flip]
   | cons z zs ih₂ =>
     simp [foldr, flip]
     rw [ih₂]

But if you put your cursor at the beginning of the line induction rs.reverse with (before its execution), you notice the introduction of an unnamed variable x✝ : List a. Why is that happening?

Kyle Miller (Apr 17 2025 at 23:05):

The induction target needs to be a local variable, so induction will use generalize rs.reverse = x first and then do induction x.

Alexandre Rademaker (Apr 17 2025 at 23:06):

Can I control the name of the result term rs.reverse? Moreover, why is this appearing before the induction being executed (the cursor was at the beginning of the line).

Kyle Miller (Apr 17 2025 at 23:15):

The induction tactic is saving the goal states after it does this generalization. Likely it should save it before generalization. (That's to say, even though your cursor is at the beginning of induction, you are seeing the goal state partway through induction being executed.)

No, you can't control the name of this term using induction. If you want control, you can manually use generalize.

There's also induction h : rs.reverse syntax for creating an equality, like with generalize h : rs.reverse = x.


Last updated: May 02 2025 at 03:31 UTC