(*|
--------------------------------
Advanced elimination / induction
--------------------------------

:Authors: Yannick Forster, Théo Winterhalter
:Files:
  - `Source <../files/lesson5_part1.v>`_
  - `Exercise sheet <../files/tp5.v>`_
  - `Exercise sheet solutions <tp5c.html>`_
  - `Self evaluation <self_eval5.html>`_

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

.. default-role:: coq

.. contents:: Table of Contents
   :depth: 2
   :local:

The goal of this lecture is to:
  - Understand more about universes in Rocq, i.e. about `Type` and `Prop`.
    This is helpful to decipher certain error messages that occasionally occur
    in practical developments.
  - Understand how induction principles are implemented and use this knowledge
    to implement induction principles for inductive types where Rocq's automated
    generation is too weak.

..
|*)

From Stdlib Require Import Arith Lia List.
Import ListNotations.

(*|
^^^^^^^^^
Universes
^^^^^^^^^

We have already seen `Type` and `Prop`.
They are what we call *universes*: they are types of types.

.. note::

  Sometimes people talk about *sorts* to mean universes, but the terminology is
  currently shifting towards only using *universe*, and to reserve *sort* for
  the part without the universe level.

You have seen that seemingly `Type : Type`:
|*)

Check (Type : Type).

(*|
But also that `Type` is actually a hierarchy of universes `Type@{i}`
in order to avoid inconsistencies with `Type : Type`, which becomes visible
once universe printing is enabled.
|*)

Set Printing Universes.

Check (Type : Type).

(*|
Below we will see more about the typing rules of `Type`, in particular a reminder
of how the typing rule of `forall` works.

We use the section mechanism which allows us to declare universe levels and so
on.
|*)

Section Universes.

(*|
Command `Universes` declares universe levels, while `Constraint` lets us
add (in)equalities between them.
Below we declare levels `i` and `j` together with constraint `i < j`.
We can see that `Type@{i}` is of type `Type@{j}` but not the converse.
|*)

  Universes i j.
  Constraint i < j.
  Check Type@{i} : Type@{j}.
  Fail Check Type@{j} : Type@{i}.

(*|
Here is the corresponding typing rule:

.. math::

   \cfrac{i < j}
    {\Gamma \vdash \mathsf{Type}_i : \mathsf{Type}_j}

^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Universe of a `∀` quantifier
^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Let us now have a look at the type of a `forall` in Rocq.
For this we're going to use another feature of the section mechanism: the
`Context` command allows us to add assumptions in our context, similar to
assumptions for a lemma.
|*)

  Universe k.

  Context (A : Type@{i}) (B : Type@{k}).

(*|
As you can see below, the type of a `forall` is the maximum of the types of
the domain and codomain.
See what it means for a `forall` containing `Type`.
|*)

  Check forall (a : A), B.

  Check forall (X : Type@{i}), Type@{k}.

(*|
.. warning::

  It's a very common mistake to confuse the level of the domain with the level
  of its type, even for experts.

The universal quantifier is often called Π-type (because it's a product in
some sense), especially when we are talking about types and not propositions.
The corresponding typing rule is given below.

.. math::

   \cfrac{
      \Gamma \vdash A : \mathsf{Type}_i
      \quad
      \Gamma, x : A \vdash B : \mathsf{Type}_j
    }
    {\Gamma \vdash \Pi (x : A). B : \mathsf{Type}_{\max(i,j)}}

^^^^^^^^^^^^
Cumulativity
^^^^^^^^^^^^

By the way, above, we've just seen a use of so-called *cumulativity* which says
that `Type@{i}` lives in `Type@{j}` for any `j` that's bigger than `i`.
By contrast, in Agda or Lean, we have unique typing and thus
`Type@{i}` is of type `Type@{i+1}` and that's it.

.. note::

  In those systems, cumulativity is regained differently, by means of so-called
  *lifting* operators that have type `Type@{i} -> Type@{j}` for `i ≤ j`.
  This complicates things a bit for end users who have to deal with those
  manually, but in exchange part of the meta-theory becomes simpler.
  We're happy to take questions about this online.

Cumulativity is actually more than that. It is in fact a form of subtyping that
says that `Type@{i}` is a subtype of `Type@{j}` whenever `i ≤ j`.

See how `A : Type@{i}` also lives in `Type@{j}` but how the converse
wouldn't work.
|*)

  Check (A : Type@{j}).

  Context (C : Type@{j}).

  Fail Check (C : Type@{i}).

(*|
`Prop`, on the other hand, lives in `Type@{i}` for all `i`.
|*)

  Check (Prop : Type@{i}).

(*|
Here you see Rocq mentions a constraint that `Set < i`.
There is indeed a third kind of universe which we did not mention but you have
probably seen already. It's called `Set`. You can think of it as the lowest
`Type` universe: `Type@{0}`, but in Rocq it's actually `Type@{Set}`
because the universe levels (`i`, `j`, `k` etc.) are not natural numbers
but abstract variables with constraints like the one we added above.

`Set` is the smallest `Type` and it is the only one which does not contain
`Prop`.
We do have cumulativity going from `Prop` to `Set` and `Type` however.

We give a summary below, where `i` is universally quantified.

.. code-block:: coq

  Prop     : Type@{i}
  Set      : Type@{i}
  Prop     ≤ Type@{i}
  Set      ≤ Type@{i}
  Type@{i} : Type@{i+1}
  Type@{i} ≤ Type@{i+1}

See how it goes in practice:
|*)

  Fail Check (Prop : Set).
  Fail Check (Prop : Type@{Set}).

  Variable (P : Prop).

  Check (P : Type@{i}).
  Check (P : Set).

