inductive Ordering : Type

• lt: Ordering
• eq: Ordering
• gt: Ordering

instance instInhabitedOrdering : Inhabited Ordering

Equations

• instInhabitedOrdering = { default := Ordering.lt }

instance instBEqOrdering : BEq Ordering

Equations

• instBEqOrdering = { beq := beqOrdering✝ }

instance Ordering.instDecidableEqOrdering : DecidableEq Ordering

Equations

• Ordering.instDecidableEqOrdering x y = if h : Ordering.toCtorIdx x = Ordering.toCtorIdx y then isTrue ⋯ else isFalse ⋯

def Ordering.swap : Ordering → Ordering

Swaps less and greater ordering results

Equations

• Ordering.swap x = match x with | Ordering.lt => Ordering.gt | Ordering.eq => Ordering.eq | Ordering.gt => Ordering.lt

@[macro_inline]

def Ordering.then : Ordering → Ordering → Ordering

If o₁ and o₂ are Ordering, then o₁.then o₂ returns o₁ unless it is .eq, in which case it returns o₂. Additionally, it has "short-circuiting" semantics similar to boolean x && y: if o₁ is not .eq then the expression for o₂ is not evaluated. This is a useful primitive for constructing lexicographic comparator functions:

structure Person where
  name : String
  age : Nat

instance : Ord Person where
  compare a b := (compare a.name b.name).then (compare b.age a.age)

This example will sort people first by name (in ascending order) and will sort people with the same name by age (in descending order). (If all fields are sorted ascending and in the same order as they are listed in the structure, you can also use deriving Ord on the structure definition for the same effect.)

Equations

• Ordering.then x✝ x = match x✝, x with | Ordering.eq, f => f | o, x => o

def Ordering.isEq : Ordering → Bool

Check whether the ordering is 'equal'.

Equations

• Ordering.isEq x = match x with | Ordering.eq => true | x => false

def Ordering.isNe : Ordering → Bool

Check whether the ordering is 'not equal'.

Equations

• Ordering.isNe x = match x with | Ordering.eq => false | x => true

def Ordering.isLE : Ordering → Bool

Check whether the ordering is 'less than or equal to'.

Equations

• Ordering.isLE x = match x with | Ordering.gt => false | x => true

def Ordering.isLT : Ordering → Bool

Check whether the ordering is 'less than'.

Equations

• Ordering.isLT x = match x with | Ordering.lt => true | x => false

def Ordering.isGT : Ordering → Bool

Check whether the ordering is 'greater than'.

Equations

• Ordering.isGT x = match x with | Ordering.gt => true | x => false

def Ordering.isGE : Ordering → Bool

Check whether the ordering is 'greater than or equal'.

Equations

• Ordering.isGE x = match x with | Ordering.lt => false | x => true

@[inline]

def compareOfLessAndEq {α : Type u_1} (x : α) (y : α) [LT α] [Decidable (x < y)] [DecidableEq α] : Ordering

Equations

• compareOfLessAndEq x y = if x < y then Ordering.lt else if x = y then Ordering.eq else Ordering.gt

@[inline]

def compareLex {α : Sort u_1} {β : Sort u_2} (cmp₁ : α → β → Ordering) (cmp₂ : α → β → Ordering) (a : α) (b : β) : Ordering

Compare a and b lexicographically by cmp₁ and cmp₂. a and b are first compared by cmp₁. If this returns 'equal', a and b are compared by cmp₂ to break the tie.

Equations

• compareLex cmp₁ cmp₂ a b = Ordering.then (cmp₁ a b) (cmp₂ a b)

class Ord (α : Type u) : Type u

• compare : α → α → Ordering

@[inline]

def compareOn {β : Type u_1} {α : Sort u_2} [ord : Ord β] (f : α → β) (x : α) (y : α) : Ordering

Compare x and y by comparing f x and f y.

Equations

• compareOn f x y = compare (f x) (f y)

instance instOrdNat : Ord Nat

Equations

• instOrdNat = { compare := fun (x y : Nat) => compareOfLessAndEq x y }

instance instOrdInt : Ord Int

Equations

• instOrdInt = { compare := fun (x y : Int) => compareOfLessAndEq x y }

instance instOrdBool : Ord Bool

