Library Paco.paco3

Require Export paconotation pacotacuser.
Require Import paconotation_internal pacotac pacon.
Set Implicit Arguments.

Section PACO3.

Variable T0 : Type.
Variable T1 : forall (x0: @T0), Type.
Variable T2 : forall (x0: @T0) (x1: @T1 x0), Type.

Record sig3T :=
  exist3T {
      proj3T0: @T0;
      proj3T1: @T1 proj3T0;
      proj3T2: @T2 proj3T0 proj3T1;
    }.

Definition uncurry3 (R: rel3 T0 T1 T2): rel1 sig3T := fun x => R (proj3T0 x) (proj3T1 x) (proj3T2 x).

Definition curry3 (R: rel1 sig3T): rel3 T0 T1 T2 :=
  fun x0 x1 x2 => R (exist3T x2).

Lemma uncurry_map3 r0 r1 (LE : r0 <3== r1) : uncurry3 r0 <1== uncurry3 r1.
Proof. intros [] H. apply LE. apply H. Qed.

Lemma uncurry_map_rev3 r0 r1 (LE: uncurry3 r0 <1== uncurry3 r1) : r0 <3== r1.
Proof.
  repeat_intros 3. intros H. apply (LE (exist3T x2) H).
Qed.

Lemma curry_map3 r0 r1 (LE: r0 <1== r1) : curry3 r0 <3== curry3 r1.
Proof.
  repeat_intros 3. intros H. apply (LE (exist3T x2) H).
Qed.

Lemma curry_map_rev3 r0 r1 (LE: curry3 r0 <3== curry3 r1) : r0 <1== r1.
Proof.
  intros [] H. apply LE. apply H.
Qed.

Lemma uncurry_bij1_3 r : curry3 (uncurry3 r) <3== r.
Proof. unfold le3. repeat_intros 3. intros H. apply H. Qed.

Lemma uncurry_bij2_3 r : r <3== curry3 (uncurry3 r).
Proof. unfold le3. repeat_intros 3. intros H. apply H. Qed.

Lemma curry_bij1_3 r : uncurry3 (curry3 r) <1== r.
Proof. intros []. intro H. apply H. Qed.

Lemma curry_bij2_3 r : r <1== uncurry3 (curry3 r).
Proof. intros []. intro H. apply H. Qed.

Lemma uncurry_adjoint1_3 r0 r1 (LE: uncurry3 r0 <1== r1) : r0 <3== curry3 r1.
Proof.
  apply uncurry_map_rev3. eapply le1_trans; [apply LE|]. apply curry_bij2_3.
Qed.

Lemma uncurry_adjoint2_3 r0 r1 (LE: r0 <3== curry3 r1) : uncurry3 r0 <1== r1.
Proof.
  apply curry_map_rev3. eapply le3_trans; [|apply LE]. apply uncurry_bij2_3.
Qed.

Lemma curry_adjoint1_3 r0 r1 (LE: curry3 r0 <3== r1) : r0 <1== uncurry3 r1.
Proof.
  apply curry_map_rev3. eapply le3_trans; [apply LE|]. apply uncurry_bij2_3.
Qed.

Lemma curry_adjoint2_3 r0 r1 (LE: r0 <1== uncurry3 r1) : curry3 r0 <3== r1.
Proof.
  apply uncurry_map_rev3. eapply le1_trans; [|apply LE]. apply curry_bij1_3.
Qed.

Definition paco3(gf : rel3 T0 T1 T2 -> rel3 T0 T1 T2)(r: rel3 T0 T1 T2) : rel3 T0 T1 T2 :=
  curry3 (paco (fun R0 => uncurry3 (gf (curry3 R0))) (uncurry3 r)).

Definition upaco3(gf : rel3 T0 T1 T2 -> rel3 T0 T1 T2)(r: rel3 T0 T1 T2) := paco3 gf r \3/ r.
Arguments paco3 : clear implicits.
Arguments upaco3 : clear implicits.
Hint Unfold upaco3.

Definition monotone3 (gf: rel3 T0 T1 T2 -> rel3 T0 T1 T2) :=
  forall x0 x1 x2 r r' (IN: gf r x0 x1 x2) (LE: r <3= r'), gf r' x0 x1 x2.

Definition _monotone3 (gf: rel3 T0 T1 T2 -> rel3 T0 T1 T2) :=
  forall r r'(LE: r <3= r'), gf r <3== gf r'.

Lemma monotone3_eq (gf: rel3 T0 T1 T2 -> rel3 T0 T1 T2) :
  monotone3 gf <-> _monotone3 gf.
Proof. unfold monotone3, _monotone3, le3. split; intros; eapply H; eassumption. Qed.

Lemma monotone3_map (gf: rel3 T0 T1 T2 -> rel3 T0 T1 T2)
      (MON: _monotone3 gf) :
  _monotone (fun R0 => uncurry3 (gf (curry3 R0))).
Proof.
  repeat_intros 3. apply uncurry_map3. apply MON; apply curry_map3; assumption.
Qed.