(*|
We rephrase what we just said using inference rules.

.. math::

   \cfrac{}{\Gamma \vdash \mathsf{Prop} : \mathsf{Type}_{i}}
   \qquad
   \cfrac{}{\Gamma \vdash \mathsf{Set} : \mathsf{Type}_{i}}
   \qquad
   \cfrac{i < j}{\Gamma \vdash \mathsf{Type}_i : \mathsf{Type}_j}

.. math::

   \cfrac{}{\Gamma \vdash \mathsf{Prop} \le \mathsf{Type}_i}
   \qquad
   \cfrac{}{\Gamma \vdash \mathsf{Set} \le \mathsf{Type}_i}
   \qquad
   \cfrac{i \le j}{\Gamma \vdash \mathsf{Type}_i \le \mathsf{Type}_j}

We also have a subsumption rule below, where :math:`s` and :math:`s'` are two
universes.

.. math::

   \cfrac{\Gamma \vdash A : s \quad \Gamma \vdash s \le s'}{\Gamma \vdash A : s'}

.. note::

  There is actually another sort of universe called `SProp` standing for
  *strict propositions*. It's a bit more restrictive than `Prop` because it
  comes with so-called *definitional proof irrelevance*: for any `P : SProp`
  and `u : P` and `v : P`, then `u` and `v` are indistinguishable for Rocq.
  We won't be using it much in this course, but know it exists.

^^^^^^^^^^^^^^^
Impredicativity
^^^^^^^^^^^^^^^

`Prop` has other particularities. When considering a `forall` that ends in a
proposition, then the whole `forall` stays a proposition.
This means that things like `forall (n : nat), n = n` or
`forall (P : Prop), P` are propositions.
This property is called *impredicativity* because things like
`forall (P : Prop), P` are actually quantifying over themselves (`P` can
be instantiated with `forall (P : Prop), P`).

This is another big difference with Agda which is predicative instead.
To remedy this they have to also add universe levels to `Prop` like
`Prop@{i}`.
But in practice, most people only use `Type` (which they call `Set`) in Agda.
Lean on the other hand does things the same way as Rocq. In fact,
impredicativity is very strong and necessary to achieve the full power of ZFC.

In Rocq, the universe of a `forall` ending in a proposition is always a
proposition, regardless of the size of what we quantify over.
This comes from the intuition (and models) that `Prop` is proof-irrelevant:
all propositions are morally either empty (`False`) or contain only one
element (`True`) so `Prop` can be seen (modelled) as a set with two elements
so it is always small.

The commands below illustrate all we just said.
|*)

  Fail Check (Prop : Prop).

  Check forall (P : Prop), P.
  Check forall (n : nat), n = n.

  Variable (Q : A -> Prop).

  Check forall (x : A), Q x.

  Check forall (X : Type@{j}), P.

  Unset Printing Universes.

End Universes.

(*|
Here is the inference rule for a Prop-valued Π-type.

.. math::

   \cfrac{
      \Gamma \vdash A : \mathsf{Type}_i
      \quad
      \Gamma, x : A \vdash B : \mathsf{Prop}
    }
    {\Gamma \vdash \Pi (x : A). B : \mathsf{Prop}}

^^^^^^^^^^^^^^^^^^^^^^^^
Elimination restrictions
^^^^^^^^^^^^^^^^^^^^^^^^

Universes are also important when defining inductive types.
You may wonder when to put your type in `Prop` or in `Type`.
We have seen several examples: things like disjunction and conjunction are
placed in `Prop`, but `bool` is a `Type` for instance.

Things that weigh in a choice are intent of course, but also the fact that
`Prop` is impredicative (as seen above), but also that `Prop` can be
axiomatically assumed to be *proof irrelevant*.
Proof irrelevance is expressed as follows.
|*)

Definition PI :=
  forall (P : Prop) (p q : P), p = q.

(*|
It states that any two proofs of a given proposition are always equal.
In other words, `PI` being consistent means that proofs cannot impact
computation in a meaningful way.
That is, we cannot analyse a proof to build a function that is supposed to
compute a Boolean.

Consider a variant of `bool` in `Prop` below.
|*)

Inductive prop_bool : Prop :=
| ptrue
| pfalse.

(*|
As long as we remain in `Prop`, we can do pretty much the same as before.
|*)

Definition pneg (b : prop_bool) : prop_bool :=
  match b with
  | ptrue => pfalse
  | pfalse => ptrue
  end.

Lemma pneg_invol :
  forall b, pneg (pneg b) = b.
Proof.
  intros []. all: reflexivity.
Qed.

(*| We can also map the usual Booleans into them. |*)

Definition to_prop_bool (b : bool) : prop_bool :=
  if b then ptrue else pfalse.

(*|
But, *crucially*, we can't do the converse!
|*)

Fail Definition to_bool (b : prop_bool) : bool :=
  match b with
  | ptrue => true
  | pfalse => false
  end.

(*|
Rocq complains that proofs can only be eliminated to build other proofs.
The same happens in proof mode of course.
|*)

