[Agda] non-constructor indices

Dan Licata drl at cs.cmu.edu
Tue Jan 15 18:50:11 CET 2008


Hi Agda hackers,

I have a question about inductive families that use non-constructor
indices.  For example:

   data Nat : Set where
     Z : Nat
     S : Nat -> Nat
   
   plus : Nat -> Nat -> Nat
   plus Z n = n
   plus (S m) n = S (plus m n)
   
   data Indexed : Nat -> Set where
     B : Indexed Z
     I : {n m : Nat} -> Indexed n -> Indexed m -> Indexed (plus n m)

Say I want to defined a recursive function over Indexed Z, a
specialization of the index, such as: 

  height : Indexed Z -> Nat

If I try to do this directly, I run into trouble:

  {- Version 1:
  height : Indexed Z -> Nat
  height B = Z 

  /afs/cs.cmu.edu/user/drl/rsh/progind/code/agda/Bug.agda:17,1-13
  Panic: failed to split: CantSplit Bug.I
  when checking the definition of height
  -}

  {-
  -- Version 2: use identity

  data Id : Nat -> Nat -> Set where
    Refl : {n : Nat} -> Id n n
  
  subst : {n m : Nat} (P : Nat -> Set) -> Id n m -> P n -> P m
  subst P Refl x = x
  
  invert-plus-z-2 : {n m : Nat} -> Id (plus n m) Z -> Id m Z 
  invert-plus-z-2 {Z} id = id
  invert-plus-z-2 {S _} ()

  height : {n : Nat} -> Id n Z -> Indexed n -> Nat
  -- can't write (same Panic as above): 
  --  height {Z} Refl B = Z
  --  height {Z} id   B = Z
  -- same thing happens if you make the 1st arg explicit

  -- this version type-checks but has unsolved metas:
  height id B = Z
  height id (I i1 i2) = height {_} (invert-plus-z-2 id) i2
  -}

The only way I've been able to successfully write the code is by using
identity in the datatype itself:

  data Indexed : Nat -> Set where
    B : Indexed Z
    I : {n m k : Nat} -> Indexed n -> Indexed m -> Id (plus n m) k -> Indexed k

And, to avoid termination problems, I have to use identity in the
theorem as well:
  
  {-
  -- termination problems:
  height : Indexed Z -> Nat 
  height B = Z
  height (I {n} {m} p1 p2 id) = height (subst Indexed (invert-plus-z-2 {n} {m} id) p2)
  -}

  -- OK!
  height2 : {n : Nat} -> Indexed n -> Id n Z -> Nat 
  height2 B Refl = Z
  height2 (I {n} {m} p1 p2 id) Refl = height2 p2 (invert-plus-z-2 {n} {m} id)

My question: does anyone know of any better solutions than what I've
come up with here?

Thanks!
-Dan


More information about the Agda mailing list