Documentation

Init.Data.Ord

inductive Ordering :

Instances For

instance instInhabitedOrdering :

Inhabited Ordering

Equations

instInhabitedOrdering = { default := Ordering.lt }

instance instBEqOrdering :

Equations

instBEqOrdering = { beq := beqOrdering✝ }

instance Ordering.instDecidableEq :

DecidableEq Ordering

def Ordering.swap :

Ordering → Ordering

Swaps less and greater ordering results

@[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.eq.then x = x
x✝.then x = x✝

def Ordering.isEq :

Ordering → Bool

Check whether the ordering is 'equal'.

Equations

Ordering.eq.isEq = true
x.isEq = false

def Ordering.isNe :

Ordering → Bool

Check whether the ordering is 'not equal'.

def Ordering.isLE :

Ordering → Bool

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

Equations

Ordering.gt.isLE = false
x.isLE = true

def Ordering.isLT :

Ordering → Bool

Check whether the ordering is 'less than'.

def Ordering.isGT :

Ordering → Bool

Check whether the ordering is 'greater than'.

def Ordering.isGE :

Ordering → Bool

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

@[inline]

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

Yields an Ordering s.t. x < y corresponds to Ordering.lt / Ordering.gt and x = y corresponds to Ordering.eq.

Equations

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

@[inline]

def compareOfLessAndBEq {α : Type u_1} (x y : α) [LT α] [Decidable (x < y)] [BEq α] :

Yields an Ordering s.t. x < y corresponds to Ordering.lt / Ordering.gt and x == y corresponds to Ordering.eq.

Equations

compareOfLessAndBEq x y = if x < y then Ordering.lt else if (x == y) = true then Ordering.eq else Ordering.gt

@[inline]

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

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 = (cmp₁ a b).then (cmp₂ a b)

class Ord (α : Type u) :

Ord α provides a computable total order on α, in terms of the compare : α → α → Ordering function.

Typically instances will be transitive, reflexive, and antisymmetric, but this is not enforced by the typeclass.

There is a derive handler, so appending deriving Ord to an inductive type or structure will attempt to create an Ord instance.

compare : α → α → Ordering
Compare two elements in α using the comparator contained in an [Ord α] instance.

Instances

@[inline]

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

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

instance instOrdNat :

Equations

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

instance instOrdInt :

Equations

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

instance instOrdBool :

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 :

Equations

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

instance instOrdFin (n : Nat) :

instance instOrdUInt8 :

instance instOrdUInt16 :

instance instOrdUInt32 :

instance instOrdUInt64 :

Equations

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

instance instOrdUSize :

instance instOrdChar :

Equations

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

instance instOrdOption {α : Type u_1} [Ord α] :

Ord (Option α)

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

Ord (α × β)

The lexicographic order on pairs.

Equations

lexOrd = { compare := compareLex (compareOn fun (x : α × β) => x.fst) (compareOn fun (x : α × β) => x.snd) }

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

LT α

instance instDecidableRelLt {α : Type u_1} [Ord α] :

DecidableRel LT.lt

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

LE α

Equations

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

instance instDecidableRelLe {α : Type u_1} [Ord α] :

DecidableRel LE.le

Equations

instDecidableRelLe = inferInstanceAs (DecidableRel fun (a b : α) => (compare a b).isLE = true)

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

BEq α

Derive a BEq instance from an Ord instance.

def Ord.toLT {α : Type u_1} :

Ord α → LT α

Derive an LT instance from an Ord instance.

Equations

x.toLT = ltOfOrd

def Ord.toLE {α : Type u_1} :

Ord α → LE α

Derive an LE instance from an Ord instance.

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

Ord α

Invert the order of an Ord instance.

Equations

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

def Ord.on {β : Type u_1} {α : Type u_2} :

Ord β → (f : α → β) → Ord α

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

Equations

x.on 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

x✝.lex x = lexOrd

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

Ord α

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

def Ord.arrayOrd {α : Type u_1} [a : Ord α] :

Creates an order which compares elements of an Array in lexicographic order.