[Agda] double constructor termination

Sergei Meshveliani mechvel at botik.ru
Mon May 2 11:47:23 CEST 2016


Hi,  

Can people advise, please, on the following subject?
The below program can be rewritten with removing a double `suc' pattern.
But let it be a contrived example:

------------------------------------------------------------------
open import Relation.Binary.PropositionalEquality as PE using (_≡_)
open import Data.Nat using (ℕ; suc; _+_; _≤_; pred)

open _≤_

lemma :  ∀ n → n ≤ n + 1
lemma 0             =  z≤n
lemma 1             =  s≤s z≤n
lemma (suc (suc n)) =  s≤s n'≤n'+1  where
                                    n'≤n'+1 = lemma (suc n)
------------------------------------------------------------------

Agda does not see termination here.
What is the nicest way to prove termination with preserving this suc-suc
pattern?
I write it this way: 

--------------------------------
lemma n =  aux n (pred n) PE.refl
  where
  aux : (n m : ℕ) → m ≡ pred n → n ≤ n + 1
  aux 0             _  _    =  z≤n
  aux 1             _  _    =  s≤s z≤n
  aux (suc (suc n)) 0  ()
  aux (suc (suc n)) (suc m) m'≡pred-n'' =  s≤s n'≤n'+1
                               where
                               m≡pred-n' = PE.cong pred m'≡pred-n''
                               n'≤n'+1   = aux (suc n) m m≡pred-n'
---------------------------------

And it looks awkward.

Thanks, 

------
Sergei 




More information about the Agda mailing list