[Agda] induction recursion - normalisation

Ondrej Rypacek ondrej.rypacek at gmail.com
Tue May 3 11:14:23 CEST 2011


Hi,
I have a fairly simple inductive-recursive definition (see below).
The hole roughly in the middle, 4th case of the def. of src, has type

?0 : src fzero z ≡ tgt fzero (comp fzero x y xy)

where the right-hand side normalises to tgt fzero y by the definition
of tgt so the normalised environment is

Goal: src fzero z ≡ tgt fzero y
————————————————————————————————————————————————————————————
xy : src fzero y ≡ tgt fzero x
yz : src fzero z ≡ tgt fzero y
z  : Freeω (suc .n)
y  : Freeω (suc .n)
x  : Freeω (suc .n)
.n : ℕ
G  : GlobularSet

But yz fits only until I recompile. Then I'm getting

"y != (comp fzero x y xy) of type (Freeω (suc .n))
when checking that the expression yz has type
src fzero z ≡ tgt fzero (comp fzero x y xy)"

Strangely, the symmetrical case below, in the definition of tgt, i.e.

tgt fzero (alpha x y z yz xy) = comp fzero x (comp fzero y z yz) xy

works fine. Why? What's the difference ?
Any ideas what's wrong and how to fix it ?


Cheers,
Ondrej

-------

{-# OPTIONS --no-termination-check #-}

module globSetCat where

open import Data.Nat
open import Data.Fin hiding (#_;_<_) renaming (suc to fsuc;zero to fzero)
open import Data.Product
open import Data.Empty
open import Data.Unit hiding (tt ; _≤_ )
open import Relation.Binary.PropositionalEquality


-- a category structure on a set
record GlobularSet : Set₁ where
  field
    #_ : ℕ → Set
    src : ∀ {n} → # (suc n) → # n
    tgt : ∀ {n} → # (suc n) → # n

    ss-st : ∀ {n x} → src {suc (suc n)} (src x) ≡ src (tgt x)
    ts-tt : ∀ {n x} → tgt {suc (suc n)} (src x) ≡ tgt (tgt x)


module Freeω (G : GlobularSet) where
  open GlobularSet G renaming (src to |src|;tgt to |tgt|)

  mutual
    data Freeω : ℕ → Set where
      emb : ∀ {n} → # n → Freeω n
      comp : ∀ {n} → (m : Fin (suc n)) → (α β : Freeω (suc n)) → src m
β ≡ tgt m α → Freeω (suc n)
      id : ∀ {n} → Freeω n → Freeω (suc n)
      alpha : ∀ {n} → (x y z : Freeω (suc n)) → src fzero z ≡ tgt
fzero y → src fzero y ≡ tgt fzero x → Freeω (suc (suc n))

    src : ∀ {n} → (m : Fin (suc n)) → Freeω (suc n) → Freeω (n ℕ-ℕ m)
    src fzero (emb y) = emb (|src| y)
    src fzero (comp _ f g _) = src fzero f
    src fzero (id y) = y
    src fzero (alpha x y z yz xy) = comp fzero (comp fzero x y xy) z {!!}
    src {zero} (fsuc ()) x
    src {suc n} (fsuc i) x = src i (src fzero x)

    tgt : ∀ {n} → (m : Fin (suc n)) → Freeω (suc n) → Freeω (n ℕ-ℕ m)
    tgt fzero (emb y) = emb (|tgt| y)
    tgt fzero (comp _ f g _) = tgt fzero g
    tgt fzero (id y) = y
    tgt fzero (alpha x y z yz xy) = comp fzero x (comp fzero y z yz) xy
    tgt {zero} (fsuc ()) x
    tgt {suc n} (fsuc i) x = tgt i (tgt fzero x)


More information about the Agda mailing list