[Agda] on parametric modules

Sergei Meshveliani mechvel at botik.ru
Mon Jun 8 18:41:08 CEST 2015


Can people, please, explain,
why the attached code produces  "unsolved metas" ?

This is 210 lines for Agda 2.4.2.3.

Unsolved metas is reported for the last line:

  fromAsd-isInj : IsInjective fromAsd
  fromAsd-isInj = fromAsd-isInjective
                                                          

Remarks
-------                                                                         
Changing  fromAsd-isInjective  to  ≈→~asd  makes it type-checked.
fromAsd-isInjective  is imported from  OfAssociated,  where it is
defined as  ≈→~asd.
And importing  ≈→~asd  from  OfAssociated  and setting it in place of
fromAsd-isInjective  makes it type-checked.

It was said that this is probably due to that
"instantiating parameterised modules changes metavariable resolution".

Can you, please, explain this on this example
(which, I think, is small enough).

Thanks,

------
Sergei

-------------- next part --------------
module ParamModQuest where
   
open import Level    using (Level; _⊔_) renaming (suc to sucL) 
open import Function using (id; _$_; _∘_; _on_)
open import Algebra.FunctionProperties as FP using (Op₂)
open import Relation.Nullary using (¬_; Dec; yes; no) 
open import Relation.Unary   using (Decidable)
open import Relation.Binary  using 
     (Rel; Reflexive; Symmetric; Transitive; module IsEquivalence; 
      IsEquivalence; Setoid; module Setoid; _Preserves_⟶_; _Preserves₂_⟶_⟶_;
      _Respects_
     )
     renaming (Decidable to Decidable₂)

open import Relation.Binary.PropositionalEquality as PE using (_≡_) 
import Relation.Binary.EqReasoning as EqR
open import Data.Product using (_×_; _,_; ∃; proj₁; proj₂; Σ; uncurry)
open PE.≡-Reasoning renaming (_≡⟨_⟩_ to _≡[_]_; begin_ to ≡begin_;
                                                                 _∎ to _≡end)



--****************************************************************************
module OfCongMap {α α= β β=} (From : Setoid α α=) (To : Setoid β β=) 
  where 
  open Setoid From using () renaming (Carrier to A; _≈_ to _=a_) 
  open Setoid To   using () renaming (Carrier to B; _≈_ to _=b_) 

  IsInjective : (A → B) → Set (β= ⊔ α= ⊔ α)
  IsInjective f =  {x x' : A} → f x =b f x' → x =a x'



--============================================================================
_Respects2_ : ∀ {a ℓ₁ ℓ₂} {A : Set a} → Rel A ℓ₁ → Rel A ℓ₂ → Set _
_Respects2_ _~_ _≈_ =
                      ∀ {x x' y y'} → x ≈ x' → y ≈ y' → x ~ y → x' ~ y'

isUnity : ∀ {α α=} (A : Setoid α α=) → let C = Setoid.Carrier A in  
                                                      Op₂ C → C → Set (α ⊔ α=)
isUnity A _∙_ e =  (x : Carrier) → ((e ∙ x) ≈ x) × ((x ∙ e) ≈ x)  where
                                                                 open Setoid A 

Unity : ∀ {α α=} (A : Setoid α α=) → Op₂ $ Setoid.Carrier A → Set (α ⊔ α=)
Unity A _∙_ =  ∃ (\ (e : Setoid.Carrier A) → isUnity A _∙_ e) 
             
RightQuotient : ∀ {α α=} (A : Setoid α α=) → 
                     let C = Setoid.Carrier A in  Op₂ C → C → C → Set (α ⊔ α=)

RightQuotient A _∙_ a b =  ∃ (\ q → (b ∙ q) ≈ a)  where _≈_ = Setoid._≈_ A


------------------------------------------------------------------------------
record CMonoid (α α= : Level) : Set (sucL (α ⊔ α=))
  where
  field  setoid : Setoid α α=
          
  open Setoid setoid using (_≈_) 
                     renaming (Carrier to C; isEquivalence to ≈equiv)

  open IsEquivalence ≈equiv using () renaming (refl to ≈refl; sym to ≈sym)  
  open module EqR≈ = EqR setoid renaming (_≈⟨_⟩_ to _≈[_]_)
  module FP≈ = FP _≈_ 

  field  _∙_    : Op₂ C
         ∙cong  : _∙_ Preserves₂ _≈_ ⟶ _≈_ ⟶ _≈_  
         ∙assoc : FP≈.Associative _∙_ 
         ∙comm  : FP≈.Commutative _∙_  
         unity  : Unity setoid _∙_

  -- some items and lemmata in-place ---------------------------------------

  ∙cong₁ : {y : C} → (\ x → x ∙ y) Preserves _≈_ ⟶ _≈_    
  ∙cong₁ x=x' =  ∙cong x=x' ≈refl

  ∙cong₂ : {x : C} → (_∙_ x) Preserves _≈_ ⟶ _≈_    
  ∙cong₂ =  ∙cong ≈refl

  _∣_ : Rel C (α ⊔ α=)                    -- `x divides y' 
  x ∣ y =  RightQuotient setoid _∙_ y x

  infix 2 _~asd_                          -- `associated'

  _~asd_ : Rel C (α ⊔ α=)
  a ~asd b =  a ∣ b  ×  b ∣ a

  ~asd→≈ :  Set _                         -- "_~asd_ is identical".
  ~asd→≈ =  ∀ {x y} → x ~asd y → x ≈ y   

  ∣cong : _∣_ Respects2 _≈_
  ∣cong {x} {x'} {y} {y'} x=x' y=y' (q , x∙q=y) =  (q , x'∙q=y')
                     where
                     x'∙q=y' :  x' ∙ q ≈ y'
                     x'∙q=y' =  begin  x' ∙ q   ≈[ ∙cong₁ $ ≈sym x=x' ]
                                       x  ∙ q   ≈[ x∙q=y ]
                                       y        ≈[ y=y' ]
                                       y'
                                ∎

  ∣cong₁ : {y : C} → (\x → x ∣ y) Respects _≈_
  ∣cong₁ x=x' =  ∣cong x=x' ≈refl

  ∣cong₂ : {x : C} → (_∣_ x) Respects _≈_
  ∣cong₂ = ∣cong ≈refl

  x∣x∙ : {x : C} → (y : C) →  x ∣ (x ∙ y)
  x∣x∙ y =  (y , ≈refl)

  ∣trans : Transitive _∣_
  ∣trans {x} {y} {z} (q , xq=y) (q' , yq'=z) =  (qq' , xqq'=z)
             where
             qq' = q ∙ q'

             xqq'=z : x ∙ qq' ≈ z
             xqq'=z = begin  x ∙ (q ∙ q')   ≈[ ≈sym $ ∙assoc x q q' ]
                             (x ∙ q) ∙ q'   ≈[ ∙cong₁ $ xq=y ]
                             y ∙ q'         ≈[ yq'=z ]
                             z
                      ∎
  ε : C  
  ε = proj₁ unity 

  ε∙ : (x : C) → (ε ∙ x) ≈ x
  ε∙ = proj₁ ∘ proj₂ unity 

  ∙ε : (x : C) → (x ∙ ε) ≈ x
  ∙ε = proj₂ ∘ proj₂ unity 

  open Setoid setoid public 





