[Agda] standard instance proposal

Serge D. Mechveliani mechvel at botik.ru
Thu Jan 10 16:09:16 CET 2013


People,

Here is a certain  Product & List instance  proposal for 
Standard Library.

(I)
  productSetoid : {c l c' l' : Level} -> (A : Setoid c  l ) -> 
                                         (B : Setoid c' l') -> Setoid _ _

builds the setoid  A x B  for setoids A and B  defined by the standard
law for direct product
(is such in the library?).

The precise code is attached to this letter.


(II) listSetoid  for  List   needs to be defined similarly 
     (Erdi Gergo has recently sent the code). 
     (is such in the library?).

(III)
  setoidByMap : {c c' l' : Level} -> (C : Set c) -> (B : Setoid c' l') ->
                                     (C -> Setoid.Carrier B) -> Setoid _ _

builds the setoid  A  on  C  from a setoid  B  and a map 
f : C -> Carrier B   -- in a natural way:
a =C a' =  f a \~~ f a'.    

(is such in the library?).

The precise code zip archive is attached to this letter.
The code for  productSetoid  is of  40 lines, with comments,  
         for  setoidByMap    --     10 lines.

(VI) A similar instance map can be applied for  Semigroup, Group, 
     and some other Standard Library instances
     (direct product of Groups,  
      Ring of  R x R x ... x R  build via the instance map for Vector,
      and such
     ).
     
About generic programming
-------------------------
This is the generic programming of which  Joachim Breitner wrote recently:
 
> to me it rather seems that there is a need for some generic programming,
> i.e. a solution that works for all algebraic data types, or at least for
> simple enough ones such as List or the simple data type Gen 
> [..]

I have the two questions.

1. The  Haskell  library has the constructor class  Functor  which allows 
to apply  fmap  (as `map') not only to List but uniformly, to  List, 
Maybe a,  to any type constructor of the class Functor.
Is this of this generic programming ?

2. Concerning  setoidByMap :
it spreads the Setoid instance from  x (Product)  and  List  to a great 
family of constructs (by any map, by surjection, by bijection).

Does this `by map' approach replace the generic programming mentioned by 
Joachim Breitner ?

Here is an example of usage.
I have 
  record UMonomial {c l : Level} {dS : DSet c l} (R : Prering c l {dS}) :
                                                                    Set _ 
       where
       private decS = DSet.decSetoid dS
               0#   = Prering.0# R
       open DecSetoid {{...}}
       field  coef    : Carrier
              exp     : Nat
              coef/=0 : \neg (coef \~~ 0#) 

-- a monomial consists of a non-zero coefficient  coef : R  and  
exponent  exp : Nat.

The following function uses  productSetoid  and  setoidByMap  to build 
the setoid for  UMonomial R: 

  uMon-setoid : {c l : Level} -> (R : Prering c l) -> Setoid _ _
  uMon-setoid R =  setoidByMap (UMonomial R) R-x-Nat-setoid toProduct
    where
    natSetoid = <extract  Setoid  for  Nat  from Standard Library>
    decS      = Prering.decSetoid R  
    open DecSetoid decS renaming (Carrier to R-Carrier; 
                                                     setoid to R-setoid)
    R-x-Nat-setoid = productSetoid R-setoid natSetoid 
    open UMonomial
    toProduct : UMonomial R -> R-Carrier x Nat 
    toProduct mon = (coef mon , exp mon)

I propose 
(1) To include  setoidByMap, productSetoid, listSetoid, vectorSetoid,
    to the Standard Library
    (the code for the first three is ready),

(2) to do the same for DecSetoid,

(3) to consider including to the Standard Library similar functions for 
    Ordering, Semigroup, Group ...

As to (3), I need to add the folowing comment.
I am trying to build the classical algebraic hierarhy of  Set, Semigroup, 
Group, ... SuchAndSuchRing, Field, LeftModuleOverRing, ...,  
and need to somewhat extend with certain additional attributes each of the 
Standard library `classes' of  Semigroup, Monoid, ..., CommutativeRing.
And so far, I fail to use the corresponding Standard classes as they are. 
So I try their modifications:  DSet, DSemigroup, DMonoid ...

Regards,

------
Sergei
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sugg.agda.zip
Type: application/zip
Size: 1042 bytes
Desc: not available
Url : http://lists.chalmers.se/pipermail/agda/attachments/20130110/aa4f3e14/sugg.agda.zip


More information about the Agda mailing list