[Agda] Guardedness-preserving type constructors

Thorsten Altenkirch txa at Cs.Nott.AC.UK
Mon Apr 5 17:49:46 CEST 2010


On 5 Apr 2010, at 13:48, Nils Anders Danielsson wrote:
> One of the new features implemented during AIM XI was
> "guardedness-preserving type constructors". Thorsten wanted to be able
> to write ΠΣ code in Agda; in particular, he wanted to be able to  
> define
> types recursively. Now he can.
>
> If the new flag --guardedness-preserving-type-constructors is used,  
> then
> type constructors are treated as inductive constructors when we check
> productivity (but only in parameter positions, and only if the
> parameters are used strictly positively or not at all). This makes
> examples such as the following possible:
>
> data Rec (A : ∞ Set) : Set where
> fold : ♭ A → Rec A

The example which motivated my suggestion was a Universe of concrete  
datatypes with decidable equality:

mutual

data Data : Set where
  empty : Data
  maybe : ∞ Data -> Data
  sigma : (A : Data) → (El A → Data) -> Data

El : Data → Set
El empty = ⊥
El (maybe A) = Rec (♯ Maybe (El (♭ A)))
El (sigma A B) = Σ (El A) (λ a → El (B a))

Previously, I believe, it was impossible to define this universe due  
to the presence of infinite types guarded by maybe.

I also have defined

eq : ∀ {A} → El A → El A → Bool

together with

rfl : ∀ {A} → (a : El A) → T (eq a a)
sbst : ∀ {A}(B : El A → Set) → (a a' : El A) → T (eq a a') →  
B a → B a'

but alas the $%^$@! termination checker isn't happy about my code (I  
know how to fix this but I think it is rather the checker which needs  
fixing).

Cheers,
Thorsten



More information about the Agda mailing list