[Agda] Simple monoid instance based on monoid instance of underlying type

James ‘Twey’ Kay twey at twey.co.uk
Sun Jan 12 13:30:33 CET 2014


In Agda you also have to lift the laws into your new type.  Unless 
you're willing to go into HoTT, as far as I can tell you need to lift it 
manually:


```

module Identity where

open import Relation.Binary.PropositionalEquality
   using (_≡_; cong; cong₂; isEquivalence)
open import Algebra using (Monoid)
open import Level using (zero; suc)
open import Algebra.Structures using (IsSemigroup; IsMonoid)
open import Algebra.FunctionProperties using (Op₂; Associative)
open import Data.Product using (_,_; proj₁; proj₂)
open import Function using (_∘_)

record Id {ℓ} (A : Set ℓ) : Set (suc ℓ) where
   constructor I
   field
     unI : A

lift-Op₂ : ∀ {ℓ} {A : Set ℓ} → Op₂ A → Op₂ (Id A)
lift-Op₂ _∙_ a b = I (Id.unI a ∙ Id.unI b)

lift-Associative : ∀ {ℓ} {A : Set ℓ} {∙ : Op₂ A}
   → Associative _≡_ ∙ → Associative _≡_ (lift-Op₂ ∙)
lift-Associative a∙ =
   λ x y z → cong I (a∙ (Id.unI x) (Id.unI y) (Id.unI z))

lift-IsSemigroup : ∀ {ℓ} {A : Set ℓ} {∙ : Op₂ A}
   → IsSemigroup _≡_ ∙ → IsSemigroup _≡_ (lift-Op₂ ∙)
lift-IsSemigroup {∙ = _∙_} a =
   record { isEquivalence = isEquivalence;
            assoc = lift-Associative {∙ = _∙_} (IsSemigroup.assoc a) ;
            ∙-cong = cong₂ (lift-Op₂ _∙_) }

lift-IsMonoid : ∀ {ℓ} {A : Set ℓ} {∙ : Op₂ A} {ε : A}
   → IsMonoid _≡_ ∙ ε → IsMonoid _≡_ (lift-Op₂ ∙) (I ε)
lift-IsMonoid a =
   record { isSemigroup = lift-IsSemigroup (IsMonoid.isSemigroup a);
            identity = cong I ∘ proj₁ (IsMonoid.identity a) ∘ Id.unI ,
                       cong I ∘ proj₂ (IsMonoid.identity a) ∘ Id.unI }

lift-Monoid : ∀ {ℓ} {A : Set ℓ} {∙ : Op₂ A} {ε : A}
   → IsMonoid _≡_ ∙ ε → Monoid (suc ℓ) (suc ℓ)
lift-Monoid {_} {A} {∙} {ε} a =
   record {
     Carrier = Id A;
     _≈_ = _≡_;
     _∙_ = lift-Op₂ ∙;
     ε = I ε;
     isMonoid = lift-IsMonoid a }

```

   HoTT gives you the univalence axiom, letting you generalize this 
process when you can prove isomorphism between the types (and also 
abstract over the relation).

   HTH,
     — Twey


On 2014-01-12 09:39, Mateusz Kowalczyk wrote:
> Hi all,
> 
> I'm struggling with something that seemed like an easy task. Consider:
> 
> ```
> open import Algebra
> 
> record Input (τ : Set) : Set where
>   constructor I
>   field
>     unI : τ
> ```
> 
> I now want to give a monoid instance to this type, as long as τ can
> give me one. That is, in Haskell I could say
> 
> ```
> import Data.Monoid
> 
> newtype I t = I t
> 
> instance Monoid t => Monoid (I t) where
>   mempty = I mempty
>   I x `mappend` I y = I $ x `mappend` y
> ```
> 
> In fact, I could use the GHC extension to derive this for me. I
> thought writing an instance like this in Agda should not be a problem
> at all but I seem to be struggling. In the snippet below is my failed
> attempt to replicate what the Haskell code does. I had hoped that I
> can simply pass the Monoid (or should I be using RawMonoid?) instance
> of the underlying type and use that. My problem with this is that I
> don't seem to be able to get out anything meaningful out of the passed
> in Monoid. For example, opening the ‘m’ and trying to use ε in my
> ‘binOp’ function quickly shoots me down with the message that ‘Carrier
> ≠ τ’. I'm unsure how to tell Agda that I only want to pass in the
> Monoid instances with τ as a Carrier or how to get the value out once
> I do: the Monoid type doesn't seem to be parametrised by anything but
> Level. I struggle to find any examples in standard lib or elsewhere of
> how to use passed in instances of Monoid from Data.Algebra: all I can
> find are either usages of monoids from other libraries or short
> documents which show off Agda by rolling their own.
> 
> Here's the snippet. I imagine that the ‘monoid’ type needs fixing up
> so that I can actually use ‘m’ somehow.
> 
> I'd appreciate if someone can point me in the right direction.
> 
> ```
> module InputMonoid where
>   open import Level using (zero)
>   open import Relation.Binary.PropositionalEquality
> 
>   monoid : (τ : Set) → (m : Monoid {!!} {!!}) → Monoid zero zero
>   monoid τ m = record
>     { Carrier = Input τ
>     ; _≈_      = _≡_
>     ; _∙_      = binOp
>     ; ε        = {!!}
>     ; isMonoid = record
>       { isSemigroup = record
>         { isEquivalence = {!!}
>         ; assoc         = {!!}
>         ; ∙-cong        = {!!}
>         }
>       ; identity = {!!}
>       }
>     }
>     where
>       open Monoid m
> 
>       binOp : ∀ {τ} → Input τ → Input τ → Input τ
>       binOp (I unI) (I unI₁) = {!!}
> ```
> 
> --
> Mateusz K.
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda


More information about the Agda mailing list