Lemma to_bool : prop_bool -> bool.
Proof.
  intro b. Fail destruct b.
Abort.

(*| We can instead prove something weaker like this: |*)

Lemma to_bool :
  forall (p : prop_bool),
    exists (b : bool), to_prop_bool b = p.
Proof.
  intros [].
  - exists true. reflexivity.
  - exists false. reflexivity.
Qed.

(*|
We can however not prove that there is a **function** inverting
`to_prop_bool` because this would be inconsistent with `PI`:
|*)

Lemma to_bool_function_not_PI (f : prop_bool -> bool) :
  (forall b, f (to_prop_bool b) = b) -> ~ PI.
Proof.
  intros H pi.
  specialize (pi prop_bool ptrue pfalse).
  specialize (H true) as e1.
  specialize (H false) as e2.
  simpl in *.
  rewrite pi in e1.
  congruence.
Qed.

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Booleans in Prop</summary>

..
|*)

(*|
.. important::

  This exercise is having you redo exactly what is in the lecture notes.
  Try to forget about the answer for a minute and come up with the answer
  yourself.

Define a copy of Booleans called `boolp` that lives in `Prop`.
Show that you can go from `bool` to `boolp`.
Can you do the converse? Why?
What would a surjective function from `boolp` to `bool` mean for
proof irrelevance? (We want to see a proof.)
|*)

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Surjectivity</summary>

..
|*)

(*|
Prove that for all `p : boolp`, there exists some `b : bool` such that
its mapping to `boolp` is equal to `p`.
|*)

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Existential quantifier and Σ types</summary>

..
|*)

(*|
`exists (x : A), P x` and `{ x : A | P x }` are two very similar types but
the former lives in `Prop` while the latter is in `Type`.
Show how one implies the other.
Why is the other implication not provable?
|*)

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. important::

  The proof irrelevance argument is *not* the reason why elimination from `Prop`
  to `Type` isn't allowed!
  It would be one unfortunate consequence, but there is a bigger problem:
  it would also lead to an inconsistency. More on this later.

|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Disjunction and sum</summary>

..
|*)

(*|
`P \/ Q` and `A + B` are also similar types. The first you know as
disjunction of propositions, the other one is relevant data that contains either
a value of type `A`, or a value of type `B`.

Prove that `P + Q -> P \/ Q`, ideally with a proof term.

Why is the other implication not provable?
|*)

Locate "+".
Print sum.

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Existential quantifier on Booleans</summary>

..
|*)

(*|
We can't show that `(exists x, P x) -> { x : A | P x }` in general, but we can
when `A` is `bool` and when `P x` is of the form `f x = true`. Show it.
|*)

(*|
.. raw:: html

   </details>

..
|*)

(*|
^^^^^^^^^^^^^^^^^^^^^^
Subsingleton criterion
^^^^^^^^^^^^^^^^^^^^^^

There are crucial exceptions to the rule that forbids elimination from `Prop`:
If a type has **at most one constructor** and **all the non-parameter
arguments of the constructor are proofs**, then such eliminations are allowed.

This property is called the *(sub)singleton criterion* because it essentially
says that you can inspect (as in case analysis) a proof, as long as there can be
at most one such proof. So a term that depends on it doesn't really depend on
it in the end, but merely on the fact that there exists a proof.

It is thanks to this property that we can eliminate a proof of `False` to
produce anything else.
|*)

Goal False -> nat.
Proof.
  intro bot. destruct bot.
Qed.

Definition exfalso' {A : Type} (bot : False) : A :=
  match bot with end.

(*|
It also works with `True`, but it's not so interesting.
We leave it to you as an exercise.
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: True is a singleton</summary>

..
|*)

(*|
Show that, for any `P : True -> Type`, it is enough to prove `P I` to prove any
`P p`. Try to do it with a proof term and explain why it is allowed.
|*)

(*|
.. raw:: html

   </details>

..
|*)

(*|
Another more interesting case is equality. This is what lets you use tactics
such as `rewrite` on any type.
|*)

Goal forall n m (P : nat -> Type), P (n + m) -> P (m + n).
Proof.
  intros n m P x.
  rewrite Nat.add_comm. assumption.
Qed.

(*|
The above we can do in general:
|*)

Goal forall {A} (P : A -> Type) {u v} (e : u = v) (t : P u), P v.
Proof.
  intros A P u v e.
  rewrite e. auto.
Qed.

(*|
Disjunction for instance does not fall under the criterion:
|*)

Goal forall P Q, P \/ Q -> bool.
Proof.
  intros P Q h.
  Fail destruct h.
Abort.

(*|
We could try to *cheat* by boxing a proposition so it only has one constructor
but it doesn't actually help.
|*)

Inductive Box (P : Prop) : Prop :=
| box (p : P).

Goal forall P Q, Box (P \/ Q) -> bool.
Proof.
  intros P Q h.
  destruct h.
  Fail destruct h.
Abort.

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Ex falso</summary>

..
|*)

(*|
Write a term that goes from `False` to any `A : Type`.
Explain why this term is allowed.
|*)

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Conjunction</summary>

..
|*)

