Understanding practice exam about Agda

2
votes

I am going through my practice exam for Programming language Foundations using agda and it has the following question:

You are given the following Agda declaration:

data Even : N → Set where
 ezero : Even 0
 esuc : { n : N }  → Even n  → Even (2+ n)

Assume that the standard library of natural numbers has been imported. Answer the following questions:

a)What is the type of ezero?

b)Are there any terms of type Even 1?

c)How many terms are of type Even 2? List them

d)Describe one potential problem that might occur if we change the return type of esuc to be Even (n+2) instead of Even (2+n).

We're not provided a solution manual. The question seems pretty basic but I am not sure about any of these.I think the answer to the first three are:

a) Set

b) No terms of type Even 1

c) One term of type Even 2

d) don't know

Answers to these questions along with a brief explanation would be highly appreciated. Thanks

1
programming-languagesagdaagda-mode

1 Answers

5
votes

What is the type of ezero?

The type of the data constructor ezero can be read from the data declaration: ezero : Even 0 states that it has type Even 0.

Are there any terms of type Even 1?

No there aren't any. This can be seen by a case distinction: if there were a term then it'd start with either one of the two constructors. And because these have specific return indices, they'd have to unify with 1.

  • ezero would enforce 1 = 0
  • esuc would mean that there is an n such that 1 = 2+ n

Both of these situations are impossible.

How many terms are of type Even 2? List them

There is exactly one: esuc ezero. With a reasoning similar to the one in the previous question, we can prove that ezero and esuc (esuc p) (for some p) won't do.

Describe one potential problem that might occur if we change the return type of esuc to be Even (n+2) instead of Even (2+n).

Consider the proof plus-Even : {m n : N} → Even m → Even n → Even (m + n). Because (+) is defined by induction on its first argument, you won't be able to immediately apply esuc in the step case. You are going to need to use rewriting to reorganize the type of the goal from Even ((m +2) + n) (or Even (m + (n +2)) depending on which argument you perform induction on) to Even ((m + n) +2) beforehand.