[Agda] termination for nested construct
Sergei Meshveliani
mechvel at botik.ru
Thu Nov 27 14:05:13 CET 2014
People,
I have a recursion of kind
f : Foo → Set
f (foo (foo' (x ∷ xs) prop'-x:xs) prop-x:xs) = ...
where
d = f (foo (foo' xs prop'-xs) prop-xs)
...,
where foo and foo' are the two record constructors, and recursion is
by changing x :: xs --> xs.
Agda-2.4.2.2 does not see termination here.
What is the simplest method to prove termination for f ?
I apply the following approach. Extract xs from the Foo data and use
it as an additional argument in 'prove'. But this needs also to equate
this argument in `prove' to the list in the Foo data. So that the
function becomes
f (foo (foo' xs prop') prop) =
prove (foo (foo' xs prop') prop) xs PE.refl
where
prove : (d : Foo) → (xs : List C) → list d ≡ xs → Set
prove _ [] _ = =foo-refl
prove (foo (foo' (x ∷ xs) prop'x:xs) prop-x:xs)
(.x ∷ .xs) PE.refl = ...
where
... prove (foo (foo' xs prop'xs) prop-xs) xs PE.refl
Is there possible a simpler method?
Thanks,
------
Sergei
More information about the Agda
mailing list