(*|
================================================
Exercise session 2 — Inductive types — Solutions
================================================

:Authors: Yannick Forster, Théo Winterhalter
:Files:
  - `Source <../files/tp2c.v>`_
  - `Back to lesson <lesson2_part1.html>`_
  - `Back to lesson part 2 <lesson2_part2.html>`_

.. role:: coq(code)
   :language: coq
   :class: highlight

.. default-role:: coq
|*)

Set Default Goal Selector "!".

(* From the lecture: *)

From Stdlib  Require Import Datatypes List.
Open Scope nat.
Import ListNotations.
Fixpoint fast_rev {A} (l : list A) (acc : list A) :=
  match l with
  | [] => acc
  | x :: l => fast_rev l (x :: acc)
  end.

(*|
^^^^^^^^^^^^^^^^^^
Exercise: Reversal
^^^^^^^^^^^^^^^^^^
|*)

(*|
Prove the following lemmas from the lecture again. You will need auxiliary
lemmas: prove them yourself by induction and do not use lemmas from the
standard library.
|*)
Module Rev.

Lemma app_nil_r {A} (l : list A) :
  l ++ [] = l.
Proof.
  induction l as [| a l IHl]. all: simpl.
  - reflexivity.
  - rewrite IHl. reflexivity.
Qed.

Lemma app_assoc {A} (l1 l2 l3 : list A) :
  l1 ++ (l2 ++ l3) = (l1 ++ l2) ++ l3.
Proof.
  induction l1 as [| a l1 IHl]. all: simpl.
  - reflexivity.
  - rewrite IHl. reflexivity.
Qed.

Lemma rev_app_distr :
  forall {A} (l1 l2 : list A),
    rev (l1 ++ l2) = rev l2 ++ rev l1.
Proof.
  intros A l1 l2. induction l1 as [| a l1 IHl]. all: simpl.
  - rewrite app_nil_r. reflexivity.
  - rewrite IHl, app_assoc. reflexivity.
Qed.

Theorem rev_rev {X} (l : list X) :
  rev (rev l) = l.
Proof.
  induction l as [| a l IHl]. all: simpl.
  - reflexivity.
  - rewrite rev_app_distr, IHl. reflexivity.
Qed.

Lemma fast_rev_eq :
  forall A (l : list A),
    fast_rev l nil = rev l.
Proof.
  intros A l.
  assert (H : forall acc, fast_rev l acc = rev l ++ acc).
  { induction l as [| a l IHl]. all: simpl. all: intros acc.
    - reflexivity.
    - rewrite IHl, <- app_assoc. reflexivity.
  }
  rewrite H, app_nil_r. reflexivity.
Qed.

End Rev.

(* From the lecture: *)

Fixpoint iter {A : Type} (f : A -> A) (n : nat) (x : A) : A :=
  match n with
  | 0 => x
  | S n' => f (iter f n' x)
  end.

(*|
^^^^^^^^^^^^^^^^^^^
Exercise: Iteration
^^^^^^^^^^^^^^^^^^^
|*)

(*|
`Nat.pow x n` is `x` to the power of `n`.
You can use `Print Nat.pow.` to see the definition.
|*)
Fact iter_pow n x :
  Nat.pow x n = iter (Nat.mul x) n 1.
Proof.
  induction n as [| n IH]. all: simpl.
  - reflexivity.
  - rewrite IH. reflexivity.
Qed.
(*|
.. tip::

  The `rewrite` tactic can be used to rewrite an equality in the opposite
  direction using `rewrite <- e`. When `e : u = v`, it will replace `v` in the
  goal by `u`.

..
|*)
Fact iter_shift A (f : A -> A) n x :
  iter f (S n) x = iter f n (f x).
Proof.
  induction n as [| n IH].
  - reflexivity.
  - simpl in *. rewrite <- IH. reflexivity.
