[Agda] algebra hierarchy in library

Sergei Meshveliani mechvel at botik.ru
Wed Mar 20 15:39:53 CET 2019


On Wed, 2019-03-20 at 11:44 +0800, Matthew Daggitt wrote:
> Say you have a module and you want to parameterise it by a semigroup
> that must use propositional equality. How would you do that using your
> hierarchy?


Let me try. 
The prelude is the definition of Magma and Semigroup by the approach II:
a) with isMagma, b) without isSemigroup, 
     c) without repeating fields. 

Then,  module Semigroup≡  is a submodule in  module Magma≡.
But it can be also declared as a top level module, with joining
parameters C, _∙_, isMagma≡.

What is wrong here?

--
SM
 

--====================================================================
open import Level using (suc; _⊔_) 
open import Algebra.FunctionProperties as FuncProp using (Op₂)
open import Relation.Binary using (_Preserves₂_⟶_⟶_; Setoid) 
open import Relation.Binary.PropositionalEquality as PE using (_≡_)

record IsMagma {α α=} (S : Setoid α α=) (_∙_ : Op₂ (Setoid.Carrier S)) :
                                                           Set (α ⊔ α=)
  where
  open Setoid S using (_≈_; Carrier)
  field
    ∙-cong : _∙_ Preserves₂ _≈_ ⟶ _≈_ ⟶ _≈_

record Magma α α= :  Set (suc (α ⊔ α=))  
  where                            -- non-standard but with `isMagma'
  constructor magma′
  
  field  setoid : Setoid α α=

  open Setoid setoid public
  infixl 7 _∙_

  field  _∙_     : Op₂ Carrier
         isMagma : IsMagma setoid _∙_


record Semigroup α α= :  Set (suc (α ⊔ α=))  -- without `isSemigroup'
  where                                         
  constructor semigroup′
  
  field magma : Magma α α=

  open Magma magma using (_≈_; _∙_)
  module FP≈ = FuncProp _≈_

  field ∙-assoc : FP≈.Associative _∙_  


-- The proper part =================================================
-- Magma≡  is parameterized by a certain representation of arbitrary 
--         magma over _≡_.

module Magma≡ {α} (C : Set α) (_∙_ : Op₂ C)
                  (let setoid≡ = PE.setoid C)
                  (isMagma≡ : IsMagma setoid≡ _∙_)
  where
  magma≡ :  Magma α _
  magma≡ =  magma′ setoid≡ _∙_ isMagma≡

  module FP≡ =  FuncProp (_≡_ {A = C})
 
  -------------------------------------------------------------------
  -- Semigroup≡  is parameterized by a certain representation of
  --             arbitrary semigroup over _≡_,
  -- and  semigroup≡  below is an arbitrary semigroup over _≡_. 
  
  module Semigroup≡ (∙assoc : FP≡.Associative _∙_)
    where
    semigroup≡ :  Semigroup α _
    semigroup≡ =  semigroup′ magma≡ ∙assoc

    {-
    ...
    -}
--------------------------------------------------------------------






> On Sun, Mar 17, 2019 at 2:52 AM Sergei Meshveliani <mechvel at botik.ru>
> wrote:
> 
>         On Sat, 2019-03-16 at 18:16 +0800, Matthew Daggitt wrote:
>         >[..]
>         
>         >         If this is the only reason, then it occurs that `Is'
>         structure
>         >         is needed only in few cases.
>         > 
>         > 
>         > I think your examples miss the point. For example take any
>         binary
>         > operator. That binary operator may form many different
>         > Semigroups/Monoids/Groups etc. depending on what the
>         underlying
>         > equality is. The `Is` structures allow you to expose which
>         equality
>         > you're using at a particular point, whereas your suggestion
>         would hide
>         > it.
>         
>         
>         A Semigroup can be only on some (magma : Magma _ _). This
>         `magma'
>         already has an instance of _≈_ and of _∙_. 
>         What freedom has one to define  (H : Semigroup _ _)  on this
>         particular
>         (magma : Magma _ _) ?
>         The only freedom is to choose a proof for  Associative _≈_
>         _∙_,
>         because _≈_ and _∙_ are already fixed, they are brought in by 
>         "open Setoid setoid ...".
>         So the matter here is only in the proof relevance.
>         
>         For defining Magma on the given (S : Setoid), there is more
>         freedom.
>         _≈_ is fixed, but _∙_ may be implemented in different ways.
>         
>         
>         > The `Is` structures allow you to expose which equality
>         you're using at
>         > a particular point, whereas your suggestion would hide it.
>         
>         No, in the experimental tower (let us call it so) the equality
>         and all
>         operations are exposed by the `open' declaration:
>         
>         -- experimental
>         ------------------------------------------------------- 
>         
>         record IsMagma {α α=} (S : Setoid α α=) (_∙_ : Op₂
>         (Setoid.Carrier S)) :
>                                                                    Set
>         (α ⊔ α=)
>           where
>           open Setoid S using (_≈_; Carrier)
>           field
>             ∙-cong : _∙_ Preserves₂ _≈_ ⟶ _≈_ ⟶ _≈_
>         
>         record Magma α α= :  Set (suc (α ⊔ α=))
>           where
>           field  setoid : Setoid α α=
>         
>           open Setoid setoid public
>           infixl 7 _∙_
>         
>           field  _∙_     : Op₂ Carrier
>                  isMagma : IsMagma setoid _∙_
>         
>         record Semigroup α α= :  Set (suc (α ⊔ α=))    -- non-standard
>           where
>           field magma : Magma α α=
>         
>           open Magma magma using (_≈_; _∙_)
>           module FP≈ = FuncProp _≈_
>         
>           field ∙-assoc : FP≈.Associative _∙_
>         --------------------------------------------------------------------------
>         
>         Here IsMagma (isMagma) is preserved as in standard, because
>         this enables
>         us to define different Magmae on the same (S : Setoid).
>         But IsSemigroup (isSemigroup) is skipped, because it is not
>         possible to
>         define different semigroups on the given (magma : Magma)
>         -- if only we ignore difference in proofs for FP≈.Associative
>         _∙_.
>         
>         Now I think that IsSemigroup is all right.
>         But repeated fields of Carrier, _≈_, and such, look strange to
>         me.
>         
>         Regards,
>         
>         ------
>         Sergei
>         
>         
>         




More information about the Agda mailing list