[Agda] basic question about induction/recursion & pattern-matching

Noam Zeilberger noam+agda at cs.cmu.edu
Tue Sep 9 18:30:50 CEST 2008


let's say we begin by defining two datatypes that mirror each other,
and a coercion between them:

 open import Logic.Identity 
 open import Data.Maybe

 module Test where

  data bool : Set where
    tt : bool
    ff : bool
  
  data BOOL : Set where
    TT : BOOL
    FF : BOOL
  
  b2B : bool -> BOOL
  b2B tt = TT
  b2B ff = FF

Now, we're interested in a datatype indexed by BOOL that has
a constructor taking a bool, like so:

  data foo : BOOL -> Set where
    FOO : (b : bool) -> foo (b2B b)

but let's also define a simpler datatype, just indexed by bool:

  data bar : bool -> Set where
    BAR : (b : bool) -> bar b

The question is, can we write an equality function on foos?

  fooeq : {B : BOOL} -> (x1 x2 : foo B) -> Maybe (x1 ≡ x2)

We can certainly write one on bars:

  bareq : {b : bool} -> (x1 x2 : bar b) -> Maybe (x1 ≡ x2)
  bareq (BAR b) (BAR .b) = just refl

But if we try to give the analogous definition of fooeq:

  fooeq (FOO b) (FOO .b) = just refl

Agda gives an error, "b' != b of type bool when checking that the
pattern FOO .b has type foo (b2B b)".  Indeed, if we do any
pattern-matching at all on the two arguments

  fooeq (FOO b1) (FOO b2) = {! !}

it gives the same error, "b2 != b1 of type bool when checking that the
pattern FOO b2 has type foo (b2B b1)".

So is there any way to write fooeq?

Noam


More information about the Agda mailing list