Equations

• instOrdBool = { compare := fun (x x_1 : Bool) => match x, x_1 with | false, true => Ordering.lt | true, false => Ordering.gt | x, x_2 => Ordering.eq }

instance instOrdString : Ord String

Equations

• instOrdString = { compare := fun (x y : String) => compareOfLessAndEq x y }

instance instOrdFin (n : Nat) : Ord (Fin n)

Equations

• instOrdFin n = { compare := fun (x y : Fin n) => compare ↑x ↑y }

instance instOrdUInt8 : Ord UInt8

Equations

• instOrdUInt8 = { compare := fun (x y : UInt8) => compareOfLessAndEq x y }

instance instOrdUInt16 : Ord UInt16

Equations

• instOrdUInt16 = { compare := fun (x y : UInt16) => compareOfLessAndEq x y }

instance instOrdUInt32 : Ord UInt32

Equations

• instOrdUInt32 = { compare := fun (x y : UInt32) => compareOfLessAndEq x y }

instance instOrdUInt64 : Ord UInt64

Equations

• instOrdUInt64 = { compare := fun (x y : UInt64) => compareOfLessAndEq x y }

instance instOrdUSize : Ord USize

Equations

• instOrdUSize = { compare := fun (x y : USize) => compareOfLessAndEq x y }

instance instOrdChar : Ord Char

Equations

• instOrdChar = { compare := fun (x y : Char) => compareOfLessAndEq x y }

def lexOrd {α : Type u_1} {β : Type u_2} [Ord α] [Ord β] : Ord (α × β)

The lexicographic order on pairs.

Equations

• lexOrd = { compare := fun (p1 p2 : α × β) => match compare p1.fst p2.fst with | Ordering.eq => compare p1.snd p2.snd | o => o }

def ltOfOrd {α : Type u_1} [Ord α] : LT α

Equations

• ltOfOrd = { lt := fun (a b : α) => (compare a b == Ordering.lt) = true }

instance instDecidableRelLtLtOfOrd {α : Type u_1} [Ord α] : DecidableRel LT.lt

Equations

• instDecidableRelLtLtOfOrd = inferInstanceAs (DecidableRel fun (a b : α) => (compare a b == Ordering.lt) = true)

def leOfOrd {α : Type u_1} [Ord α] : LE α

Equations

• leOfOrd = { le := fun (a b : α) => Ordering.isLE (compare a b) = true }

instance instDecidableRelLeLeOfOrd {α : Type u_1} [Ord α] : DecidableRel LE.le

Equations

• instDecidableRelLeLeOfOrd = inferInstanceAs (DecidableRel fun (a b : α) => Ordering.isLE (compare a b) = true)

def Ord.toBEq {α : Type u_1} (ord : Ord α) : BEq α

Derive a BEq instance from an Ord instance.

Equations

• Ord.toBEq ord = { beq := fun (x y : α) => compare x y == Ordering.eq }

def Ord.toLT {α : Type u_1} : Ord α → LT α

Derive an LT instance from an Ord instance.

Equations

• Ord.toLT x = ltOfOrd

def Ord.toLE {α : Type u_1} : Ord α → LE α

Derive an LE instance from an Ord instance.

Equations

• Ord.toLE x = leOfOrd

def Ord.opposite {α : Type u_1} (ord : Ord α) : Ord α

Invert the order of an Ord instance.

Equations

• Ord.opposite ord = { compare := fun (x y : α) => compare y x }

def Ord.on {β : Type u_1} {α : Type u_2} (ord : Ord β) (f : α → β) : Ord α

ord.on f compares x and y by comparing f x and f y according to ord.

Equations

• Ord.on ord f = { compare := compareOn f }

def Ord.lex {α : Type u_1} {β : Type u_2} : Ord α → Ord β → Ord (α × β)

Derive the lexicographic order on products α × β from orders for α and β.

Equations

• Ord.lex x✝ x = lexOrd

def Ord.lex' {α : Type u_1} (ord₁ : Ord α) (ord₂ : Ord α) : Ord α

Create an order which compares elements first by ord₁ and then, if this returns 'equal', by ord₂.

Equations

• Ord.lex' ord₁ ord₂ = { compare := compareLex compare compare }