[Agda] hidden proofs

Sergei Meshveliani mechvel at botik.ru
Tue Jul 30 20:57:34 CEST 2013


On Wed, 2013-07-31 at 03:46 +1000, Liam O'Connor wrote:
> Hi Sergei,
> 
> 
> I was pretty easily able to define "even" using a similar definition
> to your first one:
> 
> 
> open import Data.Nat
> 
> 
> mutual
>  data Even : ℕ → Set
>   where
>    even0 : Even 0
>    even-suc : {n : ℕ} → Even n → Even (suc (suc n)) 
> 
> 
> open import Relation.Nullary
> 
> 
> even : (n : ℕ) -> Dec (Even n)
> even zero = yes even0
> even (suc zero) = no (λ ()) -- absurd pattern :)
> even (suc (suc n)) with even n
> ... | yes p = yes (even-suc p)
> ... | no p = no (λ { (even-suc x) → p x })
> 

Great! Thank you. A good point for me.

Initially I also had this precise definition of Even.
But I was stupid enough and has not guessed that  even (suc 0)
is an absurd pattern here.

There remains a (beginner) question here:
how does the programmer know which pattern the type checker will agree
to qualify as absurd?
This is a matter of the Language definition.

If the checker was only for this example with Even, then all right,
there is a clear special algorithm.
But suppose that one defines

  data Foo : ℕ → Set where
                     foo1 : Bool -> (n : ℕ) → Foo n
                     foo2 : <something complex>
                     ...
                     foo9 : ... -> Foo (f n)

  foo? : ℕ → Dec $ Foo n
  foo? 100 = no (λ ())
  ...

How does the checker decide on whether  foo? 100 
is an absurd pattern or not?

Thanks,

------
Sergei



More information about the Agda mailing list