# BasicsFunctional Programming in Coq

Inductive day : Type :=

| monday

| tuesday

| wednesday

| thursday

| friday

| saturday

| sunday.

| monday

| tuesday

| wednesday

| thursday

| friday

| saturday

| sunday.

Definition next_weekday (d:day) : day :=

match d with

| monday ⇒ tuesday

| tuesday ⇒ wednesday

| wednesday ⇒ thursday

| thursday ⇒ friday

| friday ⇒ monday

| saturday ⇒ monday

| sunday ⇒ monday

end.

match d with

| monday ⇒ tuesday

| tuesday ⇒ wednesday

| wednesday ⇒ thursday

| thursday ⇒ friday

| friday ⇒ monday

| saturday ⇒ monday

| sunday ⇒ monday

end.

Compute (next_weekday friday).

(* ==> monday : day *)

Compute (next_weekday (next_weekday saturday)).

(* ==> tuesday : day *)

(* ==> monday : day *)

Compute (next_weekday (next_weekday saturday)).

(* ==> tuesday : day *)

Second, we can record what we

*expect*the result to be in the form of a Coq example:
Example test_next_weekday:

(next_weekday (next_weekday saturday)) = tuesday.

(next_weekday (next_weekday saturday)) = tuesday.

A proof script giving evidence for the claim:

Proof. simpl. reflexivity. Qed.

Inductive bool : Type :=

| true

| false.

| true

| false.

Booleans are also available from Coq's standard library, but
in this course we'll define everything from scratch, just to see
how it's done.

Definition negb (b:bool) : bool :=

match b with

| true ⇒ false

| false ⇒ true

end.

