[Agda] Non-termination help!

Martín martin at dcc.fceia.unr.edu.ar
Wed Dec 6 14:56:12 CET 2017


Hello everyone. I am struggling with Agda's termination checker.

The idea is to define a recursive function like *size* over terms µ S 
for some signature S (definitions are bellow). I can destruct (t : µ S) 
to obtain some symbol and its 'arguments', such arguments should be 
smaller since µ S is strictly positive. Therefore, I should be able to 
recursively call size, right?.

Here is an example where I leave the holes to be filled. I have tried 
different approaches to help the termination checker such as views and 
sized types. Sized types fix these simple functions, but it complicates 
matters in further proofs.

Cheers,

Martín.

----

module Q where

open import Data.Vec
open import Data.Nat

open import Level renaming (zero to lzero ; suc to lsuc)

record Signature : Set (lsuc lzero) where
   constructor sig
   field
     σ : Set
     arity : σ -> ℕ

record Σ (Sig : Signature) (X : Set) : Set where
   constructor _,_
   field
     C : Signature.σ Sig
     as : Vec X (Signature.arity Sig C)

data µ (S : Signature) : Set where
   In : Σ S (µ S) -> µ S

size : {S : Signature} -> µ S -> ℕ
size (In (C , as)) = suc (sum (map {!size!} as))

size' : {S : Signature} -> µ S -> ℕ
size' {sig σ arity} (In (C , as)) with arity C
size' {sig σ arity} (In (C , [])) | zero = 0
size' {sig σ arity} (In (C , (x ∷ as))) | suc arC = suc (sum (map 
{!size'!} (x ∷ as) ))



More information about the Agda mailing list