[Agda] Termination problems with "with" and recursion

Jan Stolarek jan.stolarek at p.lodz.pl
Sun Dec 1 10:02:54 CET 2013


> Ulf recently changed Agda to reduce the need for workarounds:
>
>    Issue 59: Improving termination checking of functions defined using
>              with
>    http://code.google.com/p/agda/issues/detail?id=59
>
> You may want to try the latest development version.
I just installed the latest version from repository and indeed there are improvements. Agda no 
longer complains about:

merge : List Nat → List Nat → List Nat
merge nil       ys             = ys
merge xs        nil            = xs
merge (x :: xs) (y :: ys) with order x y
merge (x :: xs) (y :: ys) | le = x :: merge xs (y :: ys)
merge (x :: xs) (y :: ys) | ge = y :: merge (x :: xs) ys

but it still complains about this:

mergeO : {b : Nat} → OList b → OList b → OList b
mergeO onil ys = ys
mergeO (ocons x blex xs) onil = ocons x blex xs
mergeO (ocons x blex xs) (ocons y bley ys) with orderD x y
mergeO (ocons x blex xs) (ocons y bley ys) | le xley =
  ocons x blex (mergeO xs (ocons y xley ys))
mergeO (ocons x blex xs) (ocons y bley ys) | ge ylex =
  ocons y bley (mergeO (ocons x ylex xs) ys)

I presume the reason is that parameter to recursive call is not an exact reconstruction of the 
input parameter (notice how bley is replaced by xley or blex by ylex). Idris is smarter here and 
correctly detects that mergeO is total.

Janek


More information about the Agda mailing list