blob: 8e1c1315b760f07f5aca40356577f7dc7845f387 [file] [edit]
universe u
def concat {α} : List α → α → List α
| [], a => [a]
| x::xs, a => x :: concat xs a
def last {α} : (xs : List α) → xs ≠ [] → α
| [], h => by contradiction
| [a], h => a
| _::a::as, h => last (a::as) (fun h => by injection h)
def dropLast {α} : List α → List α
| [] => []
| [a] => []
| a::as => a :: dropLast as
variable {α}
theorem concatEq (xs : List α) (h : xs ≠ []) : concat (dropLast xs) (last xs h) = xs := by
match xs, h with
| [], h => contradiction
| [x], h => rfl
| x₁::x₂::xs, h => simp [concat, dropLast, last, concatEq (x₂::xs)]
theorem lengthCons {α} (x : α) (xs : List α) : (x::xs).length = xs.length + 1 :=
rfl
theorem eqNilOfLengthZero {α} : (xs : List α) → xs.length = 0 → xs = []
| [], h => rfl
| x::xs, h => by rw [lengthCons] at h; contradiction
theorem dropLastLen {α} (xs : List α) : (n : Nat) → xs.length = n+1 → (dropLast xs).length = n := by
match xs with
| [] => intros; contradiction
| [a] =>
intro n h
have : 1 = n + 1 := h
have : 0 = n := by injection this
subst this
rfl
| x₁::x₂::xs =>
intro n h
cases n with
| zero =>
simp at h
| succ n =>
have : (x₁ :: x₂ :: xs).length = xs.length + 2 := by simp
have : xs.length = n := by rw [this] at h; injection h with h; injection h
simp [dropLast, dropLastLen (x₂::xs) xs.length (lengthCons ..), this]
@[inline]
def concatElim {α}
(motive : List α → Sort u)
(base : Unit → motive [])
(ind : (xs : List α) → (a : α) → motive xs → motive (concat xs a))
(xs : List α)
: motive xs :=
let rec @[specialize] aux : (n : Nat) → (xs : List α) → xs.length = n → motive xs
| 0, xs, h => by
have aux := eqNilOfLengthZero _ h
subst aux
apply base ()
| n+1, xs, h => by
have notNil : xs ≠ [] := by intro h1; subst h1; injection h
let ih := aux n (dropLast xs) (dropLastLen _ _ h)
let aux := ind (dropLast xs) (last xs notNil) ih
rw [concatEq] at aux
exact aux
aux xs.length xs rfl
-- The generated code is tail recursive
def test (xs : List Nat) : IO Unit :=
concatElim (motive := fun _ => IO Unit)
(fun _ => pure ())
(fun xs x r => do IO.println s!"step xs: {xs} x: {x}"; r)
xs
/--
info: step xs: [1, 2, 3] x: 4
step xs: [1, 2] x: 3
step xs: [1] x: 2
step xs: [] x: 1
-/
#guard_msgs in
#eval test [1, 2, 3, 4]