(*|
============================================================
Exercise session 4 — Modelling and automation — Solutions
============================================================

:Authors: Yannick Forster, Théo Winterhalter
:Files:
  - `Source <../files/tp4c.v>`_
  - `Back to lesson <lesson4_part1.html>`_

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

.. default-role:: coq
|*)
Set Default Goal Selector "!".

Set Default Goal Selector "!".

(* From the lecture: *)

From Stdlib Require Import Lia List ZArith.
Import ListNotations.

Record prod' (A B : Type) := mkpair {
  fst' : A ;
  snd' : B
}.

Arguments mkpair {A B}.

Definition to_prod {A B} (p : prod' A B) : A * B :=
  match p with
  | mkpair a b => (a, b)
  end.

Arguments fst' {A B}.
Arguments snd' {A B}.

Definition to_prod_alt3 {A B} (p : prod' A B) : A * B :=
  (fst' p, snd' p).

(*|
^^^^^^^^^^^^^^^^^^^^^
Exercise: Projections
^^^^^^^^^^^^^^^^^^^^^
|*)

(*| Show that `to_prod` and `to_prod_alt3` produce the same result. |*)

Lemma to_prod_eq :
  forall A B (p : prod' A B),
    to_prod p = to_prod_alt3 p.
Proof.
  intros A B p.
  destruct p as [a b]. reflexivity.
Qed.

(* From the lecture: *)

Record monoid := {
  m_ty : Type ;
  m_ne : m_ty ;
  m_op : m_ty -> m_ty -> m_ty ;
  m_l_ne : forall x, m_op m_ne x = x ;
  m_r_ne : forall x, m_op x m_ne = x ;
  m_assoc : forall x y z, m_op (m_op x y) z = m_op x (m_op y z)
}.

Notation "a ** b" := (m_op _ a b) (at level 11, left associativity).

Lemma monoid_fact :
  forall (M : monoid) (x y : M.(m_ty)),
    x ** M.(m_ne) ** y = x ** y.
Proof.
  intros M x y.
  (*| More complicated than necessary of course |*)
  rewrite m_assoc. rewrite m_l_ne. reflexivity.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Groups as records
^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Define a record for groups, building on the record for monoids.
Then show that `monoid_fact` also holds in groups.
|*)

Check monoid_fact.

Record group := {
  g_mon : monoid ;
  g_inv : forall x : g_mon.(m_ty),
    exists y, x ** y = g_mon.(m_ne) /\ y ** x = g_mon.(m_ne)
}.

Lemma group_fact :
  forall (G : group) (x y : G.(g_mon).(m_ty)),
    x ** G.(g_mon).(m_ne) ** y = x ** y.
Proof.
  intros G x y.
  apply monoid_fact.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Lists form a monoid
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Show that lists form a monoid using `++` as operation.
How does `monoid_fact` translate to lists?
Note that, unlike `**` or `+`, `++` associates to the right,
meaning `x ++ y ++ z` stands for `x ++ (y ++ z)`.
|*)

Definition list_monoid (A : Type) : monoid.
Proof.
  refine {|
    m_ty := list A ;
    m_ne := [] ;
    m_op x y := x ++ y
  |}.
  - intro. simpl. reflexivity.
  - intro. rewrite app_nil_r. reflexivity.
  - intros. rewrite app_assoc. reflexivity.
Defined.

Lemma list_fact :
  forall A (x y : list A),
    (x ++ []) ++ y = x ++ y.
Proof.
  intros A x y.
  apply monoid_fact with (M := list_monoid A).
Qed.

(* From the lecture: *)

Class Monoid (A : Type) (neu : A) (op : A -> A -> A) := {
  mon_left_neutral : forall x, op neu x = x ;
  mon_right_neutral : forall x, op x neu = x ;
  mon_assoc : forall x y z, op (op x y) z = op x (op y z)
}.
#[export] Instance MonoidNat : Monoid nat 0 plus.
Proof.
  split.
  - intro. reflexivity.
  - intro. lia.
  - intros. lia.
Qed.
Lemma test_monoid :
  forall M neu op `{Monoid M neu op} k n m,
    op (op (op k n) m) neu = op k (op n m).
Proof.
  intros.
  rewrite mon_right_neutral.
  rewrite mon_assoc. reflexivity.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Product instance
^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*| Complete the product instance. |*)

#[export] Instance MonoidProd :
  forall A B na nb opa opb,
    Monoid A na opa ->
    Monoid B nb opb ->
    Monoid (A * B) (na,nb) (fun '(xa,xb) '(ya,yb) => (opa xa ya, opb xb yb)).
Proof.
  intros A B na nb opa opb MA MB.
  split.
  - intros [a b].
    rewrite mon_left_neutral with (x := a).
    rewrite mon_left_neutral with (x := b).
    reflexivity.
  - intros [a b].
    rewrite mon_right_neutral with (x := a).
    rewrite mon_right_neutral with (x := b).
    reflexivity.
  - intros [xa xb] [ya yb] [za zb].
    rewrite !mon_assoc. reflexivity.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Monoid instance for lists
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Define an instance for lists and apply `test_monoid` to it.
Then check that Rocq can now find a monoid structure on
`list bool * nat * list nat`.

.. tip::

  If asked for an instance of `Monoid`, you can always write `exact _`.
  It will trigger class resolution and find it automatically (if you have a
  corresponding instance).

..
|*)

Check test_monoid.

#[export] Instance MonoidList : forall A, Monoid (list A) [] (@app A).
Proof.
  intros A.
  split.
  - intro. reflexivity.
  - intro. apply app_nil_r.
  - intros. rewrite app_assoc. reflexivity.
Qed.

Lemma test_list :
  forall A (k n m : list A), ((k ++ n) ++ m) ++ [] = k ++ n ++ m.
Proof.
  intros. apply test_monoid.
  exact _.
Qed.

Definition bar : Monoid (list bool * nat * list nat) _ _ := _.

(* From the lecture: *)

Class Eq A := {
  eqb : A -> A -> bool ;
  eqb_iff : forall x y, eqb x y = true <-> x = y
}.

Fixpoint memb {A} `{Eq A} (x : A) (l : list A) : bool :=
  match l with
  | [] => false
  | y :: l => eqb x y || memb x l
  end.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Specification of memb
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Give `memb` a specification using the `In` predicate and show it correct with
respect to it.
|*)

Check memb.

