[Agda] Positivity checker
Wouter Swierstra
wss at cs.nott.ac.uk
Thu Dec 4 17:31:54 CET 2008
When I define the following data type in Agda, the positivity checker
complains:
data Data : Nat -> Set where
Base : Data Zero
Step : forall {n} -> (Data n -> Data n) -> Data (Succ n)
This declaration reeks of negativity, but on closer inspection it
shouldn't really be a problem. The index limits the amount of
recursion that can be done. You run into problems immediately if you
try to do things like:
app : forall {n} -> Data n -> Data n -> Data n
app (Constructor f) x = f x
omega : forall {n} -> Data (Succ n)
omega = Constructor (\d -> app ? d)
The indexing prevents the usual "self-application" from type checking.
I suppose I could define a function into Set instead of a data type,
but I'd much rather work with data (the example I have in mind is
pretty complicated).
Is there a way to define this kind of data type without switching off
the positivity checker? Thanks,
Wouter
More information about the Agda
mailing list