Definition andb (b

match b

| true ⇒ b

| false ⇒ false

end.

Definition orb (b

match b

| true ⇒ true

| false ⇒ b

end.

_{1}:bool) (b_{2}:bool) : bool :=match b

_{1}with| true ⇒ b

_{2}| false ⇒ false

end.

Definition orb (b

_{1}:bool) (b_{2}:bool) : bool :=match b

_{1}with| true ⇒ true

| false ⇒ b

_{2}end.

Example test_orb1: (orb true false) = true.

Proof. simpl. reflexivity. Qed.

Example test_orb2: (orb false false) = false.

Proof. simpl. reflexivity. Qed.

Example test_orb3: (orb false true) = true.

Proof. simpl. reflexivity. Qed.

Example test_orb4: (orb true true) = true.

Proof. simpl. reflexivity. Qed.

We can define new symbolic notation for an existing definition.

Notation "x && y" := (andb x y).

Notation "x || y" := (orb x y).

Example test_orb5: false || false || true = true.

Proof. simpl. reflexivity. Qed.

Notation "x || y" := (orb x y).

Example test_orb5: false || false || true = true.

Proof. simpl. reflexivity. Qed.

#### Exercise: 1 star, standard (nandb)

Remove "Admitted." and complete the definition of the following function; then make sure that the Example assertions below can each be verified by Coq. (I.e., fill in each proof, following the model of the orb tests above.) The function should return true if either or both of its inputs are false.
Definition nandb (b

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

Example test_nandb1: (nandb true false) = true.

(* FILL IN HERE *) Admitted.

Example test_nandb2: (nandb false false) = true.

(* FILL IN HERE *) Admitted.

Example test_nandb3: (nandb false true) = true.

(* FILL IN HERE *) Admitted.

Example test_nandb4: (nandb true true) = false.

(* FILL IN HERE *) Admitted.

☐
_{1}:bool) (b_{2}:bool) : bool(* REPLACE THIS LINE WITH ":= _your_definition_ ." *). Admitted.

Example test_nandb1: (nandb true false) = true.

(* FILL IN HERE *) Admitted.

Example test_nandb2: (nandb false false) = true.

(* FILL IN HERE *) Admitted.

Example test_nandb3: (nandb false true) = true.

(* FILL IN HERE *) Admitted.

Example test_nandb4: (nandb true true) = false.

(* FILL IN HERE *) Admitted.

## Types

Check true.

(* ===> true : bool *)

Check (negb true).

(* ===> negb true : bool *)

(* ===> true : bool *)

Check (negb true).

(* ===> negb true : bool *)

Functions like negb itself are also data values, just like
true and false. Their types are called

*function types*, and they are written with arrows.
Check negb.

(* ===> negb : bool -> bool *)

(* ===> negb : bool -> bool *)

Inductive rgb : Type :=

| red

| green

| blue.

Inductive color : Type :=

| black

| white

| primary (p : rgb).

| red

| green

| blue.

Inductive color : Type :=

| black

| white

| primary (p : rgb).

In general, Inductive declarations introduce "inductively
defined sets," which consist of all legal combinations of the
constructors.
Every inductively defined type (day, bool, rgb, color,
etc.) contains a set of

We can define functions on colors using pattern matching just as
we have done for day and bool.

### Let's look at this in a little more detail.

*constructor expressions*built from*constructors*like red, primary, true, false, monday, etc.### The definitions of rgb and color say how expressions in the sets rgb and color can be built:

- red, green, and blue are the constructors of rgb;
- black, white, and primary are the constructors of color;
- the expression red belongs to the set rgb, as do the expressions green and blue;
- the expressions black and white belong to the set color;
- if p is an expression belonging to the set rgb, then primary p (pronounced "the constructor primary applied to the argument p") is an expression belonging to the set color; and
- expressions formed in these ways are the
*only*ones belonging to the sets rgb and color.

Definition monochrome (c : color) : bool :=

match c with

| black ⇒ true

| white ⇒ true

| primary q ⇒ false

end.

match c with

| black ⇒ true

| white ⇒ true

| primary q ⇒ false

end.

Since the primary constructor takes an argument, a pattern
matching primary should include either a variable (as above —
note that we can choose its name freely) or a constant of
appropriate type (as below).

Definition isred (c : color) : bool :=

match c with

| black ⇒ false

| white ⇒ false

| primary red ⇒ true

| primary _ ⇒ false

end.

match c with

| black ⇒ false

| white ⇒ false

| primary red ⇒ true

| primary _ ⇒ false

end.

The pattern primary _ here is shorthand for "primary applied
to any rgb constructor except red." (The wildcard pattern _
has the same effect as the dummy pattern variable p in the
definition of monochrome.)

Inductive bit : Type :=

| B

| B

Inductive nybble : Type :=

| bits (b

Check (bits B

(* ==> bits B

| B

_{0}| B

_{1}.Inductive nybble : Type :=

| bits (b

_{0}b_{1}b_{2}b_{3}: bit).Check (bits B

_{1}B_{0}B_{1}B_{0}).(* ==> bits B

_{1}B_{0}B_{1}B_{0}: nybble *)
Definition all_zero (nb : nybble) : bool :=

match nb with

| (bits B

| (bits _ _ _ _) ⇒ false

end.

Compute (all_zero (bits B

(* ===> false : bool *)

Compute (all_zero (bits B

(* ===> true : bool *)

match nb with

| (bits B

_{0}B_{0}B_{0}B_{0}) ⇒ true| (bits _ _ _ _) ⇒ false

end.

Compute (all_zero (bits B

_{1}B_{0}B_{1}B_{0})).(* ===> false : bool *)

Compute (all_zero (bits B

_{0}B_{0}B_{0}B_{0})).(* ===> true : bool *)

## Modules

Module NatPlayground.

## Numbers

*n*gives the representation of

*n+1*.

Inductive nat : Type :=

| O

| S (n : nat).

| O

| S (n : nat).

With this definition, 0 is represented by O, 1 by S O,
2 by S (S O), and so on.
Again, let's look at this in a little more detail. The definition
of nat says how expressions in the set nat can be built:

Critical point: this just defines a
We could just as well represent numbers with different marks:

- O and S are constructors;
- the expression O belongs to the set nat;
- if n is an expression belonging to the set nat, then S n is also an expression belonging to the set nat; and
- expressions formed in these two ways are the only ones belonging to the set nat.

*representation*of numbers — a unary notation for writing them down.- The names O and S are arbitrary.
- They are just two different "marks", with no intrinsic meaning.

Inductive nat' : Type :=

| stop

| tick (foo : nat').

| stop

| tick (foo : nat').

The

*interpretation*of these marks comes from how we use them to compute.
Definition pred (n : nat) : nat :=

match n with

| O ⇒ O

| S n' ⇒ n'

end.

End NatPlayground.

match n with

| O ⇒ O

| S n' ⇒ n'

end.

End NatPlayground.

Check (S (S (S (S O)))).

(* ===> 4 : nat *)

Definition minustwo (n : nat) : nat :=

match n with

| O ⇒ O

| S O ⇒ O

| S (S n') ⇒ n'

end.

Compute (minustwo 4).

(* ===> 2 : nat *)

(* ===> 4 : nat *)

Definition minustwo (n : nat) : nat :=

match n with

| O ⇒ O

| S O ⇒ O

| S (S n') ⇒ n'

end.

Compute (minustwo 4).

(* ===> 2 : nat *)

Fixpoint evenb (n:nat) : bool :=

match n with

| O ⇒ true

| S O ⇒ false

| S (S n') ⇒ evenb n'

end.

match n with

| O ⇒ true

| S O ⇒ false

| S (S n') ⇒ evenb n'

end.

Definition oddb (n:nat) : bool := negb (evenb n).

Example test_oddb1: oddb 1 = true.

Proof. simpl. reflexivity. Qed.

Example test_oddb2: oddb 4 = false.

Proof. simpl. reflexivity. Qed.

Example test_oddb1: oddb 1 = true.

Proof. simpl. reflexivity. Qed.

Example test_oddb2: oddb 4 = false.

Proof. simpl. reflexivity. Qed.

Module NatPlayground2.

Fixpoint plus (n : nat) (m : nat) : nat :=

match n with

| O ⇒ m

| S n' ⇒ S (plus n' m)

end.

Compute (plus 3 2).

(* plus (S (S (S O))) (S (S O))

==> S (plus (S (S O)) (S (S O)))

by the second clause of the match

==> S (S (plus (S O) (S (S O))))

by the second clause of the match

==> S (S (S (plus O (S (S O)))))

by the second clause of the match

==> S (S (S (S (S O))))

by the first clause of the match

*)

Fixpoint plus (n : nat) (m : nat) : nat :=

match n with

| O ⇒ m

| S n' ⇒ S (plus n' m)

end.

Compute (plus 3 2).

(* plus (S (S (S O))) (S (S O))

==> S (plus (S (S O)) (S (S O)))

by the second clause of the match

==> S (S (plus (S O) (S (S O))))

by the second clause of the match

==> S (S (S (plus O (S (S O)))))

by the second clause of the match

==> S (S (S (S (S O))))

by the first clause of the match

*)

Fixpoint mult (n m : nat) : nat :=

match n with

| O ⇒ O

| S n' ⇒ plus m (mult n' m)

end.

Example test_mult1: (mult 3 3) = 9.

Proof. simpl. reflexivity. Qed.

match n with

| O ⇒ O

| S n' ⇒ plus m (mult n' m)

end.

Example test_mult1: (mult 3 3) = 9.

Proof. simpl. reflexivity. Qed.

Fixpoint minus (n m:nat) : nat :=

match n, m with

| O , _ ⇒ O

| S _ , O ⇒ n

| S n', S m' ⇒ minus n' m'

end.

End NatPlayground2.

match n, m with

| O , _ ⇒ O

| S _ , O ⇒ n

| S n', S m' ⇒ minus n' m'

end.

End NatPlayground2.

### Again, we can make numerical expressions easier to read and write by introducing notations for addition, multiplication, and subtraction.

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

(at level 50, left associativity)

: nat_scope.

Notation "x - y" := (minus x y)

(at level 50, left associativity)

: nat_scope.

Notation "x * y" := (mult x y)

(at level 40, left associativity)

: nat_scope.

Check ((0 + 1) + 1).

(at level 50, left associativity)

: nat_scope.

Notation "x - y" := (minus x y)

(at level 50, left associativity)

: nat_scope.

Notation "x * y" := (mult x y)

(at level 40, left associativity)

: nat_scope.

Check ((0 + 1) + 1).

### When we say that Coq comes with almost nothing built-in, we really mean it: even equality testing is a user-defined operation!

Fixpoint eqb (n m : nat) : bool :=

match n with

| O ⇒ match m with

| O ⇒ true

| S m' ⇒ false

end

| S n' ⇒ match m with

| O ⇒ false

| S m' ⇒ eqb n' m'

end

end.

match n with

| O ⇒ match m with

| O ⇒ true

| S m' ⇒ false

end

| S n' ⇒ match m with

| O ⇒ false

| S m' ⇒ eqb n' m'

end

end.

### Similarly, the leb function tests whether its first argument is less than or equal to its second argument, yielding a boolean.

Fixpoint leb (n m : nat) : bool :=

match n with

| O ⇒ true

| S n' ⇒

match m with

| O ⇒ false

| S m' ⇒ leb n' m'

end

end.

Example test_leb1: (leb 2 2) = true.

Proof. simpl. reflexivity. Qed.

Example test_leb2: (leb 2 4) = true.

Proof. simpl. reflexivity. Qed.

Example test_leb3: (leb 4 2) = false.

Proof. simpl. reflexivity. Qed.

match n with

| O ⇒ true

| S n' ⇒

match m with

| O ⇒ false

| S m' ⇒ leb n' m'

end

end.

Example test_leb1: (leb 2 2) = true.

Proof. simpl. reflexivity. Qed.

Example test_leb2: (leb 2 4) = true.

Proof. simpl. reflexivity. Qed.

Example test_leb3: (leb 4 2) = false.

Proof. simpl. reflexivity. Qed.

Since we'll be using these (especially eqb) a lot, let's give
them infix notations.

Notation "x =? y" := (eqb x y) (at level 70) : nat_scope.

Notation "x <=? y" := (leb x y) (at level 70) : nat_scope.

Example test_leb3': (4 <=? 2) = false.

Proof. simpl. reflexivity. Qed.

Notation "x <=? y" := (leb x y) (at level 70) : nat_scope.

Example test_leb3': (4 <=? 2) = false.

Proof. simpl. reflexivity. Qed.

Theorem plus_O_n : ∀n : nat, 0 + n = n.

Proof.

intros n. simpl. reflexivity. Qed.

Proof.

intros n. simpl. reflexivity. Qed.

The simpl tactic is actually redundant, as reflexivity
already does some simplification for us:

Theorem plus_O_n' : ∀n : nat, 0 + n = n.

Proof.

intros n. reflexivity. Qed.

Proof.

intros n. reflexivity. Qed.

Theorem plus_1_l : ∀n:nat, 1 + n = S n.

Proof.

intros n. reflexivity. Qed.

Theorem mult_0_l : ∀n:nat, 0 * n = 0.

Proof.

intros n. reflexivity. Qed.

Proof.

intros n. reflexivity. Qed.

Theorem mult_0_l : ∀n:nat, 0 * n = 0.

Proof.

intros n. reflexivity. Qed.

Theorem plus_id_example : ∀n m:nat,

n = m →

n + n = m + m.

Proof.

(* move both quantifiers into the context: *)

intros n m.

(* move the hypothesis into the context: *)

intros H.

(* rewrite the goal using the hypothesis: *)

rewrite → H.

reflexivity. Qed.

n = m →

n + n = m + m.

Proof.

(* move both quantifiers into the context: *)

intros n m.

(* move the hypothesis into the context: *)

intros H.

(* rewrite the goal using the hypothesis: *)

rewrite → H.

reflexivity. Qed.

The uses of intros name the hypotheses as they are moved
to the context. The rewrite needs to know which equality is being
used and in which direction to do the replacement.

### We can also use the rewrite tactic with a previously proved theorem instead of a hypothesis from the context. If the statement of the previously proved theorem involves quantified variables, as in the example below, Coq tries to instantiate them by matching with the current goal.

Theorem mult_0_plus : ∀n m : nat,

(0 + n) * m = n * m.

Proof.

intros n m.

rewrite → plus_O_n.

reflexivity. Qed.

(0 + n) * m = n * m.

Proof.

intros n m.

rewrite → plus_O_n.

reflexivity. Qed.

Theorem plus_1_neq_0_firsttry : ∀n : nat,

(n + 1) =? 0 = false.

Proof.

intros n.

simpl. (* does nothing! *)

Abort.

(n + 1) =? 0 = false.

Proof.

intros n.

simpl. (* does nothing! *)

Abort.

We can use destruct to perform case analysis:

Theorem plus_1_neq_0 : ∀n : nat,

(n + 1) =? 0 = false.

Proof.

intros n. destruct n as [| n'] eqn:E.

- reflexivity.

- reflexivity. Qed.

(n + 1) =? 0 = false.

Proof.

intros n. destruct n as [| n'] eqn:E.

- reflexivity.

- reflexivity. Qed.

Theorem negb_involutive : ∀b : bool,

negb (negb b) = b.

Proof.

intros b. destruct b eqn:E.

- reflexivity.

- reflexivity. Qed.

negb (negb b) = b.

Proof.

intros b. destruct b eqn:E.

- reflexivity.

- reflexivity. Qed.

Theorem andb_commutative : ∀b c, andb b c = andb c b.

Proof.

intros b c. destruct b eqn:Eb.

- destruct c eqn:Ec.

+ reflexivity.

+ reflexivity.

- destruct c eqn:Ec.

+ reflexivity.

+ reflexivity.

Qed.

Proof.

intros b c. destruct b eqn:Eb.

- destruct c eqn:Ec.

+ reflexivity.

+ reflexivity.

- destruct c eqn:Ec.

+ reflexivity.

+ reflexivity.

Qed.

### Besides - and +, we can use * (asterisk) as a third kind of bullet. We can also enclose sub-proofs in curly braces, which is useful in case we ever encounter a proof that generates more than three levels of subgoals:

Theorem andb_commutative' : ∀b c, andb b c = andb c b.

Proof.

intros b c. destruct b eqn:Eb.

{ destruct c eqn:Ec.

{ reflexivity. }

{ reflexivity. } }

{ destruct c eqn:Ec.

{ reflexivity. }

{ reflexivity. } }

Qed.

Proof.

intros b c. destruct b eqn:Eb.

{ destruct c eqn:Ec.

{ reflexivity. }

{ reflexivity. } }

{ destruct c eqn:Ec.

{ reflexivity. }

{ reflexivity. } }

Qed.

Theorem plus_1_neq_0' : ∀n : nat,

(n + 1) =? 0 = false.

Proof.

intros [|n].

- reflexivity.

- reflexivity. Qed.

(n + 1) =? 0 = false.

Proof.

intros [|n].

- reflexivity.

- reflexivity. Qed.

Theorem andb_commutative'' :

∀b c, andb b c = andb c b.

Proof.

intros [] [].

- reflexivity.

- reflexivity.

- reflexivity.

- reflexivity.

Qed.

∀b c, andb b c = andb c b.

Proof.

intros [] [].

- reflexivity.

- reflexivity.

- reflexivity.

- reflexivity.

Qed.