[Agda] Setoid for List

Serge D. Mechveliani mechvel at botik.ru
Wed Jan 9 11:28:12 CET 2013


On Wed, Jan 09, 2013 at 10:19:33AM +0100, Joachim Breitner wrote:
> Hello,
> 
> Am Dienstag, den 08.01.2013, 20:35 +0400 schrieb Serge D. Mechveliani:
> > If it does not, then is the following a reasonable program for this?
> > 
> >   listSetoid : {c l : Level} -> DecSetoid c l -> Setoid _ _
> >   listSetoid A = record{ Carrier       = List ACarr 
> >                        ; _\~~_         = eqList               
> >                        ; isEquivalence = isEquiv } 
> >       where    
> >       ACarr = DecSetoid.Carrier A                                   
> >       open DecSetoid {{...}}                                         
> >       eqList : Rel (List ACarr) _                                       
> >       eqList []        []        = \top                          
> >       eqList []        (_ :: _)  = \bot                                   
> >       eqList (_ :: _)  []        = \bot                                 
> >       eqList (x :: xs) (y :: ys)  with x \?= y                            
> >       ...                       | yes _ = eqList xs ys                    
> >       ...                       | _     = \bot
> >                                                                               
> >       isEquiv : IsEquivalence eqList            
> >       isEquiv =  <a proof, which I would have to set if not find in 
> >                   libraries>
> 
> I don't think you need DecSetoid to define Setoid for Lists. Here is my
> solution requiring only Setoid on the element types:
> 
> listSetoid : {c l : Level} -> Setoid c l -> Setoid _ _
> listSetoid {c} {l} A =
> [..]

>     open Setoid A
>     eqList : Rel (List ACarr) l                                    
>     eqList []        []       = Lift \top
> [..]
>     eqList (x :: xs) (y :: ys)  = x \~~ y \times eqList xs ys
>   

(I have substituted some math symbols).

I know this. But I doubt about efficiency for long lists.

 
> I also tried to give isEquiv, and it seems it worked, but agda still
> highlights eqRefl, eqSym and eqTrans in the last line as yellow, and I
> do not know why:
> [..]

I fear I would need to set some similar code.
But it is desirable to have such in the Standard Library for Agda.
Say,  Setoid, DecSetoid, TotalOrder ...  for  Product, List, Vector
-- these instances are very generic and fundamental.
My main question was: which of them are in the libraries?

Regards,

------
Sergei


More information about the Agda mailing list