Zulip Chat Archive
Stream: new members
Topic: rfl and proof of termination
Daniel Lu (Oct 09 2023 at 22:19):
i ran into some trouble in a proof and tried to reproduce the core of my question here.
consider the following, which itself typechecks fine:
def func { a : Type } : List a -> List a -> List a
| _, [] => []
| xs, y :: ys => y :: func ys xs
termination_by _ x y => x.length + y.length
my intuition was that i could prove the following:
theorem test
(x y : a)
(xs ys : List a)
: func (x :: xs) (y :: ys) = y :: func ys (x :: xs)
:= rfl
however, this does not work. the fact that i am trying to prove is obviously true (replacing rfl
with by simp [func]
fixes the error) but i'm curious about why simply using rfl
does not work here. my best guess is that this has to do with the fact that func
needs a termination_by
clause, but i'm not sure if that's right
Last updated: Dec 20 2023 at 11:08 UTC