PADEC
Coq Library
Tools
PADEC - Coq Library

Library Padec.Tools.OptionUtil

A Framework for Certified Self-Stabilization
PADEC Coq Library

Global imports

Require Import Relations.
Require Import SetoidClass.

Local imports

Require Import SetoidUtil.

Open Scope signature_scope.
Set Implicit Arguments.

Setoid and Partial Setoid on options

equality on option
Definition eqoptionA {A: Type} (eqA: relation A): relation (option A) :=
  fun oa1 oa2 => match oa1,oa2 with
                 | None, None => True
                 | Some a1, Some a2 => eqA a1 a2
                 | _, _ => False
                 end.

comparison on option
Definition leoptionA {A: Type} (eqA: relation A): relation (option A) :=
  fun oa1 oa2 => match oa1, oa2 with
                 | None, _ => True
                 | Some a1, Some a2 => eqA a1 a2
                 | _, _ => False
                 end.

Instance leoptionA_compat {A: Type} (eqA: relation A) `{P: PER _ eqA}:
  Proper (eqoptionA eqA ==> eqoptionA eqA ==> iff) (leoptionA eqA).

Instance leoptionA_transitive {A: Type} (eqA: relation A):
  Transitive eqA -> Transitive (leoptionA eqA).

PartialSetoid/Setoid for options based on a PartialSetoid/Setoid
Instance eqoptionA_per {A: Type} (eqA: relation A) `{P: PER _ eqA}:
  PER (eqoptionA eqA).

Instance eqoptionA_equiv {A: Type} (eqA: relation A)
         `{P: Equivalence _ eqA}: Equivalence (eqoptionA eqA).

Instance option_PartialSetoid {A} `{SA: PartialSetoid A}:
  PartialSetoid (option A) := {| pequiv := eqoptionA pequiv |}.

Instance option_Setoid {A} `{SA: Setoid A}:
  Setoid (option A) := {| equiv := eqoptionA equiv |}.

Decidability

Lemma eqoptionA_dec {A:Type} (eqA: relation A):
  Decider eqA -> Decider (eqoptionA eqA).

Lemma leoptionA_dec {A:Type} (eqA: relation A):
  Decider eqA -> Decider (leoptionA eqA).

Properties assuming Setoids

Section with_Setoid.

  Context {A} `{A_Setoid: Setoid A}.

  Instance leoptionA_preorder: PreOrder (leoptionA equiv).

  Instance leoptionA_partialorder: PartialOrder equiv (leoptionA equiv).

  Global Instance Some_compat : Proper (equiv ==> equiv) (@Some A).

  Global Instance None_compat : Proper equiv (@None A) := I.

  Context {B: Type} `{B_Setoid: Setoid B}.

  Global Instance option_rect_compat:
    Proper ((equiv (A := A) ==> equiv (A := B))
              ==> equiv ==> equiv ==> equiv) (option_rect (fun _=>B)).

  Global Instance option_map_compat:
    Proper ((equiv (A := A) ==> equiv (A := B))
              ==> equiv ==> equiv) (option_map (B := B)).

End with_Setoid.

Properties assuming Partial Setoids

Section with_PartialSetoid.

  Context {A} `{A_PartialSetoid: PartialSetoid A}.

  Global Instance Some_compat': Proper (pequiv ==> pequiv) (@Some A).

  Global Instance None_compat': Proper pequiv (@None A) := I.

  Context {B:Type} `{B_Psetoid: PartialSetoid B}.

  Global Instance option_rect_compat':
    Proper ((pequiv (A := A) ==> pequiv (A := B))
              ==> pequiv ==> pequiv ==> pequiv) (option_rect (fun _=>B)).

  Global Instance option_map_compat' {A B} eqA eqB:
    Proper ((eqA ==> eqB) ==> (eqoptionA eqA)
                          ==> (eqoptionA eqB)) (@option_map A B).

End with_PartialSetoid.

Unset Implicit Arguments.
Close Scope signature_scope.