[Agda] common super-structure

Guillaume Allais gallais at cs.ru.nl
Mon Sep 18 13:59:58 CEST 2017


Hi Sergei,

I don't really have an informed opinion on the two different approaches
but something I noticed while I was preparing the PR for the stdlib's
structure homomorphisms is that Agda will accept a record definition
with missing fields as long as they can be resolved by unification.

This means in particular that the where-clause of your g' can be reduced
to (this pattern should maybe be given a toplevel definition called
"mkSemigroup"):

==========================================================
  H  = record{ isSemigroup = isSemig
             }
  H' = record{ isSemigroup = isSemig'
             }
==========================================================

Given that this gets rid of a lot of the repetitions (at least in the
term fragment, if not the type one) it may make the stdlib's approach
more tractable for you.

Best,
--
gallais


On 15/09/17 15:27, Sergei Meshveliani wrote:
> 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
>
>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <http://lists.chalmers.se/pipermail/agda/attachments/20170918/341885bc/attachment.sig>


More information about the Agda mailing list