(*|
We have seen above that disjunction did not satisfy the subsingleton criterion.
What about conjunction?
State the equivalence between `P * Q` and `P /\ Q`.
Either give a proof script that fails because conjunction does not satisfy
the subsingleton criterion, or give a proof script that works because it does.
Explain why it satisfies it or not.
|*)

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Singleton version of <code class="coq highlight">le</code></summary>

..
|*)

(*|
Propose a version of `le` that satisfies the singleton criterion
(in particular, make sure it is defined in `Prop`).
You can use the goal below with `le` (`<=`) and with your `le'`.
It should only work with `le'`.
Is it satisfying? If not you can try and think if you can't define one
(perhaps not with the `Inductive` keyword) that works a bit better.
Be warned: you probably won't be satisfied either.
|*)

Goal forall n m, n <= m -> nat.
Proof.
  intros n m h.
  Fail destruct h.
Abort.

(*|
.. raw:: html

   </details>

..
|*)

(*|
^^^^^^^^^^^^^^^^^^^^
Induction principles
^^^^^^^^^^^^^^^^^^^^

Let us now move to induction principles.
For this, we'll have a look at trees again.

We can easily define binary trees (with labels in `A`) as follows.
|*)

Inductive bintree A :=
| bt_leaf (a : A)
| bt_node (a : A) (l r : bintree A).

Arguments bt_leaf {A}.
Arguments bt_node {A}.

(*|
As for every inductive type, Rocq generates induction principles corresponding
to the various sorts:

- `bintree_ind` for `Prop`,
- `bintree_rect` for `Type`,
- `bintree_rec` for `Set` (but you can ignore it and use `bintree_rect`).

.. note::

  Here we use *sort* and not *universe* because it refers to the part without
  the universe level, so `Type` and not `Type@{i}`.

They only vary in the return type of the *motive* (the return predicate).
|*)

Check bintree_rect.

(*|
Now consider the following map function on `bintree`.
|*)

Fixpoint bt_map {A B} (f : A -> B) (t : bintree A) : bintree B :=
  match t with
  | bt_leaf a => bt_leaf (f a)
  | bt_node a l r => bt_node (f a) (bt_map f l) (bt_map f r)
  end.

(*|
When proving properties about it, we will use the `induction` tactic which
picks up the corresponding induction principle, below `bintree_ind`, and applies
it for us.
|*)

Lemma bt_map_id :
  forall A (t : bintree A),
    bt_map (fun x => x) t = t.
Proof.
  intros A t.
  induction t as [a | a l ihl r ihr].
  - reflexivity.
  - cbn. rewrite ihl, ihr. reflexivity.
Qed.

(*|
If you print the term, you will see that it indeed starts with an application of
`bintree_ind`. No need to read the rest for now.
|*)
Print bt_map_id.

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Binary trees</summary>

..
|*)

(*|
Define an inductive type `bintree'` for binary trees.
Write down both type and term for `bintree_rect'` (the induction principle
with `Type`-valued motive) manually.
|*)

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Map on binary trees</summary>

..
|*)

(*|
Define a map function for it, and show mapping with the identity results in
the identity on binary trees.
|*)

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Induction principle for indexed type</summary>

..
|*)

(*|
Define an inductive type `dtree A : nat -> Type` for binary trees indexed by
their depth. State and prove (with a term) its `Type`-valued induction
principle.

.. caution::

  Do not define balanced trees by mistake.

..
|*)

(*|
.. raw:: html

   </details>

..
|*)

(*|

Nested induction principles
---------------------------

We have seen in `week 3 <lesson3_part1.html#recursors>`_ that nested inductive
types required special care, because by default, Rocq generates the wrong
induction principle.
Since Rocq 9.2 — the version we are currently using — the situation changed
slightly.
In fact, if you define a nested inductive type like `tree` you will see a bunch
of warnings appearing (in fact, it's many times the same warning, who knows
why 🤷).
|*)

Inductive mytree A :=
| mynode (a : A) (children : list (mytree A)).

(*|
The warning tells you that no "scheme" for `list` is registered as `All`.
Since the warning is so insistent, let us follow its advice.
|*)

Scheme All for list.

(*|
This defines a new inductive type called `list_all` that is a bit like `Forall`:
|*)

Print list_all.

(*|
It is important to note: this is not literally `Forall`, in particular you will
see the surprising `Type@{α ; _}` used in the type of `PA`.
It also appears in the name: `list_all@{α ; u u0}`.
Let us analyse what this all means before going forward:

`u` and `u0` are *universe level* variables, as we have seen in this chapter
already.

.. tip::

  If you write `Set Printing Universes.` before the `Print` you will see the
  underscore `_` replaced by `u0` actually.

`α` on the other hand is a *sort* variable. It can be instantiated by `Prop` or
by `Type` typically.
So for instance `Type@{Type ; i}` is the same as `Type@{i}`, while
`Type@{Prop ; i}` is just `Prop`.
This feature is relatively new in Rocq, so notations and general support might be
a bit rough for now; it should get better with newer releases of Rocq.

If we rephrase, `list_all` is like `Forall` but defined generically to work
with `Prop` or `Type` depending on what is needed.
Now that it is defined, Rocq no longer warns us about nesting `list` in our
inductive definition:

|*)

Inductive tree A :=
| node (a : A) (children : list (tree A)).

Arguments node {A}.

(*|
If we look at the induction principle, it now uses `list_all` which gives us
something strong enough to prove things about `tree`.
|*)

