[Agda] direct product for list

Serge D. Mechveliani mechvel at botik.ru
Sun Oct 7 16:49:40 CEST 2012


Can you, please, answer a beginner question about the type for an 
ordered-list proof? 

First, I define of what is a  natural list ordered by <= : 
(for this letter I change  \bn -> Nat,  \<= to <=,  \_2 -> -2 ) 

  data OrderedList? : List Nat -> Set
       where
       nil    : OrderedList? []
       single : (x : Nat)  -> OrderedList? (x :: [])
       prep2  : (x y : Nat) -> (xs : List Nat) -> x <= y ->
                OrderedList? (y :: xs) -> OrderedList? (x :: y :: xs)

And I manage to use this definition in practice. For example,

  -- x :: xs  is ordered  ==>  xs  is ordered
  tailOrdered : {x : Nat} {xs : List Nat} -> OrderedList? (x :: xs) ->
                                                      OrderedList? xs
  tailOrdered (single _)                = nil
  tailOrdered (prep2 x y xs _ ord-y:xs) = ord-y:xs

  -- xs  is ordered  ==>  0 :: xs  is ordered
  prep0Ordered : {xs : List Nat} -> OrderedList? xs -> 
                                                  OrderedList? (0 :: xs)
  prep0Ordered nil                        = single 0
  prep0Ordered (single x)                 = prep2 0 x [] z<=n $ single x
  prep0Ordered (prep2 x y xs x<=y ord-y-xs) = 
                                            prep2 0 x (y :: xs) z<=n
                                            (prep2 x y xs x<=y ord-y-xs)


But then, I thought of the definition via the direct product (\times):

  OrderedList'? : List Nat -> Set
  OrderedList'? []             =  \top
  OrderedList'? (x :: [])      =  \top \times \top
  OrderedList'? (x :: y :: xs) =  x <= y \times (OrderedList'? (y :: xs))

It looks simpler, it does not introduce new constructors.
But I fail to process its data, so far. For example,

  tailOrdered' : {x : Nat} {xs : List Nat} -> OrderedList'? (x :: xs) ->
                                                        OrderedList'? xs
  tailOrdered' = proj-2

is not compiled: 
   OrderedList'? (.x :: .xs) !=< \Sigma _154 _155 of type Set
   when checking that the expression proj-2 has type
   OrderedList'? (.x :: .xs) -> OrderedList'? .xs

The expression   tailOrdered' ( _ , tl ) = tl                                

also is not compiled, it reports of a wrong pattern.

Is not  OrderedList'? (x :: xs)  a direct product of two types
(so that its member is a pair  ( _ , tl ) ) 
?
How to fix this?

Which definition of an  ordered natural list  is better to use?

Thank you in advance for explanation,

------
Sergei



More information about the Agda mailing list