Failed to generate equational theorem

Stream: lean4

[Anand Rao]

I am facing an error when trying to simplify function definitions that make use of decreasing_by to show termination. I have created a minimal example of this issue that tries to calculate the length of a list in an extremely contrived way:

inductive ListSplit : List α → Type _
  | split l₁ l₂ : ListSplit (l₁ ++ l₂)

def splitList {α : Type _} : (l : List α) → ListSplit l
  | [] => ListSplit.split [] []
  | h :: t => ListSplit.split [h] t

theorem Nat.lt_add_left {m n : Nat}  : m < n + m := sorry
theorem Nat.lt_add_right {m n : Nat} : m < m + n := sorry

def len : List α → Nat
  | [] => 0
  | a :: [] => 1
  | l =>
    match (splitList l) with
      | ListSplit.split fst snd =>
        len fst + len snd
termination_by _ l => l.length
decreasing_by
  simp [measure, id, invImage, InvImage, Nat.lt_wfRel, WellFoundedRelation.rel, sizeOf] <;>
  first
    | apply Nat.lt_add_right
    | apply Nat.lt_add_left

theorem listlen : ∀ l : List α, l.length = len l := by
  intro l
  induction l with
    | nil => rfl
    | cons h t ih =>
      simp [List.length]
      simp [len] -- Error: failed to generate equational theorem for 'len'

Does anyone know the reason for this issue and how to bypass it? Thank you in advance.

[Leonardo de Moura]

This issue has been fixed a few days ago. The Lean 4 master can generate the equational theorems for len.
Here is the full example.

inductive ListSplit : List α → Type _
  | split l₁ l₂ : ListSplit (l₁ ++ l₂)

def splitList {α : Type _} : (l : List α) → ListSplit l
  | [] => ListSplit.split [] []
  | h :: t => ListSplit.split [h] t

theorem Nat.lt_add_left {m n : Nat}  : m < n + m := sorry
theorem Nat.lt_add_right {m n : Nat} : m < m + n := sorry

def len : List α → Nat
  | [] => 0
  | a :: [] => 1
  | l =>
    match splitList l with
    | ListSplit.split fst snd => len fst + len snd
termination_by _ l => l.length
decreasing_by
  simp [measure, id, invImage, InvImage, Nat.lt_wfRel, WellFoundedRelation.rel, sizeOf] <;>
  first
    | apply Nat.lt_add_right
    | apply Nat.lt_add_left

theorem len_nil : len ([] : List α) = 0 := by
  simp [len]

-- The `simp [len]` above generated the following equation theorems for len
#check @len._eq_1
#check @len._eq_2
#check @len._eq_3 -- It is conditional, and may be tricky to use.

theorem len_1 (a : α) : len [a] = 1 := by
  simp [len]

theorem len_2 (a b : α) (bs : List α) : len (a::b::bs) = 1 + len (b::bs) := by
  conv => lhs; unfold len

-- The `unfold` tactic above generated the following theorem
#check @len._unfold

theorem len_cons (a : α) (as : List α) : len (a::as) = 1 + len as := by
  cases as with
  | nil => simp [len_1, len_nil]
  | cons b bs => simp [len_2]

theorem listlen : ∀ l : List α, l.length = len l := by
  intro l
  induction l with
  | nil => rfl
  | cons h t ih =>
    simp [List.length, len_cons, ih]
    rw [Nat.add_comm]

[Jakub Nowak]

Lean failed to generate equational theorem for this type. I was told this is something that could be fixed in Lean itself. See #new members > What's going on with Prod?.

inductive VecOrd : Type 1 where
| zero : VecOrd
| succ : VecOrd → VecOrd

inductive VecType : Type where
| zero : VecType
| succ : VecType

def VecOrd.type : VecOrd → VecType
| .zero => .zero
| .succ .. => .succ

def VecT (m : Type → Type) (α : Type) (ord : VecOrd) : Type :=
  (type : VecType) × (_ : ord.type = type) ×' Unit × ((match type, ord with
    | .zero, .zero => Unit
    | .succ, .succ o => α × m (VecT m α o)
  ) : Type)

/--
error: failed to generate equational theorem for `VecT`
  no progress at goal
  m : Type → Type
  α : Type
  ord : VecOrd
  r : VecOrd.below ord :=
    (VecOrd.brecOn.go ord fun ord f =>
        (type : VecType) ×
          (x : ord.type = type) ×'
            Unit ×
              (match (motive := (type : VecType) → (ord : VecOrd) → ord.type = type → VecOrd.below ord → Type) type,
                  ord, x with
                | VecType.zero, VecOrd.zero, x => fun x => Unit
                | VecType.succ, o.succ, x => fun x => α × m x.1)
                f).2
  ⊢ ((type : VecType) ×
        (x : ord.type = type) ×'
          Unit ×
            (match (motive :=
                (type : VecType) →
                  (ord : VecOrd) → ord.type = type → VecOrd.rec PUnit (fun a a_ih => Type ×' a_ih) ord → Type)
                type, ord, x with
              | VecType.zero, VecOrd.zero, x => fun x => Unit
              | VecType.succ, o.succ, x => fun x => α × m x.1)
              r) =
      ((type : VecType) ×
        (x : ord.type = type) ×'
          Unit ×
            match type, ord, x with
            | VecType.zero, VecOrd.zero, x => Unit
            | VecType.succ, o.succ, x => α × m (VecT m α o))

-/
#guard_msgs in
example : VecT m α ord := by
  unfold VecT