Check tree_rect.

(*|
Let's see it in action, by defining a map function and then proving things about
it.
|*)

Fixpoint tree_map {A B} (f : A -> B) (t : tree A) : tree B :=
  match t with
  | node a l => node (f a) (map (tree_map f) l)
  end.

Lemma tree_map_id A (t : tree A) :
  tree_map (fun x => x) t = t.
Proof.
  induction t as [a l ih].
  cbn. f_equal.
Abort.

(*|
We'll stop here, but, compared to last time, the induction principle is enough
to conclude. We'll leave it as an exercise for you.
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Using <code class="coq highlight">list_all</code></summary>

..
|*)

(*|
Prove the following lemma.
|*)

Lemma tree_map_id A (t : tree A) :
  tree_map (fun x => x) t = t.
Proof.
Admitted.

(*|
.. raw:: html

   </details>

..
|*)

(*|
Another valid approach is to define `tree_map_id` directly using `Fixpoint`.
We can in fact do this directly using proof mode (with tactics).
Let's see it in action.
|*)

Fixpoint tree_map_id_fix A (t : tree A) {struct t} :
  tree_map (fun x => x) t = t.
Proof.
  destruct t.
  cbn. f_equal.
  erewrite map_ext.
  - apply map_id.
  - cbn. intros x. apply tree_map_id_fix.
Fail Qed.
Abort.

(*|
`Qed` fails here because Rocq cannot see our fixpoint terminates.
Indeed, we used a recursive call on something completely unrelated.
We are only told now because Rocq only checks for termination at `Qed`
time, and not before.
There is a way to know beforehand though: the `Guarded` command checks that
the guard condition (which verifies termination) holds up to the point where
it's called.
|*)

Fixpoint tree_map_id_fix A (t : tree A) {struct t} :
  tree_map (fun x => x) t = t.
Proof.
  destruct t.
  cbn. f_equal.
  Guarded.
  erewrite map_ext_in.
  - apply map_id.
  - Guarded. cbn. intros x h. Guarded. apply tree_map_id_fix.
  Fail Guarded.
Fail Qed.
Abort.

(*|
This time it should actually work because morally we only use recursive
calls on elements *inside* the list, but Rocq doesn't know it.

We in fact need to be able to recurse on the list, so the same way we nested
inductive types, we need to nest fixpoints.
For this we can use the `fix` tactic which introduces a fixed point.
We need to `revert` the argument on which we want to recurse (to put it back
into the goal) and then `fix aux 1` will introduce a new hypothesis named
`aux` corresponding to potential recursive calls.
|*)

Fixpoint tree_map_id_fix A (t : tree A) {struct t} :
  tree_map (fun x => x) t = t.
Proof.
  destruct t.
  cbn. f_equal.
  revert children. fix aux 1. intro l.
  destruct l as [| x l].
  - reflexivity.
  - cbn. f_equal.
    + apply tree_map_id_fix.
    + apply aux.
Qed.

(*|
This was rather painful because we had to manually ensure that Rocq recognises
the proof as structurally recursive.

The version from earlier using `list_all` wasn't so bad right? 😸
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Nested induction principle by hand</summary>

..
|*)

(*|
You already had an exercise about defining a nice induction principle for `tree`
using `Forall` (which is the special case of `list_all` for `Prop`-valued
predicates).
To switch things up we'll be using a different method, using `In`.

State and prove the induction principle for `tree` called `tree_ind_in`.
You will likely have to use the `fix` tactic, and probably the `revert` tactic
to generalise the goal (`revert x` is basically the opposite of `intro x`).
|*)

(*|
You can add `using tree_ind_in` to an `induction` command to instruct Rocq to
use your custom induction principle instead.
Use it to prove the following.

.. tip::

  You may use the `Search` command to find out about useful lemmas in this
  situation. For instance `Search map In.` will find lemmas that mention both
  `map` and `In`.

..
|*)

Lemma tree_map_id_again A (t : tree A) :
  tree_map (fun x => x) t = t.
Proof.
Admitted.

(*|
.. raw:: html

   </details>

..
|*)

(*|
^^^^^^^^^^^^^^
Size recursion
^^^^^^^^^^^^^^

In pen-and-paper proofs, you often see people perform induction on the size of
objects, or alternatively with a measure.
We can do this generically for any type `X` which has a `size : X -> nat`
function.
|*)

Lemma size_recursion (X : Type) (size : X -> nat) (P : X -> Type) :
  (forall x, (forall y, size y < size x -> P y) -> P x) ->
  forall x, P x.
Proof.
  intros D x. apply D.
  cut (forall n y, size y < n -> P y).
  { eauto. }
  clear x. intros n y E.
  induction n as [| n ih] in y, E |- *. 1: lia.
  apply D. intros x F. apply ih. lia.
Defined.

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Strong induction on natural numbers</summary>

..
|*)

(*|
We have seen strong induction on `nat` already, but show it again and use it to
prove the following lemma that corresponds to induction on natural numbers with
access to the two previous cases.
|*)

Lemma nat_ind_2 :
  forall (P : nat -> Prop),
    P 0 ->
    P 1 ->
    (forall n, P n -> P (S n) -> P (S (S n))) ->
    forall n, P n.
Proof.
Admitted.

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Fibonacci</summary>

..
|*)