Qed.
(*| Define a tail-recursive iteration function. |*)
Fixpoint iter_tail {A : Type} (f : A -> A) (n : nat) (x : A) : A :=
  match n with
  | 0 => x
  | S n => iter_tail f n (f x)
  end.

Lemma iter_tail_correct {A : Type} (f : A -> A) (n : nat) (x : A) :
  iter f n x = iter_tail f n x.
Proof.
  revert x. induction n as [| n IH]. all: intros x.
  - reflexivity.
  - simpl. rewrite <- IH. apply iter_shift.
Qed.

(* From the lecture: *)

Inductive tree (A : Type) :=
| nnode : A -> forest A -> tree A

with forest (A : Type) :=
| nnil : forest A
| ncons : tree A -> forest A -> forest A.

Scheme tree_ind' := Induction for tree Sort Prop
    with forest_ind' := Induction for forest Sort Prop.
Combined Scheme tree_forest_mutind from tree_ind', forest_ind'.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Mapping over trees
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Define a map function for `tree`.

.. tip ::

  You probably will have to change `Definition` into something else.

..
|*)
Definition tree_map {A B} (f : A -> B) (t : tree A) : tree B :=
  (fix map_tree (t : tree A) : tree B :=
     match t with
     | nnode _ a l => nnode _ (f a) (map_forest l)
     end
   with map_forest (l : forest A) : forest B :=
     match l with
     | nnil _ => nnil _
     | ncons _ t tl => ncons _ (map_tree t) (map_forest tl)
     end
   for map_tree) t.

(* From the lecture: *)

From Stdlib Require Import Lia.

Lemma strong_nat_ind :
  forall (P : nat -> Prop),
    (forall n, (forall m, m < n -> P m) -> P n) ->
    forall n, P n.
Proof.
  intros P h n.
(*|
We'll show a stronger property by induction, that `P` is valid for `n` and
everything below.
|*)
  assert (hn : forall m, m <= n -> P m).
  { induction n as [| n ih].
    - intros m hm. inversion hm.
      apply h. intros k hk. lia.
(*|
`lia` knows there can't be `k < 0` so it solves the goal for us.
It is implicitly using a proof of `~ k < 0` together with `False`
elimination.
|*)
    - intros m hm. inversion hm.
      + apply h. intros k hk. apply ih. lia.
      + apply ih. lia.
  }
  apply hn. lia.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Strong induction
^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
We now allow you to use `lia`.
Prove strong induction yourself, without looking at the proof from the
lecture.
|*)
Module StrongInd.

Lemma strong_nat_ind :
  forall (P : nat -> Prop),
    (forall n, (forall m, m < n -> P m) -> P n) ->
    forall n, P n.
Proof.
  intros P h n.
  assert (hn : forall m, m <= n -> P m).
  { induction n as [| n ih].
    - intros m hm. inversion hm.
      apply h. intros k hk. lia.
    - intros m hm. inversion hm.
      + apply h. intros k hk. apply ih. lia.
      + apply ih. lia.
  }
  apply hn. lia.
Qed.

End StrongInd.

(*| You can now use `strong_nat_ind` in the following exercises. |*)
Import StrongInd.

(*|
^^^^^^^^^^^^^^^^^^
Exercise: Evenness
^^^^^^^^^^^^^^^^^^
|*)

(*| Here are two definitions of even numbers. |*)
Definition even1 n :=
  exists m, n = 2 * m.

Fixpoint even2 (n : nat) :=
  match n with
  | 0 => true
  | 1 => false
  | S (S n) => even2 n
  end.

(*|
Define an even predicate similar to how you would define a Boolean predicate
but using propositions instead.
|*)
Fixpoint even3 (n : nat) : Prop :=
  match n with
  | 0 => True
  | 1 => False
  | S (S n) => even3 n
  end.

