[Agda] struggling `with'

Sergei Meshveliani mechvel at botik.ru
Fri Jan 2 20:15:43 CET 2015


On Fri, 2015-01-02 at 16:51 +0100, Andrea Vezzosi wrote:
> It's really hard to see what's going on without being able to load the
> code, and with a lot of it omitted.
> 
> We need at least the definition of "ins" and the original type of
> "foo", then we might be able to figure out a better type for the two
> alternatives, so that the splitting on (k ≟ k') only needs to be done
> once.
> 

Here follows the full code. It occurs small.

I am grateful to anyone who shows how to write 
                                         ins-kv∘ins-ku-eq 
in a nicer way.

------
Sergei



--**********************************************************************
module AssocList where 
open import Level    using (Level) 
open import Function using (_$_; case_of_)
open import Relation.Nullary using (¬_; Dec; yes; no)
open import Relation.Unary   using (Decidable)
open import Relation.Binary  using 
     (Rel; _⇒_; Reflexive; Symmetric; Transitive; IsEquivalence;
      module IsEquivalence; Setoid; module Setoid; module DecSetoid; 
      DecSetoid 
     )
open import Relation.Binary.PropositionalEquality as PE using (_≡_)
import Relation.Binary.EqReasoning as EqR
open import Data.Empty   using (⊥; ⊥-elim)
open import Data.Product using (_×_;  _,_)
open import Relation.Binary.Product.Pointwise using (_×-setoid_)
open import Data.List using (List; []; _∷_)
open import Relation.Binary.List.Pointwise as Pointwise using ()
                                   renaming ([] to []pn; _∷_ to _∷pn_)

-----------------------------------------------------------------------
module _ {α α= β β= : Level} (keyDSetoid : DecSetoid α α=)
                             (valSetoid  : Setoid β β=)
  where
  open DecSetoid keyDSetoid using (_≈_; _≟_; setoid) renaming 
                                (Carrier to K; isEquivalence to kEquiv)
  open IsEquivalence kEquiv using () 
                renaming (refl to ≈refl; sym to ≈sym; trans to ≈trans)

  open Setoid valSetoid using () renaming (Carrier to V; _≈_ to _=v_;
                                               isEquivalence to vEquiv)
  open IsEquivalence vEquiv using () 
           renaming (refl to =v-refl; sym to =v-sym; trans to =v-trans;
                                             reflexive to =v-reflexive)

  pairSetoid = setoid ×-setoid valSetoid                  -- for  K × V
  open Setoid pairSetoid using () renaming (Carrier to KV; _≈_ to _=p_;
                                              isEquivalence to pEquiv) 
  open IsEquivalence pEquiv using () 
          renaming (refl to =p-refl; sym to =p-sym; trans to =p-trans; 
                                             reflexive to =p-reflexive)

  point-p-setoid = Pointwise.setoid pairSetoid  
  open Setoid point-p-setoid using () 
                      renaming (_≈_ to _=pn_; isEquivalence to pnEquiv)
  -- "pn" stands for "pointwise for List KV"

  open IsEquivalence pnEquiv using () 
               renaming (refl to =pn-refl; reflexive to =pn-reflexive; 
                                                 sym to =pn-sym)   
  open module EqR-pn = EqR point-p-setoid
      renaming (begin_ to begin-pn_; _∎ to _end-pn; _≈⟨_⟩_ to _=pn[_]_)


  -------------------------------------------------------------------
  Pairs : Set _
  Pairs = List KV

  CombineKVV : Set _  -- (α ⊔ β)
  CombineKVV = K → V → V → V

  ----------------------------------------------------------------------
  insertWithKey : CombineKVV →  KV → Pairs → Pairs
               -- \key newV oldV |→ resV

  insertWithKey _    p         []                =  p ∷ []
  insertWithKey comb (k , new) ((k' , old) ∷ ps) =
        case k ≟ k'
        of \
        { (yes _) → (k' , comb k new old) ∷ ps
        ; (no _)  → (k' , old) ∷ (insertWithKey comb (k , new) ps) }

  ----------------------------------------------------------------------
  ins-kv∘ins-ku-eq :
             (comb : CombineKVV) → ∀ k u v ps →
             (∀ {w} → comb k v (comb k u w) =v comb k (comb k v u) w) →
             let ins = insertWithKey comb 
             in
             ins (k , v) (ins (k , u) ps)  =pn  ins (k , comb k v u) ps

  -- Example:  it fits  comb _ u v = f u v   with any Associative f.

  ins-kv∘ins-ku-eq _    k _ _ []   _  with k ≟ k
  ...                                     | yes _  =  =pn-refl
  ...                                     | no k≉k =  ⊥-elim $ k≉k ≈refl

  ins-kv∘ins-ku-eq comb k u v ((k' , w) ∷ ps) sym-assoc-comb =  
                                                        prove (k ≟ k')
    where
    ins  = insertWithKey comb 
    kv   = (k , v)
    ku   = (k , u)
    k'w  = (k' , w) 
    ckuw = comb k u w
    ckvu = comb k v u

    -------------------------------------------------------------------
    case≈ : k ≈ k' →
            ins kv (ins ku (k'w ∷ ps)) =pn ins (k , ckvu) (k'w ∷ ps)

    case≈ k≈k' =  
      begin-pn
        ins kv (ins ku (k'w ∷ ps))   =pn[ =pn-reflexive $ 
                                          PE.cong (ins kv) e1
                                        ]
        ins kv ((k' , ckuw) ∷ ps)    =pn[ =pn-reflexive e2 ]
        (k' , comb k v ckuw) ∷ ps    =pn[ e0 ∷pn =pn-refl ]
        (k' , comb k ckvu w) ∷ ps    =pn[ =pn-reflexive $ PE.sym e3 ]
        ins (k , ckvu) (k'w ∷ ps)
      end-pn
      where
      e0 : (k' , comb k v ckuw) =p (k' , comb k ckvu w)
      e0 = (≈refl , sym-assoc-comb)

      e1 :  ins ku ((k' , w) ∷ ps) ≡ (k' , ckuw) ∷ ps   
      e1 with k ≟ k' 
      ... | yes _   = PE.refl
      ... | no k≉k' = ⊥-elim $ k≉k' k≈k'

      e2 :  ins kv ((k' , ckuw) ∷ ps) ≡ (k' , comb k v ckuw) ∷ ps 
      e2 with k ≟ k' 
      ... | yes _   = PE.refl
      ... | no k≉k' = ⊥-elim $ k≉k' k≈k'

      e3 :  ins (k , ckvu) (k'w ∷ ps) ≡ (k' , comb k ckvu w) ∷ ps    
      e3 with k ≟ k' 
      ... | yes _   = PE.refl
      ... | no k≉k' = ⊥-elim $ k≉k' k≈k'

    -------------------------------------------------------------------
    case≉ : ¬ k ≈ k' → 
            ins kv (ins ku (k'w ∷ ps))  =pn  ins (k , ckvu) (k'w ∷ ps)
  
    case≉ k≉k' = 
      begin-pn  
        ins kv (ins ku (k'w ∷ ps))      =pn[ =pn-reflexive $
                                              PE.cong (ins kv) e1 ]
         ins kv (k'w ∷ (ins ku ps))     =pn[ =pn-reflexive e2 ]
         k'w ∷ (ins kv $ ins ku ps)     =pn[ =p-refl ∷pn e0 ]
         k'w ∷ (ins (k , ckvu) ps)      =pn[ =pn-reflexive e3 ]
         ins (k , ckvu) (k'w ∷ ps)
      end-pn
      where
      e0 : (ins kv (ins ku ps)) =pn (ins (k , ckvu) ps)
      e0 = ins-kv∘ins-ku-eq comb k u v ps sym-assoc-comb

      e1 : ins ku (k'w ∷ ps) ≡ k'w ∷ (ins ku ps)
      e1 with k ≟ k'
      ... | no _     = PE.refl 
      ... | yes k≈k' = ⊥-elim $ k≉k' k≈k'

      e2 : ins kv (k'w ∷ ins ku ps) ≡ k'w ∷ (ins kv $ ins ku ps)
      e2 with k ≟ k'
      ... | no _     = PE.refl
      ... | yes k≈k' = ⊥-elim $ k≉k' k≈k'

      e3 :  k'w ∷ (ins (k , ckvu) ps) ≡ ins (k , ckvu) (k'w ∷ ps)
      e3 with k ≟ k'
      ... | no _     = PE.refl
      ... | yes k≈k' = ⊥-elim $ k≉k' k≈k'

    -----------------------------------------------------------------
    prove : Dec (k ≈ k') → ins kv (ins ku (k'w ∷ ps)) =pn 
                           ins (k , comb k v u) (k'w ∷ ps)
    prove (no k≉k')  = case≉ k≉k'
    prove (yes k≈k') = case≈ k≈k'

-------------------------------------------------------------------------------






More information about the Agda mailing list