Lemma memb_spec :
  forall A `(Eq A) (x : A) l,
    memb x l = true <-> In x l.
Proof.
  intros A hA x l.
  induction l as [| a l ih].
  - simpl. split.
    + discriminate.
    + intros [].
  - simpl. destruct (eqb x a) eqn: e.
    + simpl. apply eqb_iff in e. subst.
      split. 2: reflexivity.
      intro. left. reflexivity.
    + simpl. split.
      * intro. right. apply ih. assumption.
      * intros [bot | h].
        1:{
          symmetry in bot. apply eqb_iff in bot. rewrite bot in e. discriminate.
        }
        apply ih. assumption.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Groups as a class
^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Define a class of groups and show uniqueness of neutral and inverse for all
groups.

Apply this result to a group of your choosing (you will have to provide an
instance). To apply a lemma, sometimes `apply` is not enough.
In this case you can use `eapply` which is more permissive. It creates
existential variables (starting with a question mark) corresponding to values
it couldn't guess. They are typically resolved as you prove the various
goals.

Can you show that every group forms a monoid (again, provide a generic
instance)?
|*)

Class Group A (ne : A) (op : A -> A -> A) := {
  group_left_neutral : forall x, op ne x = x ;
  group_right_neutral : forall x, op x ne = x ;
  group_assoc : forall x y z, op (op x y) z = op x (op y z) ;
  group_inv : forall x, exists y, op x y = ne /\ op y x = ne
}.

Lemma group_neutral_unique :
  forall G ne op `{Group G ne op} ne',
    (forall x, op ne' x = x) ->
    (forall x, op x ne' = x) ->
    ne = ne'.
Proof.
  intros G ne op H ne' hl hr.
  specialize (hl ne). rewrite group_right_neutral in hl. subst.
  reflexivity.
Qed.

Lemma group_inverse_unique :
  forall G ne op `{Group G ne op} a b c,
    op a b = ne ->
    op b a = ne ->
    op a c = ne ->
    op c a = ne ->
    b = c.
Proof.
  intros G ne op H a b c hbr hbl hcr hcl.
  apply (f_equal (op c)) in hbr.
  rewrite <- group_assoc in hbr. rewrite hcl in hbr.
  rewrite group_left_neutral in hbr.
  rewrite group_right_neutral in hbr. assumption.
Qed.

#[export] Instance Group_Z : Group Z 0%Z Z.add.
Proof.
  constructor.
  - intro. lia.
  - intro. lia.
  - intros. lia.
  - intro x. exists (- x)%Z. lia.
Qed.

Lemma one_zero_Z :
  forall (z : Z),
    (forall i, z + i = i)%Z ->
    (forall i, i + z = i)%Z ->
    z = 0%Z.
Proof.
  intros z hl hr.
  symmetry.
  eapply group_neutral_unique. 1: exact _.
  all: assumption.
Qed.

#[export] Instance Monoid_Group :
  forall G ne op,
    Group G ne op ->
    Monoid G ne op.
Proof.
  intros G ne op H.
  constructor.
  - intro. apply group_left_neutral.
  - intro. apply group_right_neutral.
  - intros x y z. apply group_assoc.
Qed.

(* From the lecture: *)
Lemma In_hd :
  forall A (x : A) l,
    In x (x :: l).
Proof.
  intros A x l.
  simpl. auto.
Qed.

Lemma In_tl :
  forall A (x y : A) l,
    In x l ->
    In x (y :: l).
Proof.
  intros A x y l h.
  simpl. auto.
Qed.

Create HintDb indb.

#[export] Hint Resolve In_hd : indb.

#[export] Hint Resolve In_hd : core.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Extending the hint database
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Expand the database so that `auto with indb` is enough to solve the following
goals.

.. note::

  `Goal` is like `Lemma` but it doesn't require a name. You won't be able to
  reuse the proven goal afterwards, but it's useful to test things.

..

Recall the following lemmas from the lecture.
|*)

Check In_hd.
Check In_tl.

#[export] Hint Resolve In_tl : indb.

Goal forall A (x a b c d : A) l,
  In x l ->
  In x (a :: b :: c :: d :: l).
Proof.
  auto with indb.
Qed.

Goal forall A (x a b c d : A) l,
  In x (a :: b :: x :: c :: d :: l).
Proof.
  auto with indb.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Membership in concatenations
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Show that `In x l` implies `In x (l ++ r)` and that `In x r` implies
`In x (l ++ r)`.

Now add both lemmas to `indb`. For the first time, we are introducing a choice
for `auto`: presented with the goal `In x (l ++ r)` it has to choose whether to
go left or right. It has no way to know in advance which one is better so it
will pick one and backtrack if it doesn't work.

Use it to solve the following two goals.
|*)

Lemma In_app_l :
  forall A (x : A) l r,
    In x l ->
    In x (l ++ r).
Proof.
  intros A x l r h.
  induction l as [| y l ih] in r, h |- *.
  - simpl in h. contradiction.
  - simpl. simpl in h. destruct h as [h | h].
    + left. assumption.
    + right. apply ih. assumption.
Qed.

Lemma In_app_r :
  forall A (x : A) l r,
    In x r ->
    In x (l ++ r).
Proof.
  intros A x l r h.
  induction l as [| y l ih] in r, h |- *.
  - simpl. assumption.
  - simpl. right. apply ih. assumption.
Qed.

#[export] Hint Resolve In_app_l : indb.
#[export] Hint Resolve In_app_r : indb.

Goal forall A (x a b c d : A) l l',
  In x l ->
  In x ([ a ; b ; c ] ++ l' ++ d :: l).
Proof.
  auto with indb.
Qed.

Goal forall A (x a b c d : A) l l',
  In x l ->
  In x (l ++ [ a ; b ; c ] ++ l' ++ [ d ]).
Proof.
  auto with indb.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Equal elements
^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
What if the element in my list is not syntactically what I'm looking for
but only equal to it?

Prove a lemma for this particular case and add a hint for it.
It should solve the following goal.
|*)

Lemma In_hd_eq :
  forall A (x y : A) l,
    x = y ->
    In x (y :: l).
Proof.
  intros A x y l e.
  simpl. auto.
Qed.

#[export] Hint Resolve In_hd_eq : indb.

Goal forall A (x y a b c d : A) l l',
  x = y ->
  In x ([ a ; b ; c ] ++ l' ++ d :: y :: l).
Proof.
  auto with indb.
Qed.

(* From the lecture: *)

Axiom DNE : forall P : Prop, ~~ P -> P.
From Stdlib Require Import Classical.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: The arith database
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
The equality in the exercise "Equal elements" is not always going to be an
assumption in the context. But it could be handled by some more automation.
There is for instance the `arith` database that can deal with arithmetic.

You can give two (or more) databases to `auto`. Check that it indeed succeeds
in the following goal with `arith` but not without.
|*)

Goal forall (a b c d : nat) l l',
  In (a + b) ([ b ; c ] ++ l' ++ d :: (b + a) :: l).
Proof.
  auto with indb.
  auto with indb arith.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Limits of arith
^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Sadly, it has its limits: check that it isn't sufficient for the following
goal even though you should be able to prove it (do it).

.. tip::

  `lia` is stronger than `auto with arith` on that one.

..
|*)

Goal forall (a b c d : nat) l l',
  In (a + b + c) ([ a ; b ; c ] ++ l' ++ d :: (c + 0 + a + b) :: l).
Proof.
  intros.
  auto with indb arith.
  repeat apply In_tl.
  apply In_app_r. apply In_tl. apply In_hd_eq.
  lia.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Using lia in auto (advanced)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
There is a way to use `lia` with `auto` actually. For this we have to provide
a different kind of hint.
Using the command `Hint Extern` we can tell Rocq what tactic to try when
encountering a goal of the form `n = m` where `n, m : nat`.

Below what we do is say that when the goal is of the shape `@eq nat _ _`
then we apply `lia`. We add this to `indb`.
The 3 is something called cost. `auto` is actually cost-based and each action
it takes has a cost attached to it. `auto` will start by picking the actions
with the lowest cost when it has a choice. When it runs out of money, it
gives up.

Check that you can solve the previous goal using `auto with indb`.
Can you also make it so that the other goal works?
|*)

#[export] Hint Extern 3 (@eq nat _ _) => lia : indb.

Goal forall (a b c d : nat) l l',
  In (a + b + c) ([ a ; b ; c ] ++ l' ++ d :: (c + 0 + a + b) :: l).
Proof.
  auto with indb.
Qed.

#[export] Hint Extern 3 (@eq Z _ _) => lia : indb.

Goal forall (a b c d : Z) l l',
  In (a + b + c)%Z ([ a ; b ; c ] ++ l' ++ d :: (c + d + 0 + a - d + b) :: l)%Z.
Proof.
  auto with indb.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Existential variables
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Solve the following goal without using any lemma or variable in the context
explicitly.
|*)

Goal forall A (x : A) l l',
  exists y, In y (l ++ x :: l').
Proof.
  intros.
  eexists.
  auto with indb.
Qed.

(*|
^^^^^^^^^^^^^^^
Exercise: eauto
^^^^^^^^^^^^^^^
|*)

(*| Solve the following goal. |*)

Goal forall A (P : A -> A -> Prop) (Q : A -> Prop),
  (forall x, exists y, P x y) ->
  (forall x y, P x y -> Q x) ->
  (forall x, Q x).
Proof.
  intros A P Q h1 h2 x.
  specialize (h1 x) as [y h1].
  eauto.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Logical equivalences (advanced)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Another interesting feature of Rocq is the ability to rewrite on other things
rather than just equality.

For instance, we can use rewrite for logical equivalences.
Let us go through it step by step.

To begin, prove the following logical equivalences.
|*)

Lemma and_AA :
  forall A, A /\ A <-> A.
Proof.
  intro A. split.
  - intros []. auto.
  - auto.
Qed.

Lemma or_AA :
  forall A, A \/ A <-> A.
Proof.
  intro A. split.
  - intros []. all: auto.
  - auto.
Qed.

Lemma and_com :
  forall A B,
    A /\ B <-> B /\ A.
Proof.
  intros A B. split.
  all: intros [] ; auto.
Qed.

Lemma or_com :
  forall A B,
    A \/ B <-> B \/ A.
Proof.
  intros A B. split.
  all: intros [] ; auto.
Qed.

Lemma and_assoc :
  forall A B C,
    (A /\ B) /\ C <-> A /\ B /\ C.
Proof.
  intros A B C. split.
  - intros [[] ?]. auto.
  - intros [? []]. auto.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Rewriting with equivalences (advanced)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Now you can solve the following goals just by using rewrite on equivalences.
No more need for split!

Note that you can also use `reflexivity`, `symmetry` and `transitivity` on those.
Under the hood, this is using class resolution to find the proper instances.
For `iff` (logical equivalence) they are already registered so we can freely
use them.
|*)

Goal forall (A B C D : Prop),
  A /\ (B /\ B) /\ (C -> D) /\ (C -> D) <-> A /\ B /\ (C -> D).
Proof.
  intros A B C D.
  rewrite !and_AA.
  reflexivity.
Qed.

Goal forall (A B : Prop),
  (B /\ A /\ B) \/ (A /\ B) <-> B /\ A.
Proof.
  intros A B.
  rewrite (and_com A B). rewrite <- and_assoc. rewrite and_AA.
  rewrite or_AA.
  reflexivity.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Set equality on lists (advanced)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Ok, this is getting old. We're going to switch to another relation which isn't
already registered in the standard library.
First we're going to introduce a relation on lists that relates two lists
if they have the same elements (regardless of how many times they appear),
i.e., if they represent the same set.

Complete the following definition.
|*)

Definition list_set_eq {A} (u v : list A) : Prop :=
  forall x, In x u <-> In x v.

Notation "u ~ v" := (list_set_eq u v) (at level 70).

(*|
We first need to show that the relation is reflexive, symmetric and
transitive. We do so by instantiating the right classes so that we can use
the corresponding tactics (as for `iff`).

Check it works with the provided goal.
|*)

From Stdlib Require Import Setoid.

#[export] Instance list_set_eq_refl :
  forall A, Reflexive (list_set_eq (A := A)).
Proof.
  intro A. intro l. intro x. reflexivity.
Qed.

#[export] Instance list_set_eq_sym :
  forall A, Symmetric (list_set_eq (A := A)).
Proof.
  intro A. intros u v h.
  intro x. symmetry. apply h.
Qed.

#[export] Instance list_set_eq_trans :
  forall A, Transitive (list_set_eq (A := A)).
Proof.
  intro A. intros u v w h1 h2.
  intro x. etransitivity.
  - eapply h1.
  - apply h2.
Qed.

Goal forall A (u v w : list A),
  v ~ u ->
  (u ~ u -> v ~ w) ->
  u ~ w.
Proof.
  intros A u v w h1 h2.
  etransitivity.
  - symmetry. eassumption.
  - eapply h2. reflexivity.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Rewriting with set equality (advanced)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
We will use the following command to register this relation to use with
rewrite. Rocq will find the instances of equivalence relation we provided
above. Otherwise we could provide them manually.
Look up the documentation if you want to do that:
https://rocq-prover.org/doc/master/refman/addendum/generalized-rewriting.html

On the left of the colon we give the list of parameters, here there is only
one which is the type of values. We call it `A` and we can refer to it after
the colon.
The next argument is the type of elements we compare with the relation:
`list A`.
Then we give the relation itself: `list_set_eq`.
Finally we give a name to the setoid relation. This is for Rocq's internal use.

Prove the following goal using rewrite. This is just transitivity again but
this is to show you how it works on a simple example.
|*)

Add Parametric Relation A : (list A) list_set_eq as list_set_rel.

Goal forall A (u v w : list A),
  u ~ v ->
  v ~ w ->
  u ~ w.
Proof.
  intros A u v w h1 h2.
  rewrite h1. assumption.
Qed.

(*| Prove that `u ++ v ~ v ++ u`. |*)

Lemma In_app_inv :
  forall A (l r : list A) x,
    In x (l ++ r) ->
    In x l \/ In x r.
Proof.
  intros A l r x h.
  induction l as [| a l ih] in r, h |- *.
  - simpl in *. auto.
  - simpl in *. destruct h as [h | h].
    + eauto with indb.
    + specialize ih with (1 := h). destruct ih.
      all: auto with indb.
Qed.

Lemma list_set_eq_app :
  forall A (u v : list A),
    u ++ v ~ v ++ u.
Proof.
  intros A u v. intro x. split.
  all: intros h%In_app_inv. all: destruct h.
  all: auto with indb.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Morphisms (advanced)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
In order to rewrite this relation inside, *e.g.*, `In`, we have to first show
that `In` is invariant under `~`. In other words, that `u ~ v` implies
`In x u <-> In x v`.
We can use the following command to declare it. This will in turn let us
rewrite inside `In`.

Prove that we indeed have a morphism.
Prove the given goals using rewrite.
|*)

Add Parametric Morphism A (x : A) : (In x)
  with signature list_set_eq ==> iff
  as In_morph.
Proof.
  intros u v e. apply e.
Qed.

Goal forall A (x : A) u v,
  In x (u ++ v) ->
  In x (v ++ u).
Proof.
  intros A x u v h.
  rewrite list_set_eq_app. assumption.
Qed.

Goal forall A (x a b c : A) u v,
  In x (u ++ [ a ; b ; c ] ++ x :: v).
Proof.
  intros A x a b c u v.
  rewrite list_set_eq_app.
  rewrite <- app_assoc.
  rewrite list_set_eq_app.
  rewrite <- app_assoc. simpl. auto.
Qed.

(*|
Look up the `Forall` predicate. Show that it is a morphism for `list_set_eq`.
Proceed to solve the following goal.
|*)

Lemma Forall_In :
  forall A (P : A -> Prop) l,
    Forall P l <-> (forall x, In x l -> P x).
Proof.
  intros A P l.
  induction l as [| x l ih].
  - split.
    + simpl. intros _ _ [].
    + intros _. constructor.
  - split.
    + intros h a ha.
      inversion h. subst.
      simpl in ha. destruct ha as [e | hl].
      * subst. assumption.
      * apply ih. all: assumption.
    + intro h. constructor.
      * apply h. auto with indb.
      * rewrite ih. intros a ha.
        apply h. auto with indb.
Qed.

Lemma Forall_set_eq :
  forall A (P : A -> Prop) u v,
    u ~ v ->
    Forall P u ->
    Forall P v.
Proof.
  intros A P u v e h.
  rewrite Forall_In in h |- *.
  intros x hx.
  rewrite <- e in hx.
  apply h. assumption.
Qed.

Add Parametric Morphism A P : (@Forall A P)
  with signature list_set_eq ==> iff
  as Forall_morph.
Proof.
  intros u v e.
  split. all: apply Forall_set_eq.
  - auto.
  - symmetry. auto.
Qed.

Goal forall u v w,
  let P n := exists m, n = 2 * m in
  Forall P (w ++ u ++ v) ->
  Forall P (u ++ v ++ w).
Proof.
  intros u v w P h.
  rewrite list_set_eq_app.
  rewrite <- app_assoc.
  rewrite list_set_eq_app.
  rewrite <- app_assoc.
  assumption.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^
Exercise: Backtracking
^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
For each of the following scripts, predict *without running Rocq* whether it
succeeds, and which goal remains or which witness is chosen.
Then check your answer, using `Show Proof` to see the witness.

The `try` are only there so that the file compiles whatever the answer.
|*)

Goal exists (b : bool), negb b = true.
Proof.
  try (unshelve eexists ; constructor).
Abort.

Goal exists (n : nat), n = 1.
Proof.
  try (unshelve eexists ; constructor).
Abort.

Goal True \/ (False -> False).
Proof.
  try constructor ; intro x.
Abort.

Goal True \/ (False -> False).
Proof.
  try constructor. try intro x.
Abort.

Goal (False -> False) \/ True.
Proof.
  try (constructor ; exact I).
Abort.

(*| Answers:

1. It succeeds with `b := false`: `constructor` first picks `true`, but then
   `true = false` cannot be proven by `constructor`, so it backtracks.
2. It succeeds with `n := 1`: `0 = 1` fails, so `constructor` picks `S ?m`
   instead, and proving `S ?m = 1` with `eq_refl` instantiates `?m := 0`.
3. Only the goal `False` remains, with `x : False`: `intro x` fails on `True`,
   so `constructor` backtracks and picks the right disjunct.
4. The goal `True` remains: `constructor` picks the left disjunct, and
   backtracking does not go back across sentences (`.`), so `intro x` just
   fails and `try` hides the failure.
5. It succeeds with `or_intror I`: `exact I` fails on `False -> False`, so
   `constructor` backtracks to the right disjunct.
|*)

(* From the lecture: *)

Inductive mult4 : nat -> Prop :=
| mult4_0 : mult4 0
| mult4_plus n : mult4 n -> mult4 (4 + n).

Inductive not_mult4 : nat -> Prop :=
| not_mult4_1 : not_mult4 1
| not_mult4_2 : not_mult4 2
| not_mult4_3 : not_mult4 3
| not_mult4_plus n : not_mult4 n -> not_mult4 (4 + n).

(*|
^^^^^^^^^^^^^^^^^^^
Exercise: Tacticals
^^^^^^^^^^^^^^^^^^^
|*)

(*|
Prove each of the following goals with a *single* sentence, that is one tactic
expression ending with a single `.` after `Proof.`.
Combine `;`, `[ ... | ... ]`, `..`, `try`, `solve`, `repeat` and `do`.
|*)

Goal mult4 12 /\ not_mult4 7 /\ mult4 0 /\ not_mult4 10.
Proof.
  repeat split ; repeat constructor.
Qed.

Goal forall n, not_mult4 n -> not_mult4 (8 + n).
Proof.
  intros n h ; do 2 apply not_mult4_plus ; exact h.
Qed.

Goal forall n, n < 3 -> not_mult4 (n + 1).
Proof.
  intros n h ; destruct n as [| [| [| n]]] ; [ constructor .. | exfalso ; lia ].
Qed.

Goal forall n, mult4 n -> mult4 (n + 4).
Proof.
  intros n h ; induction h ;
    [ constructor ; constructor | simpl ; constructor ; assumption ].
Qed.

Ltac split_or_apply :=
  match goal with
  | |- ?A /\ ?B => split
  | h : ?B -> ?A |- ?A => apply h (* Here we match on any hypothesis *)
  (* The name [h] is of our choosing, it's going to apply to hypothesis
     [H : nat -> bool] for instance. *)
  end.

Ltac my_assumption :=
  match goal with
  | H : ?A |- ?A => apply H
  end.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Repeated split
^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Define a tactic `splits` to perform `split` repeatedly on goals of the shape
`A * B` but not on any other kinds of goals (for instance it should not solve
`True`).

For instance, on `(nat * bool) * (unit * bool)` it should yield 4 subgoals.

.. tip::

  You will need `split` and `match goal` or `lazymatch goal` and `idtac`.

..
|*)

Ltac splits :=
  lazymatch goal with
  | |- ?A * ?B => split ; splits
  | _ => idtac
  end.

(*| Try it on these goals. |*)

Goal nat * bool.
Proof.
  splits. (* 2 goals *)
Abort.

Goal nat * (bool * unit) * (unit * nat * bool) * unit.
Proof.
  splits. (* 7 goals *)
Abort.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Clearing before induction
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Prove the following by induction on `n`.
In particular, don't use `lia`: we want you to use the induction hypothesis.
|*)
Goal forall n, n mod 14 = 7 -> n - n = 0.
Proof.
  intros n hn.
  clear hn. (* Note that without this, the IH is useless *)
  induction n.
  - reflexivity.
  - cbn. eauto.
Qed.

Ltac handle_hyp h :=
  lazymatch type of h with
  | (?A * ?B)%type => destruct h
  | nat => induction h
  | _ => idtac
  end.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Forward reasoning
^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
A very useful tactic that should be part of the standard library, but is not,
is the `fwd` tactic.
Given `H : P -> Q`, `fwd H` will yield two goals:

- one where `P` must be proven
- and one where `H` has been replaced by `H : Q`

Note that there shouldn't be anything else appearing in the goal.

Define such a tactic.
|*)

Ltac fwd h :=
  match type of h with
  | ?P -> _ =>
    let h' := fresh in
    assert (h' : P) ; [| specialize (h h') ; clear h' ]
  end.

(*| Try on the following goal.
Do not use `apply`, only `intros`, `fwd` and `assumption`. |*)
Goal forall P Q R, (P -> Q -> R) -> (P -> Q) -> P -> R.
Proof.
  intros P Q R h1 h2 h3.
  fwd h2. 1: assumption.
  fwd h1. 1: assumption.
  fwd h1. 1: assumption.
  assumption.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Forward reasoning with a tactic (harder)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Try to generalise the code for `fwd` so that you can also provide a tactic.
If `H : P -> Q` then `forward_gen H tac` will also apply `tac` to try and
solve the goal `P` first.
|*)

Ltac forward_gen h tac :=
  match type of h with
  | ?P -> _ =>
    let h' := fresh in
    assert (h' : P) ; [ tac | specialize (h h') ; clear h' ]
  end.

(*| Once `forward_gen` is defined, we define handy notations:
`Tactic Notation "forward" constr(H) := forward_gen H ltac:(idtac).` and
`Tactic Notation "forward" constr(H) "by" tactic(tac) := forward_gen H tac.`
|*)
Tactic Notation "forward" constr(H) := forward_gen H ltac:(idtac).
Tactic Notation "forward" constr(H) "by" tactic(tac) := forward_gen H tac.

Goal forall P Q R, (P -> Q -> R) -> (P -> Q) -> P -> R.
Proof.
  intros P Q R h1 h2 h3.
  forward h2 by assumption.
  do 2 forward h1 by assumption.
  assumption.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: A tauto tactic
^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Write a tactic `my_tauto` that solves the following goals.
You can start from the following, and expand it:
`Ltac my_tauto := lazymatch goal with | |- True => constructor end.`
|*)

Ltac my_tauto :=
  lazymatch goal with
  | h : ?P |- ?P => exact h

  | |- True => constructor
  | |- _ /\ _ => split ; my_tauto
  | |- _ -> _ => intro ; my_tauto

  | h : False |- _ => destruct h
  | h : _ /\ _ |- _ => destruct h ; my_tauto
  | h : _ \/ _ |- _ => destruct h ; my_tauto

  | h1 : ?P -> ?Q, h2 : ?P |- _ => specialize (h1 h2) ; my_tauto

  | |- _ \/ _ => (left ; my_tauto) || (right ; my_tauto)
  end.

Section Tauto.

  Variables (P Q R : Prop).

  Goal P -> True /\ True.
  Proof.
    my_tauto.
  Qed.

  Goal P -> P.
  Proof.
    my_tauto.
  Qed.

  Goal P -> (P -> R) -> R.
  Proof.
    my_tauto.
  Qed.

  Goal False \/ True.
  Proof.
    my_tauto.
  Qed.

  Goal (P \/ Q \/ False) /\ (P -> Q) -> True /\ (R \/ Q).
  Proof.
    my_tauto.
  Qed.

End Tauto.

(* From the lecture: *)

Require Import MetaRocqPrelude.

Axiom LEM : forall (P : Prop), P \/ ~ P.
Axiom funext : forall A B (f g : A -> B), (forall x, f x = g x) -> f = g.

Lemma foo_ax :
  (fun n => n + 0) = (fun n => n).
Proof.
  apply funext. intro. rewrite <- plus_n_O. reflexivity.
Qed.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Print Assumptions
^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Define a Rocq function `assumptions : global_env × term -> list kername`
such that `Compute assumptions ($quote_rec f)` returns the list of
assumptions (axioms) that `f` depends on, including recursively.

Note: You cannot convince Rocq that it is terminating, so we'll deactivate
termination checking. That's ok when meta-programming.

.. tip::

  You may use the `flat_map` and `lookup_constant` functions too.

..
|*)

Unset Guard Checking.
Fixpoint assms (env : global_env) (t : term) {struct t} : list kername :=
  match t with
  | tConst c u =>
      match lookup_constant env c with
      | Some body =>
          match body.(cst_body) with
          | None => [c]
          | Some c => assms env c
          end
      | _ => []
      end
  | tRel _ | tVar _ | tSort _ | tInd _ _ | tConstruct _ _ _ | tInt _ | tFloat _ | tString _ => []
  | tEvar ev args => flat_map (assms env) args
  | tCast t kind v => assms env t ++ assms env v
  | tProd na ty body => assms env ty ++ assms env body
  | tLambda na ty body => assms env ty ++ assms env body
  | tLetIn na def def_ty body => assms env def ++ assms env def_ty ++ assms env body
  | tApp f args => assms env f ++ flat_map (assms env) args
  | tCase ci type_info discr branches =>
      assms env discr ++ flat_map (fun b => assms env b.(bbody)) branches
  | tProj proj t => assms env t
  | tFix mfix idx => flat_map (fun d => assms env d.(dbody)) mfix
  | tCoFix mfix idx => flat_map (fun d => assms env d.(dbody)) mfix
  | tArray u arr def ty => flat_map (assms env) arr ++ assms env def ++ assms env ty
  end.
Set Guard Checking.

Definition assumptions p :=
  assms p.1 p.2.

Compute assumptions ($quote_rec 0).

Compute assumptions ($quote_rec foo_ax).

Definition bar_ax : nat :=
  let x := foo_ax in
  139.

Compute assumptions ($quote_rec bar_ax).

Module test.

  Lemma DNE P : ~~ P -> P.
  Proof.
    tauto.
  Qed.

End test.

Compute assumptions ($quote_rec test.DNE).

Definition more_deps :=
  (bar_ax, test.DNE, LEM).

Compute assumptions ($quote_rec more_deps).

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Folding multiply-add
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Define a function which replaces any subterm of the form `a * b + c` with
`muladd a b c` defined below.

.. tip::

  You can use `u == v` to check whether `u` and `v` are equal terms
  (it returns a Boolean).

..
|*)

Definition muladd a b c :=
  a * b + c.

#[bypass_check(guard)] Fixpoint fold_muladd (t : term) : term :=
  match t with
  | tApp p ([ tApp m [ a ; b ] ; c ] as args) =>
      if (p == $quote plus) && (m == $quote mult)
      then tApp ($quote muladd) [ fold_muladd a ; fold_muladd b ; fold_muladd c ]
      else tApp (fold_muladd p) (map fold_muladd args)
  | tApp f args => tApp (fold_muladd f) (map fold_muladd args)
  | tRel n => tRel n
  | tVar id => tVar id
  | tEvar ev args => tEvar ev (map fold_muladd args)
  | tSort s => tSort s
  | tCast t kind v => tCast (fold_muladd t) kind (fold_muladd v)
  | tProd na ty body => tProd na (fold_muladd ty) (fold_muladd body)
  | tLambda na ty body => tLambda na (fold_muladd ty) (fold_muladd body)
  | tLetIn na def def_ty body => tLetIn na (fold_muladd def) (fold_muladd def_ty) (fold_muladd body)
  | tConst c u => tConst c u
  | tInd ind u => tInd ind u
  | tConstruct ind idx u => tConstruct ind idx u
  | tCase ind p discr brs =>
      let p' := map_predicate id fold_muladd fold_muladd p in
      let brs' := map_branches fold_muladd brs in
      tCase ind p' (fold_muladd discr) brs'
  | tProj proj t => tProj proj (fold_muladd t)
  | tFix mfix idx => tFix (map (map_def fold_muladd fold_muladd) mfix) idx
  | tCoFix mfix idx => tCoFix (map (map_def fold_muladd fold_muladd) mfix) idx
  | tInt i => tInt i
  | tFloat f => tFloat f
  | tString s => tString s
  | tArray u arr def ty => tArray u (map fold_muladd arr) (fold_muladd def) (fold_muladd ty)
  end.

(*| Test it with the following. |*)

Check $unquote (fold_muladd ($quote (3 * 2 + 5))).
Check $unquote (fold_muladd ($quote (1 + (3 * 2 + 5)))).
Check $unquote (fold_muladd ($quote ((9 * 2 + 0) * (1 + (3 * 2 + 5)) + 1 + (3 * 2 + 5)))).

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Folding multiply-add with transform
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Now that you suffered through the definition of `fold_muladd`, define it again
using `transform`.
`transform` takes `h : tm_handler` and transforms `t : term` into another
`term`.
The handler is typically of the form `fun t k => ...` where `t` is the subterm
to inspect/transform and `k` is a continuation. Calling `k` on a subterm
(or on `t` itself) gives control back to `transform` which will decompose
the subterm once, and then call the handler again on the subsequent subterms.
|*)

Definition muladd_handler : tm_handler :=
  fun t k =>
    match t with
    | tApp p [ tApp m [ a ; b ] ; c ] =>
      if (p == $quote plus) && (m == $quote mult)
      then k (tApp ($quote muladd) [ a ; b ; c ])
      else k t
    | _ => k t
    end.

Definition fold_muladd_alt :=
  transform muladd_handler.

Check $unquote (fold_muladd_alt ($quote (3 * 2 + 5))).
Check $unquote (fold_muladd_alt ($quote (1 + (3 * 2 + 5)))).
Check $unquote (fold_muladd_alt ($quote ((9 * 2 + 0) * (1 + (3 * 2 + 5)) + 1 + (3 * 2 + 5)))).

(*|
If you want, you can also do the same for `assumptions` by using
`tm_fold` which is similar but implements a fold instead.
|*)

Definition assum_fold (env : global_env) : fold_handler (list kername) :=
  fun t a k =>
    match t with
    | tConst c u =>
        match lookup_constant env c with
        | Some body =>
            match body.(cst_body) with
            | None => c :: a
            | Some c => k a c
            end
        | _ => []
        end
    | _ => k a t
    end.

Definition assumptions_alt p : list kername :=
  tm_fold (assum_fold p.1) [] p.2.

Compute assumptions_alt ($quote_rec 0).
Compute assumptions_alt ($quote_rec foo_ax).
Compute assumptions_alt ($quote_rec bar_ax).
Compute assumptions_alt ($quote_rec test.DNE).

(*|
^^^^^^^^^^^^^^^^^^^^^
Exercise: Reification
^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Write a command `reify` that turns a Rocq expression of type `nat` into an
expression of the following datatype.
Expressions that do not start with `+` or `*` are reified as constants.
|*)

Inductive arith :=
| aPlus : arith -> arith -> arith
| aTimes : arith -> arith -> arith
| aConst : nat -> arith.

#[bypass_check(guard)] Fixpoint reify (t : term) : term :=
  match t with
  | tApp c [ u ; v ] =>
      if c == $quote plus then tApp ($quote aPlus) [ reify u ; reify v ]
      else if c == $quote mult then tApp ($quote aTimes) [ reify u ; reify v ]
      else tApp ($quote aConst) [t]
  | _n => tApp ($quote aConst) [t]
  end.

Goal 4 * (9 + 12) + (3 + 1 * 7) = 2.
Proof.
  match goal with
  | [ |- ?L = _ ] =>
    let x := eval cbv in $unquote (reify ($quote L)) in
    pose x
  end.
Abort.

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Instantiating axioms (advanced)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
Write a meta-program that takes a definition potentially using an axiom and
a proof of said axiom to produce a new definition, equal to the original one
except that uses of the axiom are replaced by the proof.

The axiom to be replaced is going to be given as a `kername`, like those
collected by `assumptions`.
You don't actually have to verify that the constant is indeed an axiom.

.. tip::

  You will need `eq_constant`.

..
|*)

Definition instantiate_axiom (ax : kername) (prf : term) : term -> term :=
  transform (fun t k =>
    match t with
    | tConst c u =>
      if eq_constant ax c then prf
      else k t
    | _ => k t
    end
  ).

Axiom mystery : nat.

Definition what :=
  mystery * 3.

Compute $unquote (instantiate_axiom ($name mystery) ($quote 10) ($Quote what)).

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Removing axioms (advanced)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
A slightly harder version would be to turn a definition using axioms to one
assuming these axioms with an implication.

For instance, for the `foo_ax` defined above which uses `funext`, we would
expect something of the following type:
`(forall A B (f g : A -> B), (forall x, f x = g x) -> f = g) -> (fun n => n + 0) = (fun n => n)`

.. tip::

  You can use `assumptions` and `lookup_constant` to get the type of a
  constant, and `lift0 1 t` to weaken `t` by adding one new variable in the
  context.

..

You can also use a variant of `transform` called `transform_nb` which also
tracks the number of introduced variables (to know how much to lift by).
|*)

Definition replace_const_lift c u :=
  transform_nb (fun nb t k =>
    match t with
    | tConst c' ui =>
      if eq_constant c c' then (lift0 nb u)
      else k nb t
    | _ => k nb t
    end
  ) 0.

Definition unaxiom (p : global_env * term) : term :=
  let axs := assumptions p in
  fold_left (fun t ax =>
    match lookup_constant p.1 ax with
    | Some body =>
      let ty := body.(cst_type) in
      tLam "ax" ty (replace_const_lift ax (tRel 0) t)
    | None => t (* Something wrong, so we just let go *)
    end
  ) axs p.2.

Eval simpl in $unquote (unaxiom ($Quote_rec what)).

Axiom unknown : bool.
Axiom random : nat -> nat.

Definition test f :=
  if unknown then what else random (f 9).

Eval simpl in $unquote (unaxiom ($Quote_rec test)).

(*|
.. note::

   This is not recursive! It could be fixed by modifying `replace_const_lift`
   further by also performing `lookup_constant` and going through constants.
   This might have the undesired side effect of unfolding all constants though
   so we'll just accept this simple solution for now.
|*)

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^
Exercise: Deriving (hard)
^^^^^^^^^^^^^^^^^^^^^^^^^
|*)

(*|
We promised MetaRocq could be used to derive automatically certain things.
Let's see how this can be done by automatically deriving update functions for
a record.

We assume that there is no dependency between the fields, otherwise it's
unclear what an update function should do.

This exercise is hard, so it makes sense to make some assumptions first
such as the absence of parameters (like in `triple` below) or of local
definitions (like in `trap` below).
Don't hesitate to ask questions if you are stuck.

We'll start with a few record definitions, together with one example of an
update function, don't hesitate to write your own and quote them to understand
what you need to write.
|*)

Record point3D := {
  px : nat ;
  py : nat ;
  pz : nat
}.

Record Zalt := {
  num : nat ;
  positive : bool
}.

Record triple A B C := {
  p1 : A ;
  p2 : B ;
  p3 : C
}.

Record trap := {
  v1 : nat ;
  v2 := 10 ^ v1 ;
  v3 : nat
}.

(*| We write an update for `num` by hand. |*)
Definition upd_num (f : nat -> nat) (x : Zalt) :=
  match x with
  | Build_Zalt num positive => Build_Zalt (f num) positive
  end.

(*|
.. note::

   There are other ways to write it, but this one might be the easiest to
   automate.
|*)

(*| Now we can look at how it is quoted.

We use `$Quote` rather than `$quote` to unfold the constant `upd_num` when
quoting it. Otherwise we would get some `tConst` which is not as informative.
|*)

Definition q_upd_num := $Quote upd_num.
Print q_upd_num.

(*|
Below is a meta-program that gives you the definition of an inductive.

.. tip::

  It may be useful to you later, perhaps not as-is, but with some
  modification to also get the argument of `tInd`.

..
|*)
Definition get_inductive {A} (ind : A) :=
  t <- tmQuote ind ;;
  match t with
  | tInd ind _ =>
    let kn := ind.(inductive_mind) in
    tmQuoteInductive kn
  | _ => tmFail "Not an inductive type"
  end.

(*| We use it like this to define `Zalt_def` to inspect at our leisure. |*)
MetaRocq Run (
  mib <- get_inductive Zalt ;;
  tmDefinition "Zalt_def" mib
).

(*| This now contains the definition of `Zalt`.

You may compare the information you see in here with what appeared in
`q_upd_num`. It might be useful to copy paste them to better compare.
|*)
Print Zalt_def.

(*| To help you build the `derive_updates` meta-program, we'll give you some
useful tools.

Also check out the following useful constructs:

- `tmMkDefinition` takes a `string` and a `term` and produces a definition
  using that name (if fresh, otherwise it fails) and unquoting the given term.
- `tmFreshName` takes a `string` and will return a new string that is fresh in
  the current environment, based on the given one (typically by adding a
  number at the end).

If you plan to handle parameters:

- `it_mkLambda_or_LetIn` takes `c : context` and `t : term` and produces
  a new λ-abstraction with body `t` and quantifying over `c`.
  Basically it does the right thing by inserting as many `tLam` as necessary.
- `subst l 0 t` will substitute the variables of `t` using the terms provided
  in `l`. For this exercise, you can provide garbage (just some random
  `tRel k` will suffice), what matters is the number of terms you provide.
  Providing `3` will reduce `tRel 5` to `tRel 2`.
|*)

(*| Handy concatenation notation. |*)
Notation "a # b" := (String.append a b).

(*| To debug we recommend you use the following in place of `tmMkDefinition` |*)
Definition tmDebugDefinition na (t : term) :=
  t <- tmEval all t ;;
  tmDefinition na t.

(*| `mkr 3 2` will produce `[ tRel 4 ; tRel 3 ; tRel 2 ]` |*)
Fixpoint mkr i off :=
  match i with
  | 0 => []
  | S i => tRel (off + i) :: mkr i off
  end.

(*| Extract the name from `aname` or use `d` as default. |*)
Definition get_name (a : aname) d :=
  match a.(binder_name) with
  | nNamed na => na
  | nAnon => d
  end.

Definition has_body (c : context_decl) :=
  match c.(decl_body) with
  | Some _ => true
  | None => false
  end.

Fixpoint mkargs_aux nargs n args i {struct i} :=
  match i, n with
  | 0, _ => []
  | S i, Some (S n) =>
    let l := mkargs_aux nargs (Some n) (tl args) i in
    if hd true args then l else tRel i :: l
  | S i, Some 0 =>
    let l := mkargs_aux nargs None (tl args) i in
    if hd true args then l else tApp (tRel (S nargs)) [ tRel i ] :: l
  | S i, None =>
    let l := mkargs_aux nargs None (tl args) i in
    if hd true args then l else tRel i :: l
  end.

Definition mkargs nargs n args :=
  let l := rev_map has_body args in
  mkargs_aux nargs n l nargs.

Definition from_arg ind npar params args cargs n (a : context_decl) :=
  match a.(decl_body) with
  | Some _ => None
  | None =>
    let nargs := List.length args in
    let ty := subst (mkr (nargs - S n) 0) 0 a.(decl_type) in
    let nparams := List.length params in
    let t :=
      it_mkLambda_or_LetIn params (
        tLam "f" (tImpl ty ty) (
          tLam "x" (mkApps (tInd ind []) (mkr nparams 1)) (
            tCase
              {| ci_ind := ind ; ci_npar := npar ; ci_relevance := Relevant |}
              {|
                puinst := [] ;
                pparams := mkr nparams 2 ;
                pcontext := [
                  {| binder_name := nNamed "x"; binder_relevance := Relevant |}
                ] ;
                preturn := mkApps (tInd ind []) (mkr nparams 3)
              |}
              (tRel 0)
              [
                {|
                  bcontext := args ;
                  bbody := tApp (tConstruct ind 0 []) (mkr nparams 5 ++ mkargs nargs (Some (nargs - S n)) cargs)
                |}
              ]
          )
        )
      )
    in
    Some (a.(decl_name), t)
  end.

Definition from_ctor ind npar params (b : constructor_body) :=
  let args := map decl_name b.(cstr_args) in
  mapi (from_arg ind npar params args b.(cstr_args)) b.(cstr_args).

Fixpoint def_list dn (l : list (option (aname * term))) :=
  match l with
  | Some (n, q) :: l =>
    na <- tmFreshName ("upd_" # get_name n dn) ;;
    tmMkDefinition na q ;;
    def_list dn l
  | None :: l => def_list dn l
  | [] => tmReturn tt
  end.

Fixpoint debug_def_list dn (l : list (option (aname * term))) :=
  match l with
  | Some (n, q) :: l =>
    na <- tmFreshName ("debug_" # get_name n dn) ;;
    tmDebugDefinition na q ;;
    debug_def_list dn l
  | None :: l => debug_def_list dn l
  | [] => tmReturn tt
  end.

Definition from_mind (def_list : ident -> list (option (aname * term)) -> TemplateMonad unit) ind mind :=
  match mind.(ind_finite) with
  | BiFinite =>
    match mind.(ind_bodies) with
    | [ oib ] =>
      match oib.(ind_ctors) with
      | [ cstr ] =>
        let upd_funs := from_ctor ind mind.(ind_npars) mind.(ind_params) cstr in
        let default_name := string_of_kername ind.(inductive_mind) in
        def_list default_name upd_funs
      | _ => tmFail "A record should have exactly one constructor"
      end
    | _ => tmFail "Expecting only one record (not mutually defined)"
    end
  | _ => tmFail "Not a record"
  end.

Definition get_inductive' {A} (ind : A) :=
  t <- tmQuote ind ;;
  match t with
  | tInd ind _ =>
    let kn := ind.(inductive_mind) in
    q <- tmQuoteInductive kn ;;
    tmReturn (ind, q)
  | _ => tmFail "Not an inductive type"
  end.

Definition derive_updates {A} (ind : A) : TemplateMonad unit :=
  '(ind, mib) <- get_inductive' ind ;;
  from_mind def_list ind mib.

(*|
.. tip::

   Use the same as `derive_updates` with `tmDebugDefinition` instead of
   `tmMkDefinition`. It will help debug because I don't expect the error messages
   to be very useful.
|*)
Definition debug_derive_updates {A} (ind : A) : TemplateMonad unit :=
  '(ind, mib) <- get_inductive' ind ;;
  from_mind debug_def_list ind mib.

(*| Below, one of them should always fail. |*)
MetaRocq Run (derive_updates point3D).
MetaRocq Run (derive_updates Zalt).
Fail MetaRocq Run (derive_updates nat).
MetaRocq Run (derive_updates triple).
MetaRocq Run (derive_updates trap).

(*| Test that it works. If you manage to execute those lines, it's very likely that it does, but
better safe than sorry.
|*)

Compute upd_p2 _ _ _ S {| p1 := "hello" ; p2 := 23 ; p3 := true |}.
Compute upd_v3 (fun n => 23 + n) {| v1 := 2 ; v3 := 12 |}.

From MetaRocq.Utils Require Import ReflectEq.

Ltac intro_Prop :=
  match goal with
  | |- forall P : Prop, _ => intro
  end.
