[Agda] generic type recursion

Serge D. Mechveliani mechvel at botik.ru
Mon Oct 8 21:24:49 CEST 2012


On Mon, Oct 08, 2012 at 03:03:50PM -0400, Daniel Peebles wrote:
> Nothing is constraining your recursive OrderedNatList? call to have the
> same DecTotalOrder as its implicit parameter, and the only part of that
> that appears explicitly is the Carrier (which couldn't be injective even if
> Agda did have some notion of that, because the same type might have
> multiple orderings). I'd recommend making the DecTotalOrder argument
> explicit and then providing it for your recursive case in cons.

Great! This type-checks. Thank you.
Initially, this argument   (ord : DecTotalOrder c l1 l2)  
was explicit. But the checker reported of a wrongly used indices in 
`cons'. And I did various changes, including hiding of  ord.
Now, I return to explicit  (ord : DecTotalOrder c l1 l2),   and it type-
checks.

It is difficult to believe that such a complex type system as of Agda
can be practically implemented.

Regards,
Sergei.


> On Mon, Oct 8, 2012 at 2:56 PM, Serge D. Mechveliani <mechvel at botik.ru>wrote:
[..]
> > This is a definition of what is an  ordered list of Nat elements.
> > I believe it looks natural. And it does work in my program.
> >
> > Then, I try to generalize it from  Nat  to  DecTotalOrder
> > (this uses the  DecTotalOrder record  of  Standard Library).
> > After many attempts I have wrtitten the following code which part
> > before `cons' is type-checked.
> >
> >   open DecTotalOrder
> >
> >   data OrderedList? {c l1 l2 : Level} {ord : DecTotalOrder c l1 l2} :
> >                     List (Carrier ord) -> Set (suc (max c (max l1 l2)))
> >        where
> >        nil    : OrderedList? []
> >        single : (x : Carrier ord) -> OrderedList? (x :: [])
> >        cons   : (x y : Carrier ord) -> (xs : List (Carrier ord)) ->
> >                 _<=_ ord x y ->
> >                 OrderedList? (y :: xs) ->
> >                 OrderedList? (x :: y :: xs)
[..]


More information about the Agda mailing list