[Agda] Termination

Geoffrey Alan Washburn geoffrey.washburn at epfl.ch
Mon Jun 2 12:48:21 CEST 2008


I've just encountered my first problem with termination.  Here is a 
really simplified example of the problem:

   Test where
   open import Data.List
   open import Data.Nat

   data Tree : Set where
     Leaf : ℕ -> Tree
     Node : [ Tree ] -> Tree

   inc : Tree -> Tree
   inc (Leaf n) = Leaf (n + 1)
   inc (Node ts) = Node (Data.List.map inc ts)

Essentially, it seems that Agda cannot tell that passing inc to map will 
be terminating.  It does not seem to be an issue of modularity 
preventing unwinding, as I can define my own list data type and map in 
the same file and it still flags it as non-terminating.

This kind of recursion is not a problem for Coq's termination checker, 
at least as long as you've defined map properly, so is there something I 
am just doing incorrectly here?  Or is the only solution here to define 
a specialized version of map mutually recursively with inc?



More information about the Agda mailing list