(*|
Use the `induction` tactic with `nat_ind_2` to prove that the Fibonacci
sequence is always above its index (`n <= fib n`).
|*)

Fixpoint fib n :=
  match n with
  | 0 => 1
  | 1 => 1
  | S (S n as m) => fib n + fib m
  end.

(*|
.. raw:: html

   </details>

..
|*)

(*|
^^^^^^^^^^^^^^^^^^^^^^
Well-founded induction
^^^^^^^^^^^^^^^^^^^^^^

The last topic is about doing induction / recursion along *any* well-founded
order.
We define well-foundedness of an order on a point as the so-called
*accessibility predicate*.

We do it inside a module to avoid overriding the definition from the standard
library.
|*)

Module Acc.

Section Well_founded.

(*|
We work with a type and a relation on it.

.. note::

  We do not require this relation to be an equivalence relation or
  anything actually. This isn't necessary.

..
|*)

  Context {A : Type}.
  Context (R : A -> A -> Prop).

(*|
A point `x` is *accessible* when all its predecessors in the relation are
accessible as well.
|*)

  Inductive Acc (x : A) : Prop :=
    Acc_intro : (forall y, R y x -> Acc y) -> Acc x.

(*|
Since the inductive type has exactly one constructor, we can show this is a
(logical) equivalence.
|*)

  Fact Acc_iff x :
    Acc x <-> forall y, R y x -> Acc y.
  Proof.
    split.
    - intros [h]. exact h.
    - intros. constructor. assumption.
  Qed.

End Well_founded.

End Acc.

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: No infinite decreasing sequence</summary>

..
|*)

(*|
You might be surprised that our definition of well-foundedness isn't talking
about the absence of infinite decreasing sequences.
While that is the usual definition, in our setting such a definition doesn't
let us *construct* terms in general, so it is better to have a positive outlook
on well-foundedness.

We can still connect the two though!
Prove the following lemmas.
|*)

Section Sequences.

  Context (A : Type) (R : A -> A -> Prop).

  Definition noseq_from x :=
    ~ (exists (u : nat -> A), u 0 = x /\ forall n, R (u (S n)) (u n)).

  Lemma wf_noseq x :
    Acc R x -> noseq_from x.
  Proof.
  Admitted.

(*|
.. tip::

  The other direction is also interesting, but it requires classical logic
  stronger than the law of excluded middle. You will actually need dependent
  choice. This is a quite advanced exercise, but you may do it if you are
  interested. Talk to us if you need help getting started.

..
|*)

End Sequences.

(*|
.. raw:: html

   </details>

..
|*)

(*|
Now behold the return of the subsingleton criterion! `Acc` indeed verifies it:
it has exactly one constructor `Acc_intro` which itself has two arguments,
`x : A` and `h : forall y, R y x -> Acc y`. The first one is a (non-uniform)
parameter so it doesn't count, and the second one is a proof (because, remember,
∀ quantifiers ending in `Prop` land in `Prop` as well).

This means that we get an induction principle with a motive in `Type`:
|*)

Check Acc_rect.

(*|
It says that when proving `P x` for accessible `x`, one can assume `P y`
for any `R`-smaller `y`.
|*)

(*| We can prove that accessible points are not contained in loops: |*)
Fact exercise_loop (X : Type) (R : X -> X -> Prop) x :
  Acc R x ->
  ~ exists y, R x y /\ R y x.
Proof.
  intros H.
  induction H as [x H ih].
  firstorder.
Qed.

(*|
To conclude this lecture, we give a proof that one can use recursion on proofs
to write a function that *extracts* the witness from a proof of
`exists n, f n = true`.
This proof can be given in different ways.
We show the easiest approach here, and leave a variant using `Acc` as
an exercise.
|*)

From Stdlib Require Import Lia.

(*|
We start by giving a predicate `least P n k` that says that `k` is the least
natural number above `n` that verifies predicate `P`.
|*)

Definition least P n k :=
  n <= k /\
  P k /\
  forall i, n <= i -> P i -> k <= i.

Section WO.

  Context (f : nat -> bool).

(*|
The key is in the definition of a guardedness predicate which is in `Prop`
(so we can eliminate `exist` into it) and which verifies the subsingleton
criterion (so we can eliminate it into `Type`).
|*)
  Inductive G (n : nat) : Prop :=
  | GI : (f n = false -> G (S n)) -> G n.

  Lemma G_sig n :
    G n ->
    { k | least (fun k => f k = true) n k }.
  Proof.
    induction 1 as [n _ ih].
    destruct (f n) eqn:e.
    - exists n. unfold least. eauto.
    - destruct (ih eq_refl) as (k & hle & hk & hleast).
      exists k. split. 2: split.
      + lia.
      + assumption.
      + intros i hi. inversion hi.
        * congruence.
        * eapply hleast. lia.
  Defined.

  Lemma G_zero n :
    G n -> G 0.
  Proof.
    induction n as [|n ih].
    - auto.
    - intros h. apply ih.
      constructor. auto.
  Defined.

  Theorem linear_search :
    (exists n, f n = true) ->
    { n | least (fun n => f n = true) 0 n }.
  Proof.
    intros h.
    apply (G_sig 0).
    destruct h as [n h].
    apply (G_zero n).
    constructor. rewrite h. discriminate.
  Defined.

End WO.

About linear_search.

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Search using Acc</summary>

