[Agda] Termination proof in partiality monad

Dan Doel dan.doel at gmail.com
Wed Nov 19 11:24:12 CET 2008


Well, I've completed proving fac-↓, sort of. Here are the proofs (hopefully 
it's still properly formatted; I had to modify for 80-columns a bit):

fix-fac-↓₁ : {g : Nat -> D Nat} {n k : Nat}
           -> fix-aux g fac-aux n ↓ k
           -> fix-aux (fac-aux g) fac-aux (suc n) ↓ suc n * k
fix-fac-↓₁ {g} {n} pf with fac-aux g n
fix-fac-↓₁ {g} {n} {k} (converge-now   .k) | now   .k
        = converge-now (suc n * k)
fix-fac-↓₁ {g} {n} {k} (converge-later pf) | later dx
        = converge-later (fix-fac-↓₁ pf) -- problem 1

fac-↓ : forall {n} -> fac n ↓
fac-↓ {0}     = (1 , converge-now 1)
fac-↓ {suc n} with fac-↓ {n}
fac-↓ {suc n} | n! , pf-n!-↓
        = (suc n * n! , converge-later (fix-fac-↓₁ pf-n!-↓)) -- problem 2

Now, here's the rub: both of these don't pass type checking. However, when 
using Agda mode, with, say:

    ... converge-later {fix-fac-↓₁ pf-n!-↓ }0 ...

it *does* pass type checking, and allows insertion. However, upon reloading 
the buffer, Agda complains:

    fix-aux (fac-aux (\x -> fac-aux g x)) fac-aux (suc n)
    | map-D (_*_ (suc n)) (fac-aux (\x -> fac-aux g x) n)
    != fix-aux (fac-aux (fac-aux g)) fac-aux (suc n) of type D Nat

in the first problem area, and:

    (fix-aux (fac-aux (\x -> never)) fac-aux (suc n)
     | map-D (_*_ (suc n)) (fac-aux (\x -> never) n))
    != fix-aux (fac-aux (\_ -> never)) fac-aux (suc n) of type D Nat

in the second. Now, there are two differences I see in those types. First is 
that "\x -> fac-aux g x" is different from "fac-aux g", and "\x -> never" is 
different from "\_ -> never" purely syntactically. However, that can't be the 
problem can it? The other difference is that the former types have the with 
annotations on them. However, when the subgoal is displayed, those aren't 
present, which, I assume, is why the mode lets me put in my expressions, since 
they match the subgoal type.

So, I'm at a bit of a loss as to what's going on here. Is there a way I can 
restructure my proofs to eliminate this problem? Is it possibly a bug of some 
sort?

Thanks for your help.
-- Dan


More information about the Agda mailing list