[Agda] common super-structure

Sergei Meshveliani mechvel at botik.ru
Fri Sep 15 15:27:37 CEST 2017


People,

I have a question on the algebraic hierarchy architecture in Standard
library.
This concerns the problem of a common super-structure (super-class).

Consider the example:

 having  f : ∀ {c l} → Semigroup c l → Semigroup c l → Semigroup c l,
 implement 
  g : (H H' : Semigroup) → H and H' are on the same setoid → Semigroup
  g H H' =  f H H'

Consider the program

----------------------------------------------------------------------
postulate  f : ∀ {c l} → Semigroup c l → Semigroup c l → Semigroup c l

g :  ∀ {c l} → Semigroup c l → Semigroup c l → Semigroup c l  -- wrong
g H H' =  f H H'
----------------------------------------------------------------------

This will not do, because the domain of  g  is not as required.

Below  g'  pretends to implement the goal:

-------------------------------------------------------------
module CommonSuper where
open import Relation.Binary            using (Setoid)
open import Algebra                    using (Semigroup)
open import Algebra.Structures         using (IsSemigroup)
open import Algebra.FunctionProperties using (Op₂)

postulate f : ∀ {c l} → Semigroup c l → Semigroup c l → Semigroup c l

g' :  ∀ {c l} → (S : Setoid c l) → 
        let open Setoid S using (_≈_; Carrier) 
        in
        (_∙_ _∙'_ : Op₂ Carrier) → 
        IsSemigroup _≈_ _∙_ → IsSemigroup _≈_ _∙'_ → Semigroup c l   

g' S _∙_ _∙'_ isSemig isSemig' =  f H H'
                        where
                        open Setoid S using (_≈_; Carrier) 

                        H  = record{ Carrier     = Carrier
                                   ; _≈_         = _≈_ 
                                   ; _∙_         = _∙_ 
                                   ; isSemigroup = isSemig
                                   }
                        H' = record{ Carrier     = Carrier
                                   ; _≈_         = _≈_ 
                                   ; _∙_         = _∙'_ 
                                   ; isSemigroup = isSemig'
                                   }
--------------------------------------------------------------

But here  g'  is applied not to a pair of semigroups but to their rather
decomposed forms.

Further,  g''  looks as something more close to the goal: 


  g'' :  ∀ {c l} → (H H' : Semigroup c l) → 
                   let S  = Semigroup.setoid H 
                       S' = Semigroup.setoid H' 
                   in
                   (CoinverseSetoidIso S S') → Semigroup c l   

  g'' H H' _ =  f H H'


Here  isoPair : CoinverseSetoidIso S S'

is a pair of mutually inverse setoid isomorphisms between S and S'.
For the condition of "over the same setoid" it suggests to include a 
setoid isomorphism into the signature.
Still a complication. We have two different types for setoid instead of
one.

The release 0.04.1 of the DoCon-A library applies the approach in which
the Semigroup record will have (S : Setoid) as an _argument_.
And a similar construct with super-structures as arguments is repeated
for Group, Ring, and so on.
With this approach, the examples like the above  g  are programmed
easier.

But this still leads to a certain complication. Because this forces 
introduction of certain up-structures: Semigroup - UpSemigroup, 
Group - UpGroup, and so on (see Manual on DoCon-A-0.04.1).

In  DoCon-A-2.00,  I return to the approach similar to Standard library,
with adding the Is-structures (IsSemigroup, IsGroup, and such).

Anyway, a spot of inadequacy is visible.

Can anybody comment on this philosophy?

Regards,

------
Sergei




More information about the Agda mailing list