(*| And a fourth one, as an inductive predicate. |*)
Inductive even4 : nat -> Prop :=
| even4O : even4 0
| even4S n : even4 n -> even4 (S (S n)).
(*|
Spell out the induction principle of `even4` without checking it.

⚠️ Do not forget this one.
|*)
(*|
.. code-block:: coq

  forall P : nat -> Prop,
    P 0 ->
    (forall n, even4 n -> P n -> P (S (S n))) ->
    forall n, even4 n -> P n
|*)
Check even4_ind.
(*|
.. tip::

  If you want to assert an equality `(e : a = b)` and then use
  `rewrite e`, then you can also make use of the `replace` tactic.
  `replace a with b` will replace `a` with `b` in the goal and ask you to prove
  the equality between the two.

..
|*)
Lemma even1_to_even2 n :
  even1 n ->
  even2 n = true.
Proof.
  intros [m e]. subst. induction m as [| m IH].
  - reflexivity.
  - replace (2 * S m) with (S (S (2 * m))) by lia.
    simpl. assumption.
Qed.
Lemma even2_iff_even3 n :
  even2 n = true <-> even3 n.
Proof.
  induction n as [n IH] using strong_nat_ind.
  destruct n as [| [| n]]. all: simpl.
  - split.
    + intros _. exact I.
    + intros _. reflexivity.
  - split.
    + intros h. discriminate.
    + intros h. contradiction.
  - apply IH. lia.
Qed.
(*|
.. tip ::

  The tactic `contradiction` is useful if you have an obviously false
  hypothesis.

..
|*)
Lemma even3_to_even4 n :
  even3 n ->
  even4 n.
Proof.
  induction n as [n IH] using strong_nat_ind.
  destruct n as [| [| n]]. all: simpl. all: intros h.
  - constructor.
  - contradiction.
  - constructor. apply IH.
    + lia.
    + assumption.
Qed.
Lemma even4_to_even1 n :
  even4 n ->
  even1 n.
Proof.
  intros h. induction h as [| n h [m e]].
  - exists 0. reflexivity.
  - exists (S m). lia.
Qed.

(* From the lecture: *)
Inductive le : nat -> nat -> Prop :=
| leO n : le n n
| leS n m : le n m -> le n (S m).

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Another definition of le
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

Inductive le' : nat -> nat -> Prop :=
| leO' n : le' 0 n
| leS' n m : le' n m -> le' (S n) (S m).

(*|
Spell out the induction principle of `le'` without checking it.
Notice that it's *not* the same definition as `le` above.

⚠️ Do not forget this one.
|*)
(*|
.. code-block:: coq

  forall P : nat -> nat -> Prop,
    (forall n, P 0 n) ->
    (forall n m, le' n m -> P n m -> P (S n) (S m)) ->
    forall n m, le' n m -> P n m
|*)
Check le'_ind.
(*|
Prove the following, and the lemmas that you need, by induction.
Do not use the standard library or `lia`!
|*)
Lemma le_0_n n :
  le 0 n.
Proof.
  induction n as [| n IH].
  - constructor.
  - constructor. assumption.
Qed.

Lemma le_n_S n m :
  le n m -> le (S n) (S m).
Proof.
  intros h. induction h as [n | n m h IH].
  - constructor.
  - constructor. assumption.
Qed.

Lemma le'_refl n :
  le' n n.
Proof.
  induction n as [| n IH].
  - constructor.
  - constructor. assumption.
Qed.

Lemma le'_S n m :
  le' n m -> le' n (S m).
Proof.
  intros h. induction h as [n | n m h IH].
  - constructor.
  - constructor. assumption.
Qed.

Lemma le_equiv n m :
  le' n m <-> le n m.
Proof.
  split.
  - intros h. induction h as [n | n m h IH].
    + apply le_0_n.
    + apply le_n_S. assumption.
  - intros h. induction h as [n | n m h IH].
    + apply le'_refl.
    + apply le'_S. assumption.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Boolean comparison
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

Fixpoint leb (n m : nat) : bool :=
  match n, m with
  | 0, _ => true
  | S _, 0 => false
  | S n, S m => leb n m
  end.
Lemma leb_le' n m :
  leb n m = true <-> le' n m.
Proof.
  revert m. induction n as [| n IH]. all: intros m.
  - split.
    + intros _. constructor.
    + intros _. reflexivity.
  - destruct m as [| m].
    + split.
      * intros h. discriminate.
      * intros h. inversion h.
    + simpl. rewrite IH. split.
      * intros h. constructor. assumption.
      * intros h. inversion h. assumption.
Qed.

Lemma leb_spec n m :
  leb n m = true <-> le n m.
Proof.
  rewrite leb_le'. apply le_equiv.
Qed.

(* From the lecture: *)

From Stdlib Require Import Lia List.

Inductive rtree (A : Type) :=
| N (a : A) (ts : list (rtree A)).

Inductive Forall {A} (P : A -> Prop) : list A -> Prop :=
| Forall_nil : Forall P nil
| Forall_cons a l : P a -> Forall P l -> Forall P (a :: l).

Fixpoint rtree_ind' :
  forall (A : Type) (P : rtree A -> Prop),
    (forall (a : A) (ts : list (rtree A)), @Forall (rtree A) P ts -> P (N A a ts)) ->
    forall r : rtree A, P r.
Proof.
  intros A P IH r.
  destruct r.
  apply IH. induction ts.
  - econstructor.
  - econstructor.
    + eapply rtree_ind'. assumption.
    + assumption.
Qed.

Scheme All for list.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Unlabelled trees
^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Consider the following type of trees, without labels.
Can you give an element of type `tree`?
|*)
Module Unlabelled.