..
|*)

(*|
We are going to show that for any decidable predicate `P` with
`exists n, P n` we can compute a natural number `n` for which `P` holds,
*i.e.* deduce `{ n | P n }`.

Prove the admitted lemmas below.
|*)

Section ConstructiveIndefiniteGroundDescription_Acc.

  Context (P : nat -> Prop).

  Hypothesis P_decidable : forall n : nat, {P n} + {~ P n}.

  Let R (x y : nat) : Prop := x = S y /\ ~ P y.

  Local Abbreviation acc x := (Acc R x).

  Lemma P_implies_acc : forall x : nat, P x -> acc x.
  Proof.
  Admitted.

  Lemma P_eventually_implies_acc : forall (x : nat) (n : nat), P (n + x) -> acc x.
  Proof.
  Admitted.

  Corollary P_eventually_implies_acc_ex : (exists n : nat, P n) -> acc 0.
  Proof.
  Admitted.

  Theorem acc_implies_P_eventually : acc 0 -> {n : nat | P n}.
  Proof.
    intros Acc_0. pattern 0.
    induction Acc_0 as [x H IH].
    (* now use decidability of P *)
  Admitted.

  Theorem constructive_indefinite_ground_description_nat_Acc :
    (exists n : nat, P n) -> {n : nat | P n}.
  Proof.
  Admitted.

End ConstructiveIndefiniteGroundDescription_Acc.

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Defining functions by well-founded recursion</summary>

..
|*)

(*|
We have seen well-founded induction, but sometimes we also want to define
functions by well-founded recursion.
The standard library comes with a helpful function for doing that called
`Fix_F`. It performs induction on accessibility like we have been doing.
|*)

About Fix_F.

(*|
Implement a `merge` function on lists such that if `l` and `r` are
individually sorted, then `merge l r` should be sorted too.
This function is the main ingredient for the merge sort algorithm.

We give you the version one would write in OCaml and you have to adapt it into
a function accepted by Rocq.
We're using lists of natural numbers to make it simpler but it could be
generalised of course.

.. tip::

  You may have to pack arguments together to make it work.

Next, prove a specification for `merge` that ensures it preserves sortedness
and that the result is a permutation of the original lists. You can use a
weak version of permutation that doesn't account for multiplicity.

We give you some lemmas about `sorted` and `wpermut` that you may or may not
use.
This is so you don't waste too much time on those. We expect you to begin
by admitting them, but you should be able to prove them.

.. tip::

  If you want to do induction on `Acc`, you had better prove a stronger
  induction principle for it because the one generated isn't enough.

..
|*)

From Stdlib Require Import RelationClasses.

Fail Fixpoint merge (l r : list nat) : list nat :=
  match l, r with
  | [], r => r
  | l, [] => l
  | x :: l, y :: r =>
    if x <? y
    then x :: merge l (y :: r)
    else y :: merge (x :: l) r
  end.

Inductive sorted : list nat -> Prop :=
| sorted_nil : sorted []
| sorted_cons : forall x l, sorted l -> Forall (le x) l -> sorted (x :: l).

Definition wpermut (l r : list nat) : Prop :=
  forall x, In x l <-> In x r.

#[export] Instance wpermut_refl : Reflexive wpermut.
Proof.
Admitted.

#[export] Instance wpermut_sym : Symmetric wpermut.
Proof.
Admitted.

#[export] Instance wpermut_trans : Transitive wpermut.
Proof.
Admitted.

Add Parametric Relation : (list nat) wpermut as wpermut_rel.

Lemma Forall_wpermut :
  forall P l r,
    wpermut l r ->
    Forall P r ->
    Forall P l.
Proof.
Admitted.

Lemma wpermut_cons :
  forall x l r,
    wpermut l r ->
    wpermut (x :: l) (x :: r).
Proof.
Admitted.

Lemma wpermut_app :
  forall l r,
    wpermut (l ++ r) (r ++ l).
Proof.
Admitted.

Lemma sorted_cons_inv :
  forall x l,
    sorted (x :: l) ->
    sorted l /\ Forall (le x) l.
Proof.
Admitted.

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Hilbert's epsilon (advanced)</summary>

..
|*)

(*|
We're going to show the Bishop-Diaconescu-Myhill-Goodman theorem.
It shows that the axiom of choice implies excluded middle with sufficient
extensionality.

There are several versions of the axiom of choice.
One is Hilbert's epsilon operator which takes a property on a type, and
returns an element of that type that verifies the property if such an element
exists. To avoid inconsistencies, we have to restrict this operator to
inhabited types.
|*)

Section Hilbert.

(*|
`inhabited A` is just a proposition from which you cannot extract the witness.
|*)
  Context (epsilon : forall A, inhabited A -> (A -> Prop) -> A).

(*|
If there is an element verifying the property, then the one `epsilon` gave us
also verifies it.
|*)
  Context (epsilon_spec :
    forall A i P,
      (exists x, P x) ->
      P (epsilon A i P)).

(*|
We also need some extensionality to tell us that the choice does not depend on
how the property was formulated.
|*)
  Context (epsilon_ext :
    forall A i P Q,
      (forall x, P x <-> Q x) ->
      epsilon A i P = epsilon A i Q
  ).

(*|
Prove the excluded middle.

.. tip::

  You can use `epsilon` with some property like `x = true \/ P` and the
  same with `false`.

..
|*)

