- Transition to Processing
- Primitive Operations
- Algorithms
- Variables
- Debugging in Processing
- Conditions
- Loops
- Functions
- Scope
- Compound Data
- Reference Semantics
- Refactoring
- Program Design
- Transition to Java
- Debugging in Java
- Unit Testing
- Classes - Writing your own Types
- Classes - Copying objects
- Classes - Functions inside objects
- Classes - Composition
- Classes - Array of objects
- Classes - Class holding array(s)
- Recursion - What goes on during a function call
- Recursion
- Recursion with String data
- Tail-optimized recursion
- Recursion with arrays
- Lists
- Iteration
- List of Lists
- Custom-built ArrayList
- Recursive data structures - 1
- Recursive data structures - 2
- Searching

- Logic and Proofs
- Relations
- Mathematical Functions
- Matrices
- Binary Numbers
- Trigonomtry
- Finite State Machines
- Turing Machines
- Counting - Inclusion/Exclusion
- Graph Algorithms

- Algorithm Efficiency
- Algorithm Correctness
- Trees
- Heaps, Stack, and Queues
- Maps and Hashtables
- Graphs and Graph Algorithms
- Advanced Trees and Computability

- Command line control
- Transition to C
- Pointers
- Memory Allocation
- IO
- Number representations
- Assembly Programming
- Structs and Unions
- How memory works
- Virtual Memory

- Version Control with Git
- Inheritance and Overloading
- Generics
- Exceptions
- Lambda Expressions
- Design Patterns
- Concepts of Concurrency
- Concurrency: Object Locks
- Modern Concurrency

- System Models
- Naming and Distributed File Systems
- Synchronisation and Concurrency
- Fault Tolerance and Security
- Clusters and Grids
- Virtualisation
- Data Centers
- Mobile Computing

- Transition to Scala
- Functional Programming
- Syntax Analysis
- Name Analysis
- Type Analysis
- Transformation and Compilation
- Control Abstraction
- Implementing Data Abstraction
- Language Runtimes

- Transition to Coq
- Proof by Induction, Structured Data
- Polymorphism and Higher-Order Functions
- More Basic Tactics
- Logical Reasoning in Proof Assistants
- Inductive Propositions
- Maps
- An Imperative Programming Language
- Program Equivalence
- Hoare Logic
- Small-Step Operational Semantics
- Simply-typed Lambda Calculus

Grab the Coq source file Poly.v

... but this would quickly become tedious, partly because we
have to make up different constructor names for each datatype, but
mostly because we would also need to define new versions of all
our list manipulating functions (length, rev, etc.) for each
new datatype definition.
To avoid all this repetition, Coq supports *polymorphic*
inductive type definitions. For example, here is a *polymorphic
list* datatype.

This is exactly like the definition of natlist from the
previous chapter, except that the nat argument to the cons
constructor has been replaced by an arbitrary type X, a binding
for X has been added to the header, and the occurrences of
natlist in the types of the constructors have been replaced by
list X. (We can re-use the constructor names nil and cons
because the earlier definition of natlist was inside of a
Module definition that is now out of scope.)
What sort of thing is list itself? One good way to think
about it is that list is a *function* from Types to
Inductive definitions; or, to put it another way, list is a
function from Types to Types. For any particular type X,
the type list X is an Inductively defined set of lists whose
elements are things of type X.
With this definition, when we use the constructors nil and
cons to build lists, we need to tell Coq the type of the
elements in the lists we are building — that is, nil and cons
are now *polymorphic constructors*. Observe the types of these
constructors:

Check nil.

(* ===> nil : forall X : Type, list X *)

Check cons.

(* ===> cons : forall X : Type, X -> list X -> list X *)

