[Agda] Size change of higher order arguments

Shin-Cheng Mu scm at iis.sinica.edu.tw
Thu Apr 24 02:08:52 CEST 2008


Hi,

The proposition Acc _<_ x states that x is "accessible" -- that is,
every element smaller than x is accessible. The following definition
is similar to the one in Logic.Induction.WellFounded:

   data Acc {a : Set}(_<_ : a -> a -> Set) : a -> Set where
     acc : (x : a) -> (forall y -> y < x -> Acc _<_ y) -> Acc _<_ x

We can define a fold for acc:

   acc-fold : {a : Set} (_<_ : a -> a -> Set) {P : a -> Set} ->
     ((x : a) -> (forall y -> y < x -> P y) -> P x) ->
       (z : a) -> Acc _<_ z -> P z
   acc-fold _<_ =A3X z (acc h) =3D
     =A3X z (\y y<z -> acc-fold _<_ =A3X y (h y y<z))

The definition passes the termination check, as I had wished.
However, I am curious why. In the recursive call:

    acc-fold _<_ =A3X y (h y y<z)

the third argument "h y y<z" does not seem structurally
"smaller" than "acc h", in the same way "n" is smaller than
"suc n", for example.

I had an impression that Agda uses a kind of size-change termination.
How is size-change of higher order arguments defined?
Is the termination checker of Agda documented somewhere?

Thanks.

best regards,
Shin




More information about the Agda mailing list