End Hilbert.

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: From relation to function (advanced)</summary>

..
|*)

(*|
Another version of the axiom of choice says that from an entire relation,
one can extract a function. It's a form of inversion of quantifiers.
|*)

Definition fun_choice :=
  forall A B (R : A -> B -> Prop),
    (forall x, exists y, R x y) ->
    exists (f : A -> B),
      forall x, R x (f x).

(*|
Show that `fun_choice` implies LEM as well.
You may use proposition and function extensionality.

The proof should share some ideas with the one above and could involve some
function of type `{ p : bool -> Prop | p = B \/ p = C } -> bool`
with carefully chosen `B` and `C`. |*)

Definition FunExt :=
  forall A B (f g : A -> B),
    (forall x, f x = g x) ->
    f = g.

Definition PropExt :=
  forall (P Q : Prop), P <-> Q -> P = Q.

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Choice and proof irrelevance (advanced)</summary>

..
|*)

(*|
PI (`forall P : Prop, forall h1 h2 : P, h1 = h2`) suffices to prove that
choice implies `ELEM := forall A : Type, forall a b : A, a = b \/ ~ (a = b)`.

Prove this, and then deduce that `PropExt` suffices for Diaconescu's theorem,
*i.e.* that `FunExt` is not actually needed.
|*)

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Choice in SProp (advanced)</summary>

..
|*)

(*|
Read the documentation of `SProp` and see whether you can prove that choice
for `SProp` implies ELEM for `SProp` (without any additional assumption).

To make our life easier, we define how to squash a proposition into a strict
proposition.
|*)

Definition squash (P : Prop) : SProp :=
  forall S : SProp, (P -> S) -> S.

Lemma sq (P : Prop) :
  P -> squash P.
Proof.
  firstorder.
Qed.

(*| The statement. |*)
Definition fun_choice_SProp :=
  forall A B (R : A -> B -> Prop),
    (forall x, squash (exists y, R x y)) ->
    squash (exists (f : A -> B),
    forall x, R x (f x)).

(*| Auxiliary definition for the proof. |*)
Inductive sig {A : Type} (P : A -> SProp) : Type :=  exist : forall x : A, P x -> sig P.

Definition proj1_sig : forall [A : Type] [P : A -> SProp], sig P -> A.
Proof.
  intros A p [x]. exact x.
Defined.

(*|
.. raw:: html

   </details>

..
|*)

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Gallery of inductive types and corresponding induction principles
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

We do not believe giving you the recipe in general is going to be useful,
instead we think showing you representative examples together is going to be
more helpful. So here we go.

Lists
-----

Lists are an inductive type (`Type`) with one uniform parameter `A : Type`,
and two constructors `nil` and `cons`.
|*)

Inductive list (A : Type) : Type :=
| nil
| cons (a : A) (l : list A).

(*|
As it's a type, it can be eliminated to produce both `Type` and `Prop`,
hence we have the two following induction principles.
|*)

Check list_ind.
Check list_rect.

(*|
The *motive* is of the form `P : list A -> Type` or `P : list A -> Prop`.
Note that `A` is a uniform parameter so it is quantified before the motive,
which is why it can mention it.
The conclusion will then be `forall (l : list A), P l`.

The induction principle has two branches, one for `nil` and one for `cons`.
Because `nil : list A` the corresponding branch is `P nil`.
Because `cons : A -> list A -> list A` the corresponding branch is
`forall (a : A) (l : list A), P l -> P (cons a l)`.
To get it, you start from the type of the constructor, and for each *recursive*
invocation of `list A` you additionally get some induction hypothesis `P l`.
The return type `list A` is then replaced by `P (cons a l)`, *i.e.* the
motive applied to the constructor itself.
|*)



(*|
Evenness
--------

We have also seen the `even` predicate which is a *proposition* (`Prop`).
It takes no parameter, has one index `n : nat` and two constructors.
|*)

Inductive even : nat -> Prop :=
| evenO : even 0
| evenS (n : nat) : even n -> even (S (S n)).

(*|
Since it has two constructors, it doesn't satisfy the subsingleton criterion
and thus it produces only `even_ind` but no `even_rect`.

Since the sort is `Prop`, the motive will *not* depend on the proof of
`even n`, only on `n`, so it will be `P : nat -> Prop`.

Otherwise the recipe is the same, you just don't need to apply `P` to the
constructor, only to the value of the index, so in one branch `P 0` and in the
other `P (S (S n))`.
The conclusion will be `forall n, even n -> P n`.
Even if `P` doesn't talk about the proof of `even n`, it is still required.
|*)

Check even_ind.

(*|
Accessibility
-------------

`Acc` has three parameters: two uniform parameters `A` and `R` and one
non-uniform parameter `x` (it stays `x` in the conclusion, but in the
argument to `Acc_intro` it is instantiated by `y`). It has no index.

Because it has one constructor with only one non-parameter argument which
happens to be a proof (`forall y, R y x -> Acc A R y` has type `Prop`), it
satisfies the subsingleton criterion.
|*)

Inductive Acc' A (R : A -> A -> Prop) (x : A) :=
| Acc_intro' : (forall y, R y x -> Acc' A R y) -> Acc' A R x.

Check Acc'_ind.
Check Acc'_rect.