(Side note on notation: In .v files, the "forall" quantifier is
spelled out in letters. In the generated HTML files, ∀ is
usually typeset as the usual mathematical "upside down A," but
you'll see the spelled-out "forall" in a few places, as in the
above comments. This is just a quirk of typesetting: there is no
difference in meaning.)
The "∀ X" in these types can be read as an additional
argument to the constructors that determines the expected types of
the arguments that follow. When nil and cons are used, these
arguments are supplied in the same way as the others. For
example, the list containing 2 and 1 is written like this:

(We've written nil and cons explicitly here because we haven't
yet defined the [] and :: notations for the new version of
lists. We'll do that in a bit.)
We can now go back and make polymorphic versions of all the
list-processing functions that we wrote before. Here is repeat,
for example:

Fixpoint repeat (X : Type) (x : X) (count : nat) : list X :=

match count with

| 0 ⇒ nil X

| S count' ⇒ cons X x (repeat X x count')

end.

As with nil and cons, we can use repeat by applying it
first to a type and then to its list argument:

To use repeat to build other kinds of lists, we simply
instantiate it with an appropriate type parameter:

Example test_repeat2 :

repeat bool false 1 = cons bool false (nil bool).

Proof. reflexivity. Qed.

Module MumbleGrumble.

Inductive mumble : Type :=

| a : mumble

| b : mumble → nat → mumble

| c : mumble.

Inductive grumble (X:Type) : Type :=

| d : mumble → grumble X

| e : X → grumble X.

Which of the following are well-typed elements of grumble X for
some type X?

☐

- d (b a 5)
- d mumble (b a 5)
- d bool (b a 5)
- e bool true
- e mumble (b c 0)
- e bool (b c 0)
- c

☐

Fixpoint repeat' X x count : list X :=

match count with

| 0 ⇒ nil X

| S count' ⇒ cons X x (repeat' X x count')

end.

Indeed it will. Let's see what type Coq has assigned to repeat':

Check repeat'.

(* ===> forall X : Type, X -> nat -> list X *)

Check repeat.

(* ===> forall X : Type, X -> nat -> list X *)

It has exactly the same type type as repeat. Coq was able
to use *type inference* to deduce what the types of X, x, and
count must be, based on how they are used. For example, since
X is used as an argument to cons, it must be a Type, since
cons expects a Type as its first argument; matching count
with 0 and S means it must be a nat; and so on.
This powerful facility means we don't always have to write
explicit type annotations everywhere, although explicit type
annotations are still quite useful as documentation and sanity
checks, so we will continue to use them most of the time. You
should try to find a balance in your own code between too many
type annotations (which can clutter and distract) and too
few (which forces readers to perform type inference in their heads
in order to understand your code).

repeat' X x count : list X :=

we can also replace the types with _
repeat' (X : _) (x : _) (count : _) : list X :=

to tell Coq to attempt to infer the missing information.
Fixpoint repeat'' X x count : list X :=

match count with

| 0 ⇒ nil _

| S count' ⇒ cons _ x (repeat'' _ x count')

end.

In this instance, we don't save much by writing _ instead of
X. But in many cases the difference in both keystrokes and
readability is nontrivial. For example, suppose we want to write
down a list containing the numbers 1, 2, and 3. Instead of
writing this...

...we can use argument synthesis to write this:

Now, we don't have to supply type arguments at all:

Alternatively, we can declare an argument to be implicit
when defining the function itself, by surrounding it in curly
braces. For example:

Fixpoint repeat''' {X : Type} (x : X) (count : nat) : list X :=

match count with

| 0 ⇒ nil

| S count' ⇒ cons x (repeat''' x count')

end.

