blob: e8cd89c3134afd0367295cf773b4a56bc97a7135 [file]
/-
Copyright (c) 2025 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Markus Himmel, Paul Reichert, Robin Arnez
-/
module
prelude
import Init.Data.List.Lemmas
import Init.Data.Array.DecidableEq
public import Init.Data.Ord.Array
public import Init.Data.BEq
public import Init.Data.Array.Basic
import Init.ByCases
import Init.Data.Bool
import Init.Data.Int.Order
import Init.Data.List.Nat.BEq
import Init.Data.Option.Lemmas
public section
/-!
# Type classes related to `Ord`
This file provides several typeclasses encode properties of an `Ord` instance. For each typeclass,
there is also a variant that does not depend on an `Ord` instance and takes an explicit comparison
function `cmp : α → α → Ordering` instead.
-/
set_option autoImplicit false
set_option linter.missingDocs true
universe u
namespace Std
section Refl
/-- A typeclass for comparison functions `cmp` for which `cmp a a = .eq` for all `a`. -/
class ReflCmp {α : Type u} (cmp : α → α → Ordering) : Prop where
/-- Comparison is reflexive. -/
compare_self {a : α} : cmp a a = .eq
namespace ReflCmp
theorem cmp_eq_of_eq {α : Type u} {cmp : α → α → Ordering} [Std.ReflCmp cmp] {a b : α} : a = b → cmp a b = .eq := by
intro h; subst a; apply compare_self
theorem ne_of_cmp_ne_eq {α : Type u} {cmp : α → α → Ordering} [Std.ReflCmp cmp] {a b : α} :
cmp a b ≠ .eq → a ≠ b :=
mt cmp_eq_of_eq
end ReflCmp
/-- A typeclass for ordered types for which `compare a a = .eq` for all `a`. -/
abbrev ReflOrd (α : Type u) [Ord α] := ReflCmp (compare : α → α → Ordering)
@[simp]
theorem ReflOrd.compare_self {α : Type u} [Ord α] [ReflOrd α] {a : α} : compare a a = .eq :=
ReflCmp.compare_self
theorem ReflCmp.isLE_rfl {α} {cmp : α → α → Ordering} [ReflCmp cmp] {a : α} :
(cmp a a).isLE := by
simp [ReflCmp.compare_self (cmp := cmp)]
@[simp]
theorem ReflOrd.isLE_rfl {α} [Ord α] [ReflOrd α] {a : α} :
(compare a a).isLE :=
ReflCmp.isLE_rfl
export ReflOrd (compare_self)
end Refl
section Oriented
/--
A typeclass for functions `α → α → Ordering` which are oriented: flipping the arguments amounts
to applying `Ordering.swap` to the return value.
-/
class OrientedCmp {α : Type u} (cmp : α → α → Ordering) : Prop where
/-- Swapping the arguments to `cmp` swaps the outcome. -/
eq_swap {a b : α} : cmp a b = (cmp b a).swap
/--
A typeclass for types with an oriented comparison function: flipping the arguments amounts to
applying `Ordering.swap` to the return value.
-/
abbrev OrientedOrd (α : Type u) [Ord α] := OrientedCmp (compare : α → α → Ordering)
variable {α : Type u} {cmp : α → α → Ordering}
theorem OrientedOrd.eq_swap [Ord α] [OrientedOrd α] {a b : α} :
compare a b = (compare b a).swap := OrientedCmp.eq_swap
instance [OrientedCmp cmp] : ReflCmp cmp where
compare_self := Ordering.eq_eq_of_eq_swap OrientedCmp.eq_swap
instance OrientedCmp.opposite [OrientedCmp cmp] : OrientedCmp fun a b => cmp b a where
eq_swap := OrientedCmp.eq_swap (cmp := cmp)
instance OrientedOrd.opposite [Ord α] [OrientedOrd α] : letI := Ord.opposite (α := α) ‹_›; OrientedOrd α :=
OrientedCmp.opposite (cmp := compare)
theorem OrientedCmp.gt_iff_lt [OrientedCmp cmp] {a b : α} : cmp a b = .gt ↔ cmp b a = .lt := by
rw [OrientedCmp.eq_swap (cmp := cmp) (a := a) (b := b)]
cases cmp b a <;> simp
theorem OrientedCmp.isGT_eq_isLT [OrientedCmp cmp] {a b : α} : (cmp a b).isGT = (cmp b a).isLT := by
rw [OrientedCmp.eq_swap (cmp := cmp) (a := a) (b := b), Ordering.isGT_swap]
theorem OrientedCmp.lt_of_gt [OrientedCmp cmp] {a b : α} : cmp a b = .gt → cmp b a = .lt :=
OrientedCmp.gt_iff_lt.1
theorem OrientedCmp.gt_of_lt [OrientedCmp cmp] {a b : α} : cmp a b = .lt → cmp b a = .gt :=
OrientedCmp.gt_iff_lt.2
theorem OrientedCmp.isGE_eq_isLE [OrientedCmp cmp] {a b : α} : (cmp a b).isGE = (cmp b a).isLE := by
rw [OrientedCmp.eq_swap (cmp := cmp), Ordering.isGE_swap]
theorem OrientedCmp.isGE_iff_isLE [OrientedCmp cmp] {a b : α} : (cmp a b).isGE ↔ (cmp b a).isLE :=
Bool.coe_iff_coe.mpr isGE_eq_isLE
theorem OrientedCmp.isLE_of_isGE [OrientedCmp cmp] {a b : α} : (cmp b a).isGE → (cmp a b).isLE :=
OrientedCmp.isGE_iff_isLE.1
theorem OrientedCmp.isGE_of_isLE [OrientedCmp cmp] {a b : α} : (cmp b a).isLE → (cmp a b).isGE :=
OrientedCmp.isGE_iff_isLE.2
theorem OrientedCmp.eq_comm [OrientedCmp cmp] {a b : α} : cmp a b = .eq ↔ cmp b a = .eq := by
rw [OrientedCmp.eq_swap (cmp := cmp) (a := a) (b := b)]
cases cmp b a <;> decide
theorem OrientedCmp.eq_symm [OrientedCmp cmp] {a b : α} : cmp a b = .eq → cmp b a = .eq :=
OrientedCmp.eq_comm.1
theorem OrientedCmp.not_isLE_of_lt [OrientedCmp cmp] {a b : α} :
cmp a b = .lt → ¬ (cmp b a).isLE := by
rw [OrientedCmp.eq_swap (cmp := cmp) (a := a) (b := b)]
simp
theorem OrientedCmp.not_isGE_of_gt [OrientedCmp cmp] {a b : α} :
cmp a b = .gt → ¬ (cmp b a).isGE := by
rw [OrientedCmp.eq_swap (cmp := cmp) (a := a) (b := b)]
simp
theorem OrientedCmp.not_lt_of_isLE [OrientedCmp cmp] {a b : α} :
(cmp a b).isLE → cmp b a ≠ .lt := by
rw [OrientedCmp.eq_swap (cmp := cmp) (a := a) (b := b)]
cases cmp b a <;> simp
theorem OrientedCmp.not_gt_of_isGE [OrientedCmp cmp] {a b : α} :
(cmp a b).isGE → cmp b a ≠ .gt := by
rw [OrientedCmp.eq_swap (cmp := cmp) (a := a) (b := b)]
cases cmp b a <;> simp
theorem OrientedCmp.not_lt_of_lt [OrientedCmp cmp] {a b : α} :
cmp a b = .lt → cmp b a ≠ .lt := by
rw [OrientedCmp.eq_swap (cmp := cmp) (a := a) (b := b)]
cases cmp b a <;> simp
theorem OrientedCmp.not_gt_of_gt [OrientedCmp cmp] {a b : α} :
cmp a b = .gt → cmp b a ≠ .gt := by
rw [OrientedCmp.eq_swap (cmp := cmp) (a := a) (b := b)]
cases cmp b a <;> simp
theorem OrientedCmp.lt_of_not_isLE [OrientedCmp cmp] {a b : α} :
¬ (cmp a b).isLE → cmp b a = .lt := by
rw [OrientedCmp.eq_swap (cmp := cmp) (a := a) (b := b)]
cases cmp b a <;> simp
theorem OrientedCmp.gt_of_not_isGE [OrientedCmp cmp] {a b : α} :
¬ (cmp a b).isGE → cmp b a = .gt := by
rw [OrientedCmp.eq_swap (cmp := cmp) (a := a) (b := b)]
cases cmp b a <;> simp
theorem OrientedCmp.isLE_antisymm [OrientedCmp cmp] {a b : α} (h₁ : cmp a b |>.isLE) (h₂ : cmp b a |>.isLE) :
cmp a b = .eq := by
rw [OrientedCmp.eq_swap (cmp := cmp)] at h₂
cases h : cmp a b <;> rw [h] at h₁ h₂ <;> simp at h₁ h₂
theorem OrientedCmp.isGE_antisymm [OrientedCmp cmp] {a b : α} (h₁ : cmp a b |>.isGE) (h₂ : cmp b a |>.isGE) :
cmp a b = .eq := by
rw [OrientedCmp.eq_swap (cmp := cmp)] at h₂
cases h : cmp a b <;> rw [h] at h₁ h₂ <;> simp at h₁ h₂
end Oriented
section Trans
/-- A typeclass for functions `α → α → Ordering` which are transitive. -/
class TransCmp {α : Type u} (cmp : α → α → Ordering) : Prop extends OrientedCmp cmp where
/-- Transitivity of `cmp`, expressed via `Ordering.isLE`. -/
isLE_trans {a b c : α} : (cmp a b).isLE → (cmp b c).isLE → (cmp a c).isLE
/-- A typeclass for types with a transitive ordering function. -/
abbrev TransOrd (α : Type u) [Ord α] := TransCmp (compare : α → α → Ordering)
variable {α : Type u} {cmp : α → α → Ordering}
theorem TransOrd.isLE_trans [Ord α] [TransOrd α] {a b c : α} :
(compare a b).isLE → (compare b c).isLE → (compare a c).isLE :=
TransCmp.isLE_trans
theorem TransCmp.isGE_trans [TransCmp cmp] {a b c : α} (h₁ : (cmp a b).isGE) (h₂ : (cmp b c).isGE) :
(cmp a c).isGE := by
rw [OrientedCmp.isGE_iff_isLE] at *
exact TransCmp.isLE_trans h₂ h₁
theorem TransOrd.isGE_trans [Ord α] [TransOrd α] {a b c : α} :
(compare a b).isGE → (compare b c).isGE → (compare a c).isGE :=
TransCmp.isGE_trans
instance TransCmp.opposite [TransCmp cmp] : TransCmp fun a b => cmp b a where
isLE_trans := flip TransCmp.isLE_trans
instance TransOrd.opposite [Ord α] [TransOrd α] : letI := Ord.opposite (α := α) ‹_›; TransOrd α :=
TransCmp.opposite (cmp := compare)
theorem TransCmp.lt_of_lt_of_eq [TransCmp cmp] {a b c : α} (hab : cmp a b = .lt)
(hbc : cmp b c = .eq) : cmp a c = .lt := by
apply OrientedCmp.lt_of_not_isLE
intro hca
suffices cmp a b ≠ .lt from absurd hab this
exact OrientedCmp.not_lt_of_isLE (TransCmp.isLE_trans (Ordering.isLE_of_eq_eq hbc) hca)
theorem TransCmp.lt_of_eq_of_lt [TransCmp cmp] {a b c : α} (hab : cmp a b = .eq)
(hbc : cmp b c = .lt) : cmp a c = .lt := by
apply OrientedCmp.lt_of_not_isLE
intro hca
suffices cmp b c ≠ .lt from absurd hbc this
exact OrientedCmp.not_lt_of_isLE (TransCmp.isLE_trans hca (Ordering.isLE_of_eq_eq hab))
theorem TransCmp.gt_of_eq_of_gt [TransCmp cmp] {a b c : α} (hab : cmp a b = .eq)
(hbc : cmp b c = .gt) : cmp a c = .gt := by
rw [OrientedCmp.gt_iff_lt] at *
exact TransCmp.lt_of_lt_of_eq hbc (OrientedCmp.eq_symm hab)
theorem TransCmp.gt_of_gt_of_eq [TransCmp cmp] {a b c : α} (hab : cmp a b = .gt)
(hbc : cmp b c = .eq) : cmp a c = .gt := by
rw [OrientedCmp.gt_iff_lt] at *
exact TransCmp.lt_of_eq_of_lt (OrientedCmp.eq_symm hbc) hab
theorem TransCmp.lt_trans [TransCmp cmp] {a b c : α} (hab : cmp a b = .lt) (hbc : cmp b c = .lt) :
cmp a c = .lt := by
cases hac : cmp a c
· rfl
· suffices cmp a b ≠ .lt from absurd hab this
exact OrientedCmp.not_lt_of_isLE (TransCmp.isLE_trans (Ordering.isLE_of_eq_lt hbc)
(Ordering.isLE_of_eq_eq (OrientedCmp.eq_symm hac)))
· suffices cmp a b ≠ .lt from absurd hab this
exact OrientedCmp.not_lt_of_isLE (TransCmp.isLE_trans (Ordering.isLE_of_eq_lt hbc)
(Ordering.isLE_of_eq_lt (OrientedCmp.lt_of_gt hac)))
theorem TransCmp.gt_trans [TransCmp cmp] {a b c : α} (hab : cmp a b = .gt) (hbc : cmp b c = .gt) :
cmp a c = .gt := by
rw [OrientedCmp.gt_iff_lt (cmp := cmp)] at *
exact lt_trans hbc hab
theorem TransCmp.lt_of_lt_of_isLE [TransCmp cmp] {a b c : α} (hab : cmp a b = .lt)
(hbc : (cmp b c).isLE) : cmp a c = .lt := by
rw [Ordering.isLE_iff_eq_lt_or_eq_eq] at hbc
obtain hbc|hbc := hbc
· exact TransCmp.lt_trans hab hbc
· exact TransCmp.lt_of_lt_of_eq hab hbc
theorem TransCmp.lt_of_isLE_of_lt [TransCmp cmp] {a b c : α} (hab : (cmp a b).isLE)
(hbc : cmp b c = .lt) : cmp a c = .lt := by
rw [Ordering.isLE_iff_eq_lt_or_eq_eq] at hab
obtain hab|hab := hab
· exact TransCmp.lt_trans hab hbc
· exact TransCmp.lt_of_eq_of_lt hab hbc
theorem TransCmp.gt_of_gt_of_isGE [TransCmp cmp] {a b c : α} (hab : cmp a b = .gt)
(hbc : (cmp b c).isGE) : cmp a c = .gt := by
rw [OrientedCmp.gt_iff_lt, OrientedCmp.isGE_iff_isLE] at *
exact TransCmp.lt_of_isLE_of_lt hbc hab
@[deprecated TransCmp.gt_trans (since := "2025-10-26")]
theorem TransCmp.gt_of_gt_of_gt [TransCmp cmp] {a b c : α} (hab : cmp a b = .gt)
(hbc : cmp b c = .gt) : cmp a c = .gt := by
apply gt_of_gt_of_isGE hab (Ordering.isGE_of_eq_gt hbc)
theorem TransCmp.gt_of_isGE_of_gt [TransCmp cmp] {a b c : α} (hab : (cmp a b).isGE)
(hbc : cmp b c = .gt) : cmp a c = .gt := by
rw [OrientedCmp.gt_iff_lt, OrientedCmp.isGE_iff_isLE] at *
exact TransCmp.lt_of_lt_of_isLE hbc hab
theorem TransCmp.eq_trans [TransCmp cmp] {a b c : α} (hab : cmp a b = .eq)
(hbc : cmp b c = .eq) : cmp a c = .eq := by
apply Ordering.eq_eq_of_isLE_of_isLE_swap
· exact TransCmp.isLE_trans (Ordering.isLE_of_eq_eq hab) (Ordering.isLE_of_eq_eq hbc)
· rw [← OrientedCmp.eq_swap]
exact TransCmp.isLE_trans (Ordering.isLE_of_eq_eq (OrientedCmp.eq_symm hbc))
(Ordering.isLE_of_eq_eq (OrientedCmp.eq_symm hab))
theorem TransCmp.congr_left [TransCmp cmp] {a b c : α} (hab : cmp a b = .eq) :
cmp a c = cmp b c := by
cases hbc : cmp b c with
| lt => exact TransCmp.lt_of_eq_of_lt hab hbc
| eq => exact TransCmp.eq_trans hab hbc
| gt =>
exact OrientedCmp.gt_of_lt
(TransCmp.lt_of_lt_of_eq (OrientedCmp.lt_of_gt hbc) (OrientedCmp.eq_symm hab))
theorem TransCmp.congr_right [TransCmp cmp] {a b c : α} (hbc : cmp b c = .eq) :
cmp a b = cmp a c := by
cases hab : cmp a b with
| lt => exact TransCmp.lt_of_lt_of_eq hab hbc |>.symm
| eq => exact TransCmp.eq_trans hab hbc |>.symm
| gt =>
exact OrientedCmp.gt_of_lt
(TransCmp.lt_of_eq_of_lt (OrientedCmp.eq_symm hbc) (OrientedCmp.lt_of_gt hab)) |>.symm
end Trans
section LawfulEq
/--
A typeclass for comparison functions satisfying `cmp a b = .eq` if and only if the logical equality
`a = b` holds.
This typeclass distinguishes itself from `LawfulBEqCmp` by using logical equality (`=`) instead of
boolean equality (`==`).
-/
class LawfulEqCmp {α : Type u} (cmp : α → α → Ordering) : Prop extends ReflCmp cmp where
/-- If two values compare equal, then they are logically equal. -/
eq_of_compare {a b : α} : cmp a b = .eq → a = b
/--
A typeclass for types with a comparison function that satisfies `compare a b = .eq` if and only if
the logical equality `a = b` holds.
This typeclass distinguishes itself from `LawfulBEqOrd` by using logical equality (`=`) instead of
boolean equality (`==`).
-/
abbrev LawfulEqOrd (α : Type u) [Ord α] := LawfulEqCmp (compare : α → α → Ordering)
variable {α : Type u} {cmp : α → α → Ordering} [LawfulEqCmp cmp]
theorem LawfulEqOrd.eq_of_compare [Ord α] [LawfulEqOrd α] {a b : α} :
compare a b = .eq → a = b := LawfulEqCmp.eq_of_compare
instance LawfulEqCmp.opposite [OrientedCmp cmp] [LawfulEqCmp cmp] :
LawfulEqCmp (fun a b => cmp b a) where
eq_of_compare := by
simp only [OrientedCmp.eq_comm (cmp := cmp)]
exact LawfulEqCmp.eq_of_compare
instance LawfulEqOrd.opposite [Ord α] [OrientedOrd α] [LawfulEqOrd α] :
letI := Ord.opposite (α := α) ‹_›; LawfulEqOrd α :=
LawfulEqCmp.opposite (cmp := compare)
@[simp]
theorem LawfulEqCmp.compare_eq_iff_eq {a b : α} : cmp a b = .eq ↔ a = b :=
⟨LawfulEqCmp.eq_of_compare, fun h => h ▸ ReflCmp.compare_self⟩
theorem LawfulEqCmp.compare_beq_iff_eq {a b : α} : cmp a b == .eq ↔ a = b :=
beq_iff_eq.trans compare_eq_iff_eq
/-- The corresponding lemma for `LawfulEqCmp` is `LawfulEqCmp.compare_eq_iff_eq` -/
@[simp, grind =]
theorem LawfulEqOrd.compare_eq_iff_eq [Ord α] [LawfulEqOrd α] {a b : α} :
compare a b = .eq ↔ a = b :=
LawfulEqCmp.compare_eq_iff_eq
/-- The corresponding lemma for `LawfulEqCmp` is `LawfulEqCmp.compare_beq_iff_eq` -/
@[grind =]
theorem LawfulEqOrd.compare_beq_iff_eq [Ord α] [LawfulEqOrd α] {a b : α} :
compare a b == .eq ↔ a = b :=
LawfulEqCmp.compare_beq_iff_eq
export LawfulEqOrd (compare_eq_iff_eq compare_beq_iff_eq)
end LawfulEq
section LawfulBEq
/--
A typeclass for comparison functions satisfying `cmp a b = .eq` if and only if the boolean equality
`a == b` holds.
This typeclass distinguishes itself from `LawfulEqCmp` by using boolean equality (`==`) instead of
logical equality (`=`).
-/
class LawfulBEqCmp {α : Type u} [BEq α] (cmp : α → α → Ordering) : Prop where
/-- If two values compare equal, then they are boolean equal. -/
compare_eq_iff_beq {a b : α} : cmp a b = .eq ↔ a == b
theorem LawfulBEqCmp.not_compare_eq_iff_beq_eq_false {α : Type u} [BEq α] {cmp}
[LawfulBEqCmp (α := α) cmp] {a b : α} : ¬ cmp a b = .eq ↔ (a == b) = false := by
rw [Bool.eq_false_iff, ne_eq, not_congr]
exact compare_eq_iff_beq
theorem LawfulBEqCmp.compare_beq_eq_beq {α : Type u} [BEq α] {cmp}
[LawfulBEqCmp (α := α) cmp] {a b : α} : (cmp a b == .eq) = (a == b) := by
rw [Bool.eq_iff_iff, beq_iff_eq, compare_eq_iff_beq]
theorem LawfulBEqCmp.isEq_compare_eq_beq {α : Type u} [BEq α] {cmp}
[LawfulBEqCmp (α := α) cmp] {a b : α} : (cmp a b).isEq = (a == b) := by
rw [Bool.eq_iff_iff, Ordering.isEq_iff_eq_eq, compare_eq_iff_beq]
/--
A typeclass for types with a comparison function that satisfies `compare a b = .eq` if and only if
the boolean equality `a == b` holds.
This typeclass distinguishes itself from `LawfulEqOrd` by using boolean equality (`==`) instead of
logical equality (`=`).
-/
abbrev LawfulBEqOrd (α : Type u) [BEq α] [Ord α] := LawfulBEqCmp (compare : α → α → Ordering)
variable {α : Type u} [BEq α] {cmp : α → α → Ordering}
theorem LawfulBEqOrd.compare_eq_iff_beq {α : Type u} {_ : Ord α} {_ : BEq α}
[LawfulBEqOrd α] {a b : α} : compare a b = .eq ↔ (a == b) = true :=
LawfulBEqCmp.compare_eq_iff_beq
theorem LawfulBEqOrd.not_compare_eq_iff_beq_eq_false {α : Type u} {_ : BEq α} {_ : Ord α}
[LawfulBEqOrd α] {a b : α} : ¬ compare a b = .eq ↔ (a == b) = false :=
LawfulBEqCmp.not_compare_eq_iff_beq_eq_false
theorem LawfulBEqOrd.compare_beq_eq_beq {α : Type u} {_ : Ord α} {_ : BEq α}
[LawfulBEqOrd α] {a b : α} : (compare a b == .eq) = (a == b) :=
LawfulBEqCmp.compare_beq_eq_beq
theorem LawfulBEqOrd.isEq_compare_eq_beq {α : Type u} {_ : Ord α} {_ : BEq α}
[LawfulBEqOrd α] {a b : α} : (compare a b).isEq = (a == b) :=
LawfulBEqCmp.isEq_compare_eq_beq
export LawfulBEqOrd (compare_eq_iff_beq not_compare_eq_iff_beq_eq_false
compare_beq_eq_beq isEq_compare_eq_beq)
instance [LawfulEqCmp cmp] [LawfulBEq α] : LawfulBEqCmp cmp where
compare_eq_iff_beq := LawfulEqCmp.compare_eq_iff_eq.trans beq_iff_eq.symm
theorem LawfulBEqCmp.reflBEq [inst : LawfulBEqCmp cmp] [ReflCmp cmp] : ReflBEq α where
rfl := inst.compare_eq_iff_beq.mp ReflCmp.compare_self
theorem LawfulBEqCmp.equivBEq [inst : LawfulBEqCmp cmp] [TransCmp cmp] : EquivBEq α where
toReflBEq := reflBEq (cmp := cmp)
symm := by
simp only [← inst.compare_eq_iff_beq]
exact OrientedCmp.eq_symm
trans := by
simp only [← inst.compare_eq_iff_beq]
exact TransCmp.eq_trans
instance LawfulBEqOrd.equivBEq [Ord α] [LawfulBEqOrd α] [TransOrd α] : EquivBEq α :=
LawfulBEqCmp.equivBEq (cmp := compare)
theorem LawfulBEqCmp.lawfulBEq [inst : LawfulBEqCmp cmp] [LawfulEqCmp cmp] : LawfulBEq α where
toReflBEq := reflBEq (cmp := cmp)
eq_of_beq := by simp [← inst.compare_eq_iff_beq]
instance LawfulBEqOrd.lawfulBEq [Ord α] [LawfulBEqOrd α] [LawfulEqOrd α] : LawfulBEq α :=
LawfulBEqCmp.lawfulBEq (cmp := compare)
instance LawfulBEqCmp.lawfulEqCmp [inst : LawfulBEqCmp cmp] [LawfulBEq α] : LawfulEqCmp cmp where
compare_self := by simp only [compare_eq_iff_beq, beq_self_eq_true, implies_true]
eq_of_compare := by simp only [compare_eq_iff_beq, beq_iff_eq, imp_self, implies_true]
theorem LawfulBEqOrd.lawfulEqOrd [Ord α] [LawfulBEqOrd α] [LawfulBEq α] : LawfulEqOrd α :=
LawfulBEqCmp.lawfulEqCmp
instance LawfulBEqCmp.opposite [OrientedCmp cmp] [LawfulBEqCmp cmp] :
LawfulBEqCmp (fun a b => cmp b a) where
compare_eq_iff_beq := by
simp [OrientedCmp.eq_comm (cmp := cmp), LawfulBEqCmp.compare_eq_iff_beq]
instance LawfulBEqOrd.opposite [Ord α] [OrientedOrd α] [LawfulBEqOrd α] :
letI := Ord.opposite (α := α) ‹_›; LawfulBEqOrd α :=
LawfulBEqCmp.opposite (cmp := compare)
end LawfulBEq
attribute [local instance] beqOfOrd in
instance {α : Type u} {_ : Ord α} : LawfulBEqOrd α where
compare_eq_iff_beq {a b} := by simp only [BEq.beq, Ordering.isEq_iff_eq_eq]
end Std
section Instances
open Std
theorem Std.TransOrd.compareOfLessAndEq_of_lt_trans_of_lt_iff
{α : Type u} [LT α] [DecidableLT α] [DecidableEq α]
(lt_trans : ∀ {a b c : α}, a < b → b < c → a < c)
(h : ∀ x y : α, x < y ↔ ¬ y < x ∧ x ≠ y) :
TransCmp (fun x y : α => compareOfLessAndEq x y) where
eq_swap := compareOfLessAndEq_eq_swap_of_lt_iff_not_gt_and_ne h
isLE_trans {x y z} h₁ h₂ := by
simp only [compareOfLessAndEq, apply_ite Ordering.isLE,
Ordering.isLE_lt, Ordering.isLE_eq, Ordering.isLE_gt] at h₁ h₂ ⊢
simp only [Bool.if_true_left, Bool.or_false, Bool.or_eq_true, decide_eq_true_eq] at h₁ h₂ ⊢
rcases h₁ with (h₁ | rfl)
· rcases h₂ with (h₂ | rfl)
· exact .inl (lt_trans h₁ h₂)
· exact .inl h₁
· exact h₂
theorem Std.TransOrd.compareOfLessAndEq_of_antisymm_of_trans_of_total_of_not_le
{α : Type u} [LT α] [LE α] [DecidableLT α] [DecidableLE α] [DecidableEq α]
(antisymm : ∀ {x y : α}, x ≤ y → y ≤ x → x = y)
(trans : ∀ {x y z : α}, x ≤ y → y ≤ z → x ≤ z) (total : ∀ (x y : α), x ≤ y ∨ y ≤ x)
(not_le : ∀ {x y : α}, ¬ x ≤ y ↔ y < x) :
TransCmp (fun x y : α => compareOfLessAndEq x y) := by
refine compareOfLessAndEq_of_lt_trans_of_lt_iff ?_ ?_
· intro a b c
simp only [← not_le]
intro h₁ h₂ h₃
replace h₁ := (total _ _).resolve_left h₁
exact h₂ (trans h₃ h₁)
· exact lt_iff_not_gt_and_ne_of_antisymm_of_total_of_not_le antisymm total not_le
namespace Bool
instance : TransOrd Bool where
eq_swap {x y} := by cases x <;> cases y <;> rfl
isLE_trans {x y z} h₁ h₂ := by cases x <;> cases y <;> cases z <;> trivial
instance : LawfulEqOrd Bool where
eq_of_compare {x y} := by cases x <;> cases y <;> simp
end Bool
namespace Nat
instance : TransOrd Nat :=
TransOrd.compareOfLessAndEq_of_antisymm_of_trans_of_total_of_not_le
Nat.le_antisymm Nat.le_trans Nat.le_total Nat.not_le
instance : LawfulEqOrd Nat where
eq_of_compare := compareOfLessAndEq_eq_eq Nat.le_refl Nat.not_le |>.mp
end Nat
namespace Int
instance : TransOrd Int :=
TransOrd.compareOfLessAndEq_of_antisymm_of_trans_of_total_of_not_le
Int.le_antisymm Int.le_trans Int.le_total Int.not_le
instance : LawfulEqOrd Int where
eq_of_compare := compareOfLessAndEq_eq_eq Int.le_refl Int.not_le |>.mp
end Int
namespace Fin
variable (n : Nat)
instance : OrientedOrd (Fin n) where
eq_swap := OrientedOrd.eq_swap (α := Nat)
instance : TransOrd (Fin n) where
isLE_trans := TransOrd.isLE_trans (α := Nat)
instance : LawfulEqOrd (Fin n) where
eq_of_compare h := Fin.eq_of_val_eq <| LawfulEqOrd.eq_of_compare h
end Fin
namespace Option
instance {α} [Ord α] [OrientedOrd α] : OrientedOrd (Option α) where
eq_swap {a b} := by cases a <;> cases b <;> simp [Ord.compare, ← OrientedOrd.eq_swap]
instance {α} [Ord α] [TransOrd α] : TransOrd (Option α) where
isLE_trans {a b c} hab hbc := by
cases a <;> cases b <;> cases c <;> (try simp_all [Ord.compare]; done)
simp only [Ord.compare] at *
apply TransOrd.isLE_trans <;> assumption
instance {α} [Ord α] [ReflOrd α] : ReflOrd (Option α) where
compare_self {a} := by cases a <;> simp [Ord.compare]
instance {α} [Ord α] [LawfulEqOrd α] : LawfulEqOrd (Option α) where
eq_of_compare {a b} := by
cases a <;> cases b <;> simp [Ord.compare]
instance {α} [Ord α] [BEq α] [LawfulBEqOrd α] : LawfulBEqOrd (Option α) where
compare_eq_iff_beq {a b} := by
cases a <;> cases b <;> simp [Ord.compare, compare_eq_iff_beq]
end Option
namespace Std
section Lex
instance {α} {cmp₁ cmp₂} [ReflCmp cmp₁] [ReflCmp cmp₂] :
ReflCmp (α := α) (compareLex cmp₁ cmp₂) where
compare_self {a} := by simp [compareLex, ReflCmp.compare_self]
instance {α} {cmp₁ cmp₂} [OrientedCmp cmp₁] [OrientedCmp cmp₂] :
OrientedCmp (α := α) (compareLex cmp₁ cmp₂) where
eq_swap {a b} := by
rw [compareLex, compareLex, OrientedCmp.eq_swap (cmp := cmp₁) (a := b), Ordering.swap_then,
Ordering.swap_swap, ← OrientedCmp.eq_swap]
instance {α} {cmp₁ cmp₂} [TransCmp cmp₁] [TransCmp cmp₂] :
TransCmp (α := α) (compareLex cmp₁ cmp₂) where
isLE_trans {a b c} hab hbc := by
simp only [compareLex] at *
simp only [Ordering.isLE_then_iff_and] at *
refine ⟨TransCmp.isLE_trans hab.1 hbc.1, ?_⟩
cases hab.2
case inl hab' => exact Or.inl <| TransCmp.lt_of_lt_of_isLE hab' hbc.1
case inr hab' =>
cases hbc.2
case inl hbc' => exact Or.inl <| TransCmp.lt_of_isLE_of_lt hab.1 hbc'
case inr hbc' => exact Or.inr <| TransCmp.isLE_trans hab' hbc'
instance {α β} {f : α → β} [Ord β] [ReflOrd β] :
ReflCmp (compareOn f) where
compare_self := ReflOrd.compare_self (α := β)
instance {α β} {f : α → β} [Ord β] [OrientedOrd β] :
OrientedCmp (compareOn f) where
eq_swap := OrientedOrd.eq_swap (α := β)
instance {α β} {f : α → β} [Ord β] [TransOrd β] :
TransCmp (compareOn f) where
isLE_trans := TransOrd.isLE_trans (α := β)
attribute [local instance] lexOrd
instance {α β} [Ord α] [Ord β] [ReflOrd α] [ReflOrd β] :
ReflOrd (α × β) :=
inferInstanceAs <| ReflCmp (compareLex _ _)
instance {α β} [Ord α] [Ord β] [OrientedOrd α] [OrientedOrd β] :
OrientedOrd (α × β) :=
inferInstanceAs <| OrientedCmp (compareLex _ _)
instance {α β} [Ord α] [Ord β] [TransOrd α] [TransOrd β] :
TransOrd (α × β) :=
inferInstanceAs <| TransCmp (compareLex _ _)
instance {α β} [Ord α] [Ord β] [LawfulEqOrd α] [LawfulEqOrd β] : LawfulEqOrd (α × β) where
eq_of_compare {a b} h := by
simp only [compare, compareLex_eq_eq, compareOn] at h
ext
· exact LawfulEqOrd.eq_of_compare h.1
· exact LawfulEqOrd.eq_of_compare h.2
end Lex
end Std
end Instances
namespace List
open Std
variable {α} {cmp : α → α → Ordering}
instance [ReflCmp cmp] : ReflCmp (List.compareLex cmp) where
compare_self {a} := by
induction a with
| nil => rfl
| cons x xs h =>
simp [List.compareLex_cons_cons, ReflCmp.compare_self, h]
instance [LawfulEqCmp cmp] : LawfulEqCmp (List.compareLex cmp) where
eq_of_compare {a b} h := by
induction a generalizing b with
| nil => simpa [List.compareLex_nil_left_eq_eq] using h
| cons x xs ih =>
cases b
· simp [List.compareLex_nil_right_eq_eq] at h
· simp only [List.compareLex_cons_cons, Ordering.then_eq_eq, LawfulEqCmp.compare_eq_iff_eq,
List.cons.injEq] at *
exact ⟨h.1, ih h.2⟩
instance [BEq α] [LawfulBEqCmp cmp] : LawfulBEqCmp (List.compareLex cmp) where
compare_eq_iff_beq {a b} := by
induction a generalizing b with
| nil => simp [List.compareLex_nil_left_eq_eq]
| cons x xs ih =>
cases b
· simp [List.compareLex_cons_nil]
· simp [List.compareLex_cons_cons, Ordering.then_eq_eq, LawfulBEqCmp.compare_eq_iff_beq, ih]
instance [OrientedCmp cmp] : OrientedCmp (List.compareLex cmp) where
eq_swap {a b} := by
induction a generalizing b with
| nil =>
cases b
· simp [List.compareLex_nil_nil]
· simp [List.compareLex_nil_cons, List.compareLex_cons_nil]
| cons x xs ih =>
cases b
· simp [List.compareLex_nil_cons, List.compareLex_cons_nil]
· simp [OrientedCmp.eq_swap (a := x), List.compareLex_cons_cons, ih, Ordering.swap_then]
instance [TransCmp cmp] : TransCmp (List.compareLex cmp) where
isLE_trans {a b c} (hab hbc) := by
induction a generalizing b c with
| nil => exact List.isLE_compareLex_nil_left
| cons _ _ ih =>
cases b <;> cases c <;> (try simp [List.compareLex_cons_nil] at *; done)
simp only [List.compareLex_cons_cons, Ordering.isLE_then_iff_and] at *
apply And.intro
· exact TransCmp.isLE_trans hab.1 hbc.1
· obtain ⟨hable, (hab | hab)⟩ := hab
· exact Or.inl <| TransCmp.lt_of_lt_of_isLE hab hbc.1
· obtain ⟨_, (hbc | hbc)⟩ := hbc
· exact Or.inl <| TransCmp.lt_of_isLE_of_lt hable hbc
· exact Or.inr <| ih hab hbc
instance [Ord α] [ReflOrd α] : ReflOrd (List α) :=
inferInstanceAs <| ReflCmp (List.compareLex compare)
instance [Ord α] [LawfulEqOrd α] : LawfulEqOrd (List α) :=
inferInstanceAs <| LawfulEqCmp (List.compareLex compare)
instance [Ord α] [BEq α] [LawfulBEqOrd α] : LawfulBEqOrd (List α) :=
inferInstanceAs <| LawfulBEqCmp (List.compareLex compare)
instance [Ord α] [OrientedOrd α] : OrientedOrd (List α) :=
inferInstanceAs <| OrientedCmp (List.compareLex compare)
instance [Ord α] [TransOrd α] : TransOrd (List α) :=
inferInstanceAs <| TransCmp (List.compareLex compare)
end List
namespace Array
open Std
variable {α} {cmp : α → α → Ordering}
instance [ReflCmp cmp] : ReflCmp (Array.compareLex cmp) where
compare_self {a} := by simp [Array.compareLex_eq_compareLex_toList, ReflCmp.compare_self]
instance [LawfulEqCmp cmp] : LawfulEqCmp (Array.compareLex cmp) where
eq_of_compare {a b} := by
simp only [Array.compareLex_eq_compareLex_toList, LawfulEqCmp.compare_eq_iff_eq]
exact congrArg List.toArray
instance [BEq α] [LawfulBEqCmp cmp] : LawfulBEqCmp (Array.compareLex cmp) where
compare_eq_iff_beq {a b} := by
simp only [Array.compareLex_eq_compareLex_toList, BEq.beq, ← Array.isEqv_toList,
LawfulBEqCmp.compare_eq_iff_beq, List.beq_eq_isEqv]
instance [OrientedCmp cmp] : OrientedCmp (Array.compareLex cmp) where
eq_swap {a b} := by simp [Array.compareLex_eq_compareLex_toList, ← OrientedCmp.eq_swap]
instance [TransCmp cmp] : TransCmp (Array.compareLex cmp) where
isLE_trans {a b c} hab hac := by
simp only [Array.compareLex_eq_compareLex_toList] at *
exact TransCmp.isLE_trans hab hac
instance [Ord α] [ReflOrd α] : ReflOrd (Array α) :=
inferInstanceAs <| ReflCmp (Array.compareLex compare)
instance [Ord α] [LawfulEqOrd α] : LawfulEqOrd (Array α) :=
inferInstanceAs <| LawfulEqCmp (Array.compareLex compare)
instance [Ord α] [BEq α] [LawfulBEqOrd α] : LawfulBEqOrd (Array α) :=
inferInstanceAs <| LawfulBEqCmp (Array.compareLex compare)
instance [Ord α] [OrientedOrd α] : OrientedOrd (Array α) :=
inferInstanceAs <| OrientedCmp (Array.compareLex compare)
instance [Ord α] [TransOrd α] : TransOrd (Array α) :=
inferInstanceAs <| TransCmp (Array.compareLex compare)
end Array