[Agda] Strict positivity and indices

Nils Anders Danielsson nad at chalmers.se
Wed May 9 20:01:13 CEST 2012


On 2012-05-09 18:37, Dan Doel wrote:
> The Agda equivalent is:
>
>      data Val : Set where
>        nat : ℕ ->  Val
>        vec : (l : List Val) ->  0<  length l ->  Val
>
> Coq rejects this as not being strictly positive. Agda doesn't complain.

Agda remembers how the arguments to _<_ and length are used, and deduces
that the definition is strictly positive.

Recently I discovered that the computation of this information can take
huge amounts of time. You can use -vtc.pos.graph:5 to see the sizes of
the positivity graphs that are constructed. The /transitive closures/ of
these graphs are used to find out how arguments are used.

I have optimised this machinery, so some code type-checks much faster
with the development version than with 2.3.0. However, these
computations can still be very time-consuming.

-- 
/NAD



More information about the Agda mailing list