Zulip Chat Archive

Stream: lean4

Topic: Did I write something wrong?


👀? (Nov 30 2022 at 07:14):

def shortest_aux (ps : List (Nat × Nat × Nat)) (o : Nat) (g : Nat) (ctx : List Nat) (l : Nat)
  : Nat × List (Nat × Nat × Nat) :=
  match ps with
  | [] => (0, [])
  | p :: ps' =>
    let (o', l', g') := p
    if o' = o ∧ g' = g then (l+l', [p])
    else if o' = o ∧ ctx.notElem g' then
      match shortest_aux ps g' g (g' :: ctx) (l+l') with
      | (0, []) => (0, [])
      | (l', es') => (l+l', p :: es')
    else shortest_aux ps' o g ctx l
fail to show termination for
  shortest_aux
with errors
argument #1 was not used for structural recursion
  failed to eliminate recursive application
    shortest_aux ps g' g (g' :: ctx) (l + l')

argument #2 was not used for structural recursion
  failed to eliminate recursive application
    shortest_aux ps g' g (g' :: ctx) (l + l')

argument #3 was not used for structural recursion
  failed to eliminate recursive application
    shortest_aux ps g' g (g' :: ctx) (l + l')

argument #4 was not used for structural recursion
  failed to eliminate recursive application
    shortest_aux ps g' g (g' :: ctx) (l + l')

argument #5 was not used for structural recursion
  failed to eliminate recursive application
    shortest_aux ps g' g (g' :: ctx) (l + l')

structural recursion cannot be used

failed to prove termination, use `termination_by` to specify a well-founded relationLean 4

Henrik Böving (Nov 30 2022 at 09:02):

Its not necessarily wrong, lean just cannot do the termination proof automatically so you have to. There is documentation in theorem proving in Lean on how to do that

👀? (Nov 30 2022 at 09:06):

How do I write a termination proof?

Alex J. Best (Nov 30 2022 at 13:50):

https://leanprover.github.io/theorem_proving_in_lean4/induction_and_recursion.html#well-founded-recursion-and-induction explains some examples of this


Last updated: Dec 20 2023 at 11:08 UTC