Inductive tree :=
| N (ts : list tree).

Definition ex4 : tree :=
  N [].

End Unlabelled.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: All and Forall
^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Here is a variant of `Forall` in `Type`. We also make the arguments of
the constructors of `All` and `Forall` implicit.
|*)
Inductive All {X} (P : X -> Type) : list X -> Type :=
| All_nil : All P nil
| All_cons x l : P x -> All P l -> All P (x :: l).

Arguments All_nil {X P}.
Arguments All_cons {X P}.
Arguments Forall_nil {A P}.
Arguments Forall_cons {A P}.

(*|
Give the induction principles for both `All` and `Forall`. For every argument,
state whether it is a parameter, non-uniform parameter, or index.
|*)
(*|
In both cases, the type (`X` or `A`) and the predicate `P` are parameters and
the list is an index. Note that the induction principle of `All`, which lives
in `Type`, is dependent: the predicate also takes the proof of `All P l`.
|*)
Check All_ind.
Check Forall_ind.
(*| Prove the following. |*)
Lemma All_Forall {A} (P : A -> Prop) (l : list A) :
  All P l -> Forall P l.
Proof.
  intros h. induction h as [| x l px h IH].
  - constructor.
  - constructor.
    + assumption.
    + assumption.
Qed.

Lemma Forall_app {A} (P : A -> Prop) (l1 l2 : list A) :
  Forall P l1 -> Forall P l2 -> Forall P (l1 ++ l2).
Proof.
  intros h1 h2. induction h1 as [| a l pa h1 IH]. all: simpl.
  - assumption.
  - constructor.
    + assumption.
    + assumption.
Qed.

Fixpoint All_app {A} (P : A -> Prop) (l1 l2 : list A) (h1 : All P l1) (h2 : All P l2) {struct h1} : All P (l1 ++ l2) :=
  match h1 in @All _ _ l1 return All P (l1 ++ l2) with
  | All_nil => h2
  | All_cons x l px hl => All_cons x (l ++ l2) px (All_app P l l2 hl h2)
  end.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Labelled trees
^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
- Extend the type `Unlabelled.tree` to have labelled nodes.
- Prove a bijection between the new type and the mutual `tree` from the first
  part, i.e. define functions from one to the other and show that they invert
  each other.