(Note that we didn't even have to provide a type argument to the
recursive call to repeat'''; indeed, it would be invalid to
provide one!)
We will use the latter style whenever possible, but we will
continue to use use explicit Argument declarations for
Inductive constructors. The reason for this is that marking the
parameter of an inductive type as implicit causes it to become
implicit for the type itself, not just for its constructors. For
instance, consider the following alternative definition of the
list type:

Because X is declared as implicit for the *entire* inductive
definition including list' itself, we now have to write just
list' whether we are talking about lists of numbers or booleans
or anything else, rather than list' nat or list' bool or
whatever; this is a step too far.
Let's finish by re-implementing a few other standard list
functions on our new polymorphic lists...

Fixpoint app {X : Type} (l

: (list X) :=

match l

| nil ⇒ l

| cons h t ⇒ cons h (app t l

end.

Fixpoint rev {X:Type} (l:list X) : list X :=

match l with

| nil ⇒ nil

| cons h t ⇒ app (rev t) (cons h nil)

end.

Fixpoint length {X : Type} (l : list X) : nat :=

match l with

| nil ⇒ 0

| cons _ l' ⇒ S (length l')

end.

Example test_rev1 :

rev (cons 1 (cons 2 nil)) = (cons 2 (cons 1 nil)).

Proof. reflexivity. Qed.

Example test_rev2:

rev (cons true nil) = cons true nil.

Proof. reflexivity. Qed.

Example test_length1: length (cons 1 (cons 2 (cons 3 nil))) = 3.

Proof. reflexivity. Qed.

One small problem with declaring arguments Implicit is
that, occasionally, Coq does not have enough local information to
determine a type argument; in such cases, we need to tell Coq that
we want to give the argument explicitly just this time. For
example, suppose we write this:

(The Fail qualifier that appears before Definition can be
used with *any* command, and is used to ensure that that command
indeed fails when executed. If the command does fail, Coq prints
the corresponding error message, but continues processing the rest
of the file.)
Here, Coq gives us an error because it doesn't know what type
argument to supply to nil. We can help it by providing an
explicit type declaration (so that Coq has more information
available when it gets to the "application" of nil):

Alternatively, we can force the implicit arguments to be explicit by
prefixing the function name with @.

Using argument synthesis and implicit arguments, we can
define convenient notation for lists, as before. Since we have
made the constructor type arguments implicit, Coq will know to
automatically infer these when we use the notations.

Notation "x :: y" := (cons x y)

(at level 60, right associativity).

Notation "[ ]" := nil.

Notation "[ x ; .. ; y ]" := (cons x .. (cons y []) ..).

Notation "x ++ y" := (app x y)

(at level 60, right associativity).

Now lists can be written just the way we'd hope:

Theorem app_nil_r : ∀(X:Type), ∀l:list X,

l ++ [] = l.

Proof.

(* FILL IN HERE *) Admitted.

Theorem app_assoc : ∀A (l m n:list A),

l ++ m ++ n = (l ++ m) ++ n.

Proof.

(* FILL IN HERE *) Admitted.

Lemma app_length : ∀(X:Type) (l

length (l

Proof.

(* FILL IN HERE *) Admitted.

Theorem rev_app_distr: ∀X (l

rev (l

Proof.

(* FILL IN HERE *) Admitted.

Theorem rev_involutive : ∀X : Type, ∀l : list X,

rev (rev l) = l.

Proof.

(* FILL IN HERE *) Admitted.

☐

As with lists, we make the type arguments implicit and define the
familiar concrete notation.

We can also use the Notation mechanism to define the standard
notation for product *types*:

(The annotation : type_scope tells Coq that this abbreviation
should only be used when parsing types. This avoids a clash with
the multiplication symbol.)
It is easy at first to get (x,y) and X*Y confused.
Remember that (x,y) is a *value* built from two other values,
while X*Y is a *type* built from two other types. If x has
type X and y has type Y, then (x,y) has type X*Y.
The first and second projection functions now look pretty
much as they would in any functional programming language.

Definition fst {X Y : Type} (p : X * Y) : X :=

match p with

| (x, y) ⇒ x

end.

Definition snd {X Y : Type} (p : X * Y) : Y :=

match p with

| (x, y) ⇒ y

end.

The following function takes two lists and combines them
into a list of pairs. In other functional languages, it is often
called zip; we call it combine for consistency with Coq's
standard library.

Fixpoint combine {X Y : Type} (lx : list X) (ly : list Y)

: list (X*Y) :=

match lx, ly with

| [], _ ⇒ []

| _, [] ⇒ []

| x :: tx, y :: ty ⇒ (x, y) :: (combine tx ty)

end.

- What is the type of combine (i.e., what does Check @combine print?)
- What does
Compute (combine [1;2] [false;false;true;true]).print? ☐

Fixpoint split {X Y : Type} (l : list (X*Y))

: (list X) * (list Y)

(* REPLACE THIS LINE WITH := _your_definition_ . *) . Admitted.

Example test_split:

split [(1,false);(2,false)] = ([1;2],[false;false]).

Proof.

(* FILL IN HERE *) Admitted.

☐

Inductive option (X:Type) : Type :=

| Some : X → option X

| None : option X.

Arguments Some {X} _.

Arguments None {X}.

We can now rewrite the nth_error function so that it works
with any type of lists.

Fixpoint nth_error {X : Type} (l : list X) (n : nat)

: option X :=

match l with

| [] ⇒ None

| a :: l' ⇒ if beq_nat n O then Some a else nth_error l' (pred n)

end.

Example test_nth_error1 : nth_error [4;5;6;7] 0 = Some 4.

Proof. reflexivity. Qed.

Example test_nth_error2 : nth_error [[1];[2]] 1 = Some [2].
Proof. reflexivity. Qed.

Example test_nth_error3 : nth_error [true] 2 = None.
Proof. reflexivity. Qed.

Definition hd_error {X : Type} (l : list X) : option X

(* REPLACE THIS LINE WITH := _your_definition_ . *) . Admitted.

Once again, to force the implicit arguments to be explicit,
we can use @ before the name of the function.

Check @hd_error.

Example test_hd_error1 : hd_error [1;2] = Some 1.

(* FILL IN HERE *) Admitted.

Example test_hd_error2 : hd_error [[1];[2]] = Some [1].

(* FILL IN HERE *) Admitted.

☐

The argument f here is itself a function (from X to
X); the body of doit3times applies f three times to some
value n.

Check @doit3times.

(* ===> doit3times : forall X : Type, (X -> X) -> X -> X *)

Example test_doit3times: doit3times minustwo 9 = 3.

Proof. reflexivity. Qed.

Example test_doit3times': doit3times negb true = false.

Proof. reflexivity. Qed.

Fixpoint filter {X:Type} (test: X→bool) (l:list X)

: (list X) :=

match l with

| [] ⇒ []

| h :: t ⇒ if test h then h :: (filter test t)

else filter test t

end.

For example, if we apply filter to the predicate evenb
and a list of numbers l, it returns a list containing just the
even members of l.

Example test_filter1: filter evenb [1;2;3;4] = [2;4].

Proof. reflexivity. Qed.

Definition length_is_1 {X : Type} (l : list X) : bool :=

beq_nat (length l) 1.

Example test_filter2:

filter length_is_1

[ [1; 2]; [3]; [4]; [5;6;7]; []; [8] ]

= [ [3]; [4]; [8] ].

Proof. reflexivity. Qed.

Definition countoddmembers' (l:list nat) : nat :=

length (filter oddb l).

Example test_countoddmembers'1: countoddmembers' [1;0;3;1;4;5] = 4.

Proof. reflexivity. Qed.

Example test_countoddmembers'2: countoddmembers' [0;2;4] = 0.

Proof. reflexivity. Qed.

Example test_countoddmembers'3: countoddmembers' nil = 0.

Proof. reflexivity. Qed.

The expression (fun n ⇒ n * n) can be read as "the function
that, given a number n, yields n * n."
Here is the filter example, rewritten to use an anonymous
function.

Example test_filter2':

filter (fun l ⇒ beq_nat (length l) 1)

[ [1; 2]; [3]; [4]; [5;6;7]; []; [8] ]

= [ [3]; [4]; [8] ].

Proof. reflexivity. Qed.

Definition filter_even_gt

(* REPLACE THIS LINE WITH := _your_definition_ . *) . Admitted.

Example test_filter_even_gt7_1 :

filter_even_gt

(* FILL IN HERE *) Admitted.

Example test_filter_even_gt7_2 :

filter_even_gt

(* FILL IN HERE *) Admitted.

☐
#### Exercise: 3 stars (partition)

Use filter to write a Coq function partition:

partition : ∀X : Type,

(X → bool) → list X → list X * list X

Given a set X, a test function of type X → bool and a list
X, partition should return a pair of lists. The first member of
the pair is the sublist of the original list containing the
elements that satisfy the test, and the second is the sublist
containing those that fail the test. The order of elements in the
two sublists should be the same as their order in the original
list.
(X → bool) → list X → list X * list X

Definition partition {X : Type}

(test : X → bool)

(l : list X)

: list X * list X

(* REPLACE THIS LINE WITH := _your_definition_ . *) . Admitted.

Example test_partition1: partition oddb [1;2;3;4;5] = ([1;3;5], [2;4]).

(* FILL IN HERE *) Admitted.

Example test_partition2: partition (fun x ⇒ false) [5;9;0] = ([], [5;9;0]).

(* FILL IN HERE *) Admitted.

☐

Fixpoint map {X Y:Type} (f:X→Y) (l:list X) : (list Y) :=

match l with

| [] ⇒ []

| h :: t ⇒ (f h) :: (map f t)

end.

It takes a function f and a list l = [n_{1}, n_{2}, n_{3}, ...]
and returns the list [f n_{1}, f n_{2}, f n_{3},...] , where f has
been applied to each element of l in turn. For example:

The element types of the input and output lists need not be
the same, since map takes *two* type arguments, X and Y; it
can thus be applied to a list of numbers and a function from
numbers to booleans to yield a list of booleans:

It can even be applied to a list of numbers and
a function from numbers to *lists* of booleans to
yield a *list of lists* of booleans:

Example test_map3:

map (fun n ⇒ [evenb n;oddb n]) [2;1;2;5]

= [[true;false];[false;true];[true;false];[false;true]].

Proof. reflexivity. Qed.

Theorem map_rev : ∀(X Y : Type) (f : X → Y) (l : list X),

map f (rev l) = rev (map f l).

Proof.

(* FILL IN HERE *) Admitted.

☐
#### Exercise: 2 stars, recommended (flat_map)

The function map maps a list X to a list Y using a function
of type X → Y. We can define a similar function, flat_map,
which maps a list X to a list Y using a function f of type
X → list Y. Your definition should work by 'flattening' the
results of f, like so:

flat_map (fun n ⇒ [n;n+1;n+2]) [1;5;10]

= [1; 2; 3; 5; 6; 7; 10; 11; 12].

= [1; 2; 3; 5; 6; 7; 10; 11; 12].

Fixpoint flat_map {X Y:Type} (f:X → list Y) (l:list X)

: (list Y)

(* REPLACE THIS LINE WITH := _your_definition_ . *) . Admitted.

Example test_flat_map1:

flat_map (fun n ⇒ [n;n;n]) [1;5;4]

= [1; 1; 1; 5; 5; 5; 4; 4; 4].

(* FILL IN HERE *) Admitted.

☐
Lists are not the only inductive type that we can write a
map function for. Here is the definition of map for the
option type:

Definition option_map {X Y : Type} (f : X → Y) (xo : option X)

: option Y :=

match xo with

| None ⇒ None

| Some x ⇒ Some (f x)

end.

Fixpoint fold {X Y:Type} (f: X→Y→Y) (l:list X) (b:Y)

: Y :=

match l with

| nil ⇒ b

| h :: t ⇒ f h (fold f t b)

end.

Intuitively, the behavior of the fold operation is to
insert a given binary operator f between every pair of elements
in a given list. For example, fold plus [1;2;3;4] intuitively
means 1+2+3+4. To make this precise, we also need a "starting
element" that serves as the initial second input to f. So, for
example,

fold plus [1;2;3;4] 0

yields
1 + (2 + (3 + (4 + 0))).

Some more examples:
Check (fold andb).

(* ===> fold andb : list bool -> bool -> bool *)

Example fold_example1 :

fold mult [1;2;3;4] 1 = 24.

Proof. reflexivity. Qed.

Example fold_example2 :

fold andb [true;true;false;true] true = false.

Proof. reflexivity. Qed.

Example fold_example3 :

fold app [[1];[];[2;3];[4]] [] = [1;2;3;4].

Proof. reflexivity. Qed.

Definition constfun {X: Type} (x: X) : nat→X :=

fun (k:nat) ⇒ x.

Definition ftrue := constfun true.

Example constfun_example1 : ftrue 0 = true.

Proof. reflexivity. Qed.

Example constfun_example2 : (constfun 5) 99 = 5.

Proof. reflexivity. Qed.

In fact, the multiple-argument functions we have already
seen are also examples of passing functions as data. To see why,
recall the type of plus.

Each → in this expression is actually a *binary* operator
on types. This operator is *right-associative*, so the type of
plus is really a shorthand for nat → (nat → nat) — i.e., it
can be read as saying that "plus is a one-argument function that
takes a nat and returns a one-argument function that takes
another nat and returns a nat." In the examples above, we
have always applied plus to both of its arguments at once, but
if we like we can supply just the first. This is called *partial
application*.

Definition plus3 := plus 3.

Check plus3.

Example test_plus3 : plus3 4 = 7.

Proof. reflexivity. Qed.

Example test_plus3' : doit3times plus3 0 = 9.

Proof. reflexivity. Qed.

Example test_plus3'' : doit3times (plus 3) 0 = 9.

Proof. reflexivity. Qed.

Definition fold_length {X : Type} (l : list X) : nat :=

fold (fun _ n ⇒ S n) l 0.

Example test_fold_length1 : fold_length [4;7;0] = 3.

Proof. reflexivity. Qed.

Prove the correctness of fold_length.

Theorem fold_length_correct : ∀X (l : list X),

fold_length l = length l.

(* FILL IN HERE *) Admitted.

Definition fold_map {X Y:Type} (f : X → Y) (l : list X) : list Y

(* REPLACE THIS LINE WITH := _your_definition_ . *) . Admitted.

Write down a theorem fold_map_correct in Coq stating that
fold_map is correct, and prove it.

(* FILL IN HERE *)

☐
#### Exercise: 2 stars, advanced (currying)

In Coq, a function f : A → B → C really has the type A
→ (B → C). That is, if you give f a value of type A, it
will give you function f' : B → C. If you then give f' a
value of type B, it will return a value of type C. This
allows for partial application, as in plus3. Processing a list
of arguments with functions that return functions is called
*currying*, in honor of the logician Haskell Curry.
Conversely, we can reinterpret the type A → B → C as (A *
B) → C. This is called *uncurrying*. With an uncurried binary
function, both arguments must be given at once as a pair; there is
no partial application.
We can define currying as follows:

As an exercise, define its inverse, prod_uncurry. Then prove
the theorems below to show that the two are inverses.

Definition prod_uncurry {X Y Z : Type}

(f : X → Y → Z) (p : X * Y) : Z

(* REPLACE THIS LINE WITH := _your_definition_ . *) . Admitted.

As a trivial example of the usefulness of currying, we can use it
to shorten one of the examples that we saw above:

Thought exercise: before running the following commands, can you
calculate the types of prod_curry and prod_uncurry?

Check @prod_curry.

Check @prod_uncurry.

Theorem uncurry_curry : ∀(X Y Z : Type)

(f : X → Y → Z)

x y,

prod_curry (prod_uncurry f) x y = f x y.

Proof.

(* FILL IN HERE *) Admitted.

Theorem curry_uncurry : ∀(X Y Z : Type)

(f : (X * Y) → Z) (p : X * Y),

prod_uncurry (prod_curry f) p = f p.

Proof.

(* FILL IN HERE *) Admitted.

☐
#### Exercise: 2 stars, advanced (nth_error_informal)

Recall the definition of the nth_error function:

☐
#### Exercise: 4 stars, advanced (church_numerals)

This exercise explores an alternative way of defining natural
numbers, using the so-called *Church numerals*, named after
mathematician Alonzo Church. We can represent a natural number
n as a function that takes a function f as a parameter and
returns f iterated n times.

Fixpoint nth_error {X : Type} (l : list X) (n : nat) : option X :=

match l with

| [] ⇒ None

| a :: l' ⇒ if beq_nat n O then Some a else nth_error l' (pred n)

end.

Write an informal proof of the following theorem:
match l with

| [] ⇒ None

| a :: l' ⇒ if beq_nat n O then Some a else nth_error l' (pred n)

end.

∀X n l, length l = n → @nth_error X l n = None

(* FILL IN HERE *)☐

Let's see how to write some numbers with this notation. Iterating
a function once should be the same as just applying it. Thus:

Similarly, two should apply f twice to its argument:

Defining zero is somewhat trickier: how can we "apply a function
zero times"? The answer is actually simple: just return the
argument untouched.

More generally, a number n can be written as fun X f x ⇒ f (f
... (f x) ...), with n occurrences of f. Notice in
particular how the doit3times function we've defined previously
is actually just the Church representation of 3.

Complete the definitions of the following functions. Make sure
that the corresponding unit tests pass by proving them with
reflexivity.
Successor of a natural number:

Definition succ (n : nat) : nat

(* REPLACE THIS LINE WITH := _your_definition_ . *) . Admitted.

Example succ_1 : succ zero = one.

Proof. (* FILL IN HERE *) Admitted.

Example succ_2 : succ one = two.

Proof. (* FILL IN HERE *) Admitted.

Example succ_3 : succ two = three.

Proof. (* FILL IN HERE *) Admitted.

Addition of two natural numbers:

Definition plus (n m : nat) : nat

(* REPLACE THIS LINE WITH := _your_definition_ . *) . Admitted.

Example plus_1 : plus zero one = one.

Proof. (* FILL IN HERE *) Admitted.

Example plus_2 : plus two three = plus three two.

Proof. (* FILL IN HERE *) Admitted.

Example plus_3 :

plus (plus two two) three = plus one (plus three three).

Proof. (* FILL IN HERE *) Admitted.

Multiplication:

Definition mult (n m : nat) : nat

(* REPLACE THIS LINE WITH := _your_definition_ . *) . Admitted.

Example mult_1 : mult one one = one.

Proof. (* FILL IN HERE *) Admitted.

Example mult_2 : mult zero (plus three three) = zero.

Proof. (* FILL IN HERE *) Admitted.

Example mult_3 : mult two three = plus three three.

Proof. (* FILL IN HERE *) Admitted.

Exponentiation:
(*Hint*: Polymorphism plays a crucial role here. However,
choosing the right type to iterate over can be tricky. If you hit
a "Universe inconsistency" error, try iterating over a different
type: nat itself is usually problematic.)

Definition exp (n m : nat) : nat

(* REPLACE THIS LINE WITH := _your_definition_ . *) . Admitted.

Example exp_1 : exp two two = plus two two.

Proof. (* FILL IN HERE *) Admitted.

Example exp_2 : exp three two = plus (mult two (mult two two)) one.

Proof. (* FILL IN HERE *) Admitted.

Example exp_3 : exp three zero = one.

Proof. (* FILL IN HERE *) Admitted.

End Church.

☐