Lemma _paco3_mon_gen (gf gf': rel3 T0 T1 T2 -> rel3 T0 T1 T2) r r'
    (LEgf: gf <4= gf')
    (LEr: r <3= r'):
  paco3 gf r <3== paco3 gf' r'.
Proof.
  apply curry_map3. red; intros. eapply paco_mon_gen. apply PR.
  - intros. apply LEgf, PR0.
  - intros. apply LEr, PR0.
Qed.

Lemma paco3_mon_gen (gf gf': rel3 T0 T1 T2 -> rel3 T0 T1 T2) r r' x0 x1 x2
    (REL: paco3 gf r x0 x1 x2)
    (LEgf: gf <4= gf')
    (LEr: r <3= r'):
  paco3 gf' r' x0 x1 x2.
Proof.
  eapply _paco3_mon_gen; [apply LEgf | apply LEr | apply REL].
Qed.

Lemma upaco3_mon_gen (gf gf': rel3 T0 T1 T2 -> rel3 T0 T1 T2) r r' x0 x1 x2
    (REL: upaco3 gf r x0 x1 x2)
    (LEgf: gf <4= gf')
    (LEr: r <3= r'):
  upaco3 gf' r' x0 x1 x2.
Proof.
  destruct REL.
  - left. eapply paco3_mon_gen; [apply H | apply LEgf | apply LEr].
  - right. apply LEr, H.
Qed.

Section Arg3.

Variable gf : rel3 T0 T1 T2 -> rel3 T0 T1 T2.
Arguments gf : clear implicits.

Theorem _paco3_mon: _monotone3 (paco3 gf).
Proof.
  repeat_intros 3. eapply curry_map3, _paco_mon; apply uncurry_map3; assumption.
Qed.

Theorem _paco3_acc: forall
  l r (OBG: forall rr (INC: r <3== rr) (CIH: l <3== rr), l <3== paco3 gf rr),
  l <3== paco3 gf r.
Proof.
  intros. apply uncurry_adjoint1_3.
  eapply _paco_acc. intros.
  apply uncurry_adjoint1_3 in INC. apply uncurry_adjoint1_3 in CIH.
  apply uncurry_adjoint2_3.
  eapply le3_trans. eapply (OBG _ INC CIH).
  apply curry_map3.
  apply _paco_mon; try apply le1_refl; apply curry_bij1_3.
Qed.

Theorem _paco3_mult_strong: forall r,
  paco3 gf (upaco3 gf r) <3== paco3 gf r.
Proof.
  intros. apply curry_map3.
  eapply le1_trans; [| eapply _paco_mult_strong].
  apply _paco_mon; intros []; intros H; apply H.
Qed.

Theorem _paco3_fold: forall r,
  gf (upaco3 gf r) <3== paco3 gf r.
Proof.
  intros. apply uncurry_adjoint1_3.
  eapply le1_trans; [| apply _paco_fold]. apply le1_refl.
Qed.

Theorem _paco3_unfold: forall (MON: _monotone3 gf) r,
  paco3 gf r <3== gf (upaco3 gf r).
Proof.
  intros. apply curry_adjoint2_3.
  eapply _paco_unfold; apply monotone3_map; assumption.
Qed.

Theorem paco3_acc: forall
  l r (OBG: forall rr (INC: r <3= rr) (CIH: l <3= rr), l <3= paco3 gf rr),
  l <3= paco3 gf r.
Proof.
  apply _paco3_acc.
Qed.

Theorem paco3_mon: monotone3 (paco3 gf).
Proof.
  apply monotone3_eq.
  apply _paco3_mon.
Qed.

Theorem upaco3_mon: monotone3 (upaco3 gf).
Proof.
  repeat_intros 5. intros R LE0.
  destruct R.
  - left. eapply paco3_mon. apply H. apply LE0.
  - right. apply LE0, H.
Qed.

Theorem paco3_mult_strong: forall r,
  paco3 gf (upaco3 gf r) <3= paco3 gf r.
Proof.
  apply _paco3_mult_strong.
Qed.

Corollary paco3_mult: forall r,
  paco3 gf (paco3 gf r) <3= paco3 gf r.
Proof. intros; eapply paco3_mult_strong, paco3_mon; [apply PR|..]; intros; left; assumption. Qed.

Theorem paco3_fold: forall r,
  gf (upaco3 gf r) <3= paco3 gf r.
Proof.
  apply _paco3_fold.
Qed.

Theorem paco3_unfold: forall (MON: monotone3 gf) r,
  paco3 gf r <3= gf (upaco3 gf r).
Proof.
  repeat_intros 1. eapply _paco3_unfold; apply monotone3_eq; assumption.
Qed.

End Arg3.

Arguments paco3_acc : clear implicits.
Arguments paco3_mon : clear implicits.
Arguments upaco3_mon : clear implicits.
Arguments paco3_mult_strong : clear implicits.
Arguments paco3_mult : clear implicits.
Arguments paco3_fold : clear implicits.
Arguments paco3_unfold : clear implicits.

Global Instance paco3_inst (gf : rel3 T0 T1 T2->_) r x0 x1 x2 : paco_class (paco3 gf r x0 x1 x2) :=
{ pacoacc := paco3_acc gf;
  pacomult := paco3_mult gf;
  pacofold := paco3_fold gf;
  pacounfold := paco3_unfold gf }.

End PACO3.

Global Opaque paco3.

Hint Unfold upaco3.
Hint Resolve paco3_fold.
Hint Unfold monotone3.