--****************************************************************************
module OfAssociated {α α=} (cMon : CMonoid α α=) 
  where
  open CMonoid cMon using (setoid; isEquivalence; _≈_; ε; _∣_; _~asd_; ∣cong;
                           ∣cong₂;∣trans; ∙ε 
                          ) 
                    renaming (Carrier to C) 

  open IsEquivalence isEquivalence using () 
                     renaming (refl to ≈refl; sym to ≈sym; trans to ≈trans)

  x∣x : (x : C) → x ∣ x
  x∣x x =  (ε , ∙ε x)

  ≈→∣ : {x y : C} → x ≈ y → x ∣ y
  ≈→∣ {x} {_} x≈y =  (ε , x∙ε≈y)  where
                                  x∙ε≈y = ≈trans (∙ε x) x≈y

 
  data Associated : Set α  where  asd : C → Associated

  fromAsd : Associated → C
  fromAsd (asd x) = x

  infixl 2 _=asd_

  _=asd_ :  Rel Associated (α ⊔ α=)
  _=asd_ =  _~asd_ on fromAsd

  ~asd-refl :  Reflexive _~asd_
  ~asd-refl {a} =  (x∣x a , x∣x a)

  ≈→~asd :  ∀ {x y} → x ≈ y → x ~asd y
  ≈→~asd {x} {y} x=y =  (x∣y , y∣x)
                                   where  x∣y = ∣cong₂ x=y $ x∣x x
                                          y∣x = ∣cong₂ (≈sym x=y) $ x∣x y
  =asdRefl : Reflexive _=asd_
  =asdRefl = ~asd-refl

  =asdSym : Symmetric _=asd_
  =asdSym (a∣b , b∣a) =  (b∣a , a∣b)

  =asdTrans : Transitive _=asd_
  =asdTrans (a∣b , b∣a) (b∣c , c∣b) =  (∣trans a∣b b∣c , ∣trans c∣b b∣a)

  asdIsEquiv : IsEquivalence _=asd_
  asdIsEquiv = record{ refl  = \{x}         → =asdRefl {x}
                     ; sym   = \{x} {y}     → =asdSym {x} {y}
                     ; trans = \{x} {y} {z} → =asdTrans {x} {y} {z} }
  
  asdSetoid : Setoid α (α ⊔ α=)
  asdSetoid = record{ Carrier       = Associated
                    ; _≈_           = _=asd_
                    ; isEquivalence = asdIsEquiv }

  open OfCongMap asdSetoid setoid using ()                              -- (1)
                                  renaming (IsInjective to IsInjective-from) 

  fromAsd-isInjective : IsInjective-from fromAsd
  fromAsd-isInjective = ≈→~asd                                          -- (2)



--****************************************************************************
module _ {α α=} (cMon : CMonoid α α=)
  where
  open CMonoid cMon using (setoid) 

  open OfAssociated {α} {α=} cMon using (asd; fromAsd; ≈→~asd; asdSetoid;
                                                          fromAsd-isInjective)
                                                                       -- (3)
  open OfCongMap {α} {α ⊔ α=} {α} {α=} asdSetoid setoid using (IsInjective)
                                                                       -- (4)
  fromAsd-isInj : IsInjective fromAsd                      
  fromAsd-isInj = fromAsd-isInjective                                  -- (5)
                  -- ≈→~asd


More information about the Agda mailing list