|*)
(*| The labelled version is exactly `rtree` from above. |*)
Fixpoint to_rtree {A} (t : tree A) : rtree A :=
  match t with
  | nnode _ a f => N A a (to_rtree_forest f)
  end
with to_rtree_forest {A} (f : forest A) : list (rtree A) :=
  match f with
  | nnil _ => []
  | ncons _ t f => to_rtree t :: to_rtree_forest f
  end.

Fixpoint from_rtree {A} (t : rtree A) : tree A :=
  match t with
  | N _ a ts =>
    nnode A a ((fix from_list (ts : list (rtree A)) : forest A :=
                  match ts with
                  | [] => nnil A
                  | t :: ts => ncons A (from_rtree t) (from_list ts)
                  end) ts)
  end.

Lemma from_to_rtree {A} (t : tree A) :
  from_rtree (to_rtree t) = t.
Proof.
  refine (proj1 (tree_forest_mutind A (fun t => from_rtree (to_rtree t) = t)
    (fun f => forall a, from_rtree (N A a (to_rtree_forest f)) = nnode A a f) _ _ _) t).
  - intros a f IH. exact (IH a).
  - intros a. reflexivity.
  - intros t' IHt f IHf a. specialize (IHf a). cbn in *.
    injection IHf as IHf. rewrite IHt, IHf. reflexivity.
Qed.

Lemma to_from_rtree {A} (t : rtree A) :
  to_rtree (from_rtree t) = t.
Proof.
  revert t. apply rtree_ind'.
  intros a ts IH. cbn. f_equal.
  induction IH as [| t ts ht hts IHts].
  - reflexivity.
  - cbn. rewrite ht, IHts. reflexivity.
Qed.

(* From the lecture: *)

Inductive rtclos {A} (R : A -> A -> Prop) (x : A) : A -> Prop :=
| refl : rtclos R x x
| incl y : R x y -> rtclos R x y
| trans y z : rtclos R x y -> rtclos R y z -> rtclos R x z.

Arguments trans {A R}.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Membership in a list
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

Fixpoint In {A} (x : A) (l : list A) : Prop :=
  match l with
  | nil => False
  | y :: m => y = x \/ In x m
  end.

(*|
Propose an inductive definition of membership
(add the missing constructor(s)).
|*)
Inductive In_i {A} : A -> list A -> Prop :=
| In_here x l : In_i x (x :: l)
| In_there x y l : In_i x l -> In_i x (y :: l).
Lemma In_iff A (x : A) l :
  In x l <-> In_i x l.
Proof.
  split.
  - induction l as [| y l IH]. all: simpl. all: intros h.
    + contradiction.
    + destruct h as [e | h].
      * subst. apply In_here.
      * apply In_there. apply IH. assumption.
  - intros h. induction h as [x l | x y l h IH]. all: simpl.
    + left. reflexivity.
    + right. assumption.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Reflexive transitive closure
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*| Here is another definition of the reflexive transitive closure. |*)
Inductive rtclos' {A} (R : A -> A -> Prop) : A -> A -> Prop :=
| refl' x : rtclos' R x x
| trans' x y z : R x y -> rtclos' R y z -> rtclos' R x z.

(*|
.. tip::

  You can use `apply f with u` to provide `u` as argument to `f` when
  Rocq can't guess it on its own.

..
|*)
Lemma rtclos'_trans :
  forall A (R : A -> A -> Prop) x y z,
    rtclos' R x y ->
    rtclos' R y z ->
    rtclos' R x z.
Proof.
  intros A R x y z h1 h2. induction h1 as [x | x w y r h1 IH].
  - assumption.
  - apply trans' with w.
    + assumption.
    + apply IH. assumption.
Qed.
Lemma rtclos_iff :
  forall A (R : A -> A -> Prop) x y,
    rtclos R x y <-> rtclos' R x y.
Proof.
  intros A R x y. split.
  - intros h. induction h as [x | x y r | x y z h1 IH1 h2 IH2].
    + apply refl'.
    + apply trans' with y.
      * assumption.
      * apply refl'.
    + apply rtclos'_trans with y.
      * assumption.
      * assumption.
  - intros h. induction h as [x | x w y r h IH].
    + apply refl.
    + apply (trans x w y).
      * apply incl. assumption.
      * assumption.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Factorial and Fibonacci (advanced)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
This and the following exercises are more advanced. Make sure you manage to do
the previous exercises before. Do not hesitate to ask for help.

Define the factorial function in two ways:

- once using `Fixpoint`
- and once using `iter`

Prove that both yield the same value for all arguments.

⚠️ Do not forget this one. We have not stated the lemmas this time.
|*)
Fixpoint fact (n : nat) : nat :=
  match n with
  | 0 => 1
  | S n => S n * fact n
  end.

Definition fact_iter (n : nat) : nat :=
  snd (iter (fun '(k, r) => (S k, S k * r)) n (0, 1)).

Lemma fact_iter_correct n :
  fact_iter n = fact n.
Proof.
  unfold fact_iter.
  assert (h : iter (fun '(k, r) => (S k, S k * r)) n (0, 1) = (n, fact n)).
  { induction n as [| n IH].
    - reflexivity.
    - cbn [iter]. rewrite IH. reflexivity.
  }
  rewrite h. reflexivity.
Qed.
(*|
Define the Fibonacci function, using only `iter` (no recursive definition).
As a reminder `fib 0 = 0`, `fib 1 = 1` and `fib (n+2) = fib (n+1) + fib n`.
Then prove that it satisfies these equations.
|*)
Module Fib_Iter.

  Definition fib (n : nat) : nat :=
    fst (iter (fun '(a, b) => (b, a + b)) n (0, 1)).

  Lemma fib_eq0 :
    fib 0 = 0.
  Proof.
    reflexivity.
  Qed.

  Lemma fib_eq1 :
    fib 1 = 1.
  Proof.
    reflexivity.
  Qed.

  Lemma fib_eq3 :
    forall n,
      fib (S (S n)) = fib n + fib (S n).
  Proof.
    intros n. unfold fib. cbn [iter].
    destruct (iter (fun '(a, b) => (b, a + b)) n (0, 1)) as [a b].
    reflexivity.
  Qed.

End Fib_Iter.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Cantor pairing (advanced)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Here is an implementation of the Cantor pairing and its inverse function,
a bijection between `nat * nat` and `nat`.
|*)
From Stdlib Require Import PeanoNat.

Fixpoint to_nat' n :=
  match n with
  | 0 => 0
  | S i => S i + to_nat' i
  end.

(*|
Note that the following notation `'(x, y)` is performing pattern matching
implicitly.
|*)
Definition to_nat '(x, y) : nat :=
  y + to_nat' (y + x).

Fixpoint of_nat (n : nat) : nat * nat :=
  match n with
  | 0 => (0,0)
  | S i =>
    let '(x,y) := of_nat i in
    match x with
    | 0 => (S y, 0)
    | S x => (x, S y)
    end
  end.

(*|
Show that `of_nat` is a left inverse for `to_nat`.

.. tip::

  First show `forall n p, to_nat p = n -> of_nat n = p`.

..
|*)
Lemma cancel_of_to :
  forall p,
    of_nat (to_nat p) = p.
Proof.
  assert (H : forall n p, to_nat p = n -> of_nat n = p).
  { induction n as [| n IH]. all: intros [x y] h.
    - destruct x as [| x], y as [| y]. all: simpl in h.
      all: try discriminate.
      reflexivity.
    - destruct y as [| y].
      + destruct x as [| x].
        * simpl in h. discriminate.
        * assert (e : to_nat (0, x) = n).
          { simpl in h |- *. rewrite Nat.add_0_r. lia. }
          simpl. rewrite (IH _ e). reflexivity.
      + assert (e : to_nat (S x, y) = n).
        { simpl in h |- *. rewrite Nat.add_succ_r. simpl. lia. }
        simpl. rewrite (IH _ e). reflexivity.
  }
  intros p. apply H. reflexivity.
Qed.

(*| Show `to_nat` is injective. |*)
Corollary to_nat_inj :
  forall p q,
    to_nat p = to_nat q ->
    p = q.
Proof.
  intros p q h.
  rewrite <- (cancel_of_to p), <- (cancel_of_to q), h. reflexivity.
Qed.

(*| Show `to_nat` is a left inverse for `of_nat`. |*)
Lemma cancel_to_of :
  forall n,
    to_nat (of_nat n) = n.
Proof.
  induction n as [| n IH].
  - reflexivity.
  - simpl. destruct (of_nat n) as [x y] eqn: e. destruct x as [| x].
    + simpl in *. rewrite Nat.add_0_r in IH. lia.
    + simpl in *. rewrite Nat.add_succ_r in IH. simpl in IH. lia.
Qed.

(*| Show `of_nat` is injective. |*)
Corollary of_nat_inj :
  forall n m,
    of_nat n = of_nat m ->
    n = m.
Proof.
  intros n m h.
  rewrite <- (cancel_to_of n), <- (cancel_to_of m), h. reflexivity.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Church encodings (advanced)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
It is possible to encode natural numbers (and other data types) using
so-called Church encodings that you might have seen in a λ-calculus class.
Below, `num` is the definition of Church numerals.
|*)
Definition num :=
  forall (X : Prop) (s : X -> X) (z : X), X.

Definition zero : num :=
  fun X s z => z.

Definition succ : num -> num :=
  fun n X s z => s (n X s z).

Fixpoint from_nat n : num :=
  match n with
  | 0 => zero
  | S n => succ (from_nat n)
  end.

Definition add : num -> num -> num :=
  fun n m X s z => n X s (m X s z).

Compute (add (from_nat 3) (from_nat 2)).

Lemma add_from_nat :
  forall n m,
    add (from_nat n) (from_nat m) = from_nat (n + m).
Proof.
  intros n m. induction n as [| n IH].
  - reflexivity.
  - simpl. rewrite <- IH. reflexivity.
Qed.
Definition mul : num -> num -> num :=
  fun n m X s z => n X (m X s) z.

Lemma mul_from_nat :
  forall n m,
    mul (from_nat n) (from_nat m) = from_nat (n * m).
Proof.
  intros n m. induction n as [| n IH].
  - reflexivity.
  - simpl. rewrite <- add_from_nat, <- IH. reflexivity.
Qed.
(*|
Define the power function (check out the lemma to make sure you
see what it should give).
|*)
Definition exp : num -> num -> num :=
  fun n m X => m (X -> X) (n X).

Lemma exp_from_nat n m :
  exp (from_nat n) (from_nat m) = from_nat (Nat.pow n m).
Proof.
  induction m as [| m IH].
  - reflexivity.
  - simpl. rewrite <- mul_from_nat, <- IH. reflexivity.
Qed.
(*| Define a predecessor function. |*)
Definition pred : num -> num :=
  fun n X s z => n ((X -> X) -> X) (fun g h => h (g s)) (fun _ => z) (fun x => x).

(*|
Two functions that give the same results are not necessarily equal in Rocq, so
we need the axiom of functional extensionality.
|*)
From Stdlib Require Import FunctionalExtensionality.

Lemma pred_aux n X s z :
  from_nat n ((X -> X) -> X) (fun g h => h (g s)) (fun _ => z) s = from_nat n X s z.
Proof.
  induction n as [| n IH].
  - reflexivity.
  - simpl. unfold succ. rewrite IH. reflexivity.
Qed.

Lemma pred_from_nat n :
  pred (from_nat n) = from_nat (Nat.pred n).
Proof.
  destruct n as [| n].
  - reflexivity.
  - unfold pred. simpl.
    extensionality X. extensionality s. extensionality z.
    apply pred_aux.
Qed.
