[Agda] On termination checkers

Andrew Pitts andrew.pitts at cl.cam.ac.uk
Mon Jun 10 16:06:12 CEST 2019



> On 10 Jun 2019, at 14:11, david.janin at labri.fr wrote:
> 
> Indeed, with sized types. 
> 
> For the record, Guillaume Allais suggested this to me. 
> His solution is (I think) worth being posted for newbies as I am for it is a fairly simple example of sized type usage with simple inductive data type.

I have been working quite a lot recently with inductive definitions involving sized types and when I started I could find rather few examples to help me (compared with the number of examples of using sized types with coinductive definitions). One thing I have learnt by trial and error is to try to make sizes parameters rather than indices in data definitions (avoiding mentioning ↑ explicitly as much as possible).

So I would write your example as

——————————————————————————————
open import Agda.Builtin.Size

data Pack (A : Set) : Set where
  pack : A -> Pack  A

unpack : ∀ {A} -> Pack A -> A
unpack (pack a) = a

data PList (A : Set)(i : Size) : Set where
 pnil  : PList A i 
 pcons : ∀{j : Size< i} → A -> Pack (PList A j) -> PList A i

pappend : ∀ {A i} -> PList A i -> PList A _ -> PList A _
pappend pnil         l = l
pappend (pcons a pp) l = pcons a (pack (pappend (unpack pp) l))
——————————————————————————————

although I doubt that in this case it make that much difference.

Perhaps an expert can comment on the pros and cons.

Andy


> -----------------------------------------------------------------------
> open import Size
> 
> data Pack (A : Set) : Set where
> pack : A -> Pack  A
> 
> unpack : ∀ {A} -> Pack A -> A
> unpack (pack a) = a
> 
> data PList (A : Set) : Size → Set where
>  pnil  : ∀ {i} → PList A (↑ i) 
>  pcons : ∀ {i} → A -> Pack (PList A i) -> PList A (↑ i)
> 
> pappend : ∀ {A i} -> PList A i -> PList A _ -> PList A _
> pappend pnil         l = l
> pappend (pcons a pp) l = pcons a (pack (pappend (unpack pp) l))
> -----------------------------------------------------------------------



More information about the Agda mailing list