Lemmas about List.min? and `List.max?.

Minima and maxima

min?

@[simp]

theorem List.min?_nil {α : Type u_1} [Min α] : [].min? = none

@[simp]

theorem List.min?_singleton {α : Type u_1} [Min α] {x : α} : [x].min? = some x

theorem List.min?_cons' {α : Type u_1} {x : α} [Min α] {xs : List α} : (x :: xs).min? = some (foldl min x xs)

@[simp]

theorem List.min?_cons {α : Type u_1} {x : α} [Min α] [Std.Associative min] {xs : List α} : (x :: xs).min? = some (xs.min?.elim x (min x))

@[simp]

theorem List.min?_eq_none_iff {α : Type u_1} {xs : List α} [Min α] : xs.min? = none ↔ xs = []

@[simp]

theorem List.isSome_min?_iff {α : Type u_1} [Min α] {xs : List α} : xs.min?.isSome = true ↔ xs ≠ []

theorem List.isSome_min?_of_mem {α : Type u_1} {l : List α} [Min α] {a : α} (h : a ∈ l) : l.min?.isSome = true

theorem List.isSome_min?_of_ne_nil {α : Type u_1} [Min α] {l : List α} (hl : l ≠ []) : l.min?.isSome = true

theorem List.min?_eq_head? {α : Type u} [Min α] {l : List α} (h : Pairwise (fun (a b : α) => min a b = a) l) : l.min? = l.head?

theorem List.min?_mem {α : Type u_1} {a : α} [Min α] [Std.MinEqOr α] {xs : List α} : xs.min? = some a → a ∈ xs

theorem List.le_min?_iff {α : Type u_1} {a : α} [Min α] [LE α] [Std.LawfulOrderInf α] {xs : List α} : xs.min? = some a → ∀ {x : α}, x ≤ a ↔ ∀ (b : α), b ∈ xs → x ≤ b

theorem List.min?_eq_some_iff {α : Type u_1} {a : α} [Min α] [LE α] {xs : List α} [Std.IsLinearOrder α] [Std.LawfulOrderMin α] : xs.min? = some a ↔ a ∈ xs ∧ ∀ (b : α), b ∈ xs → a ≤ b

theorem List.min?_eq_min?_attach {α : Type u_1} [Min α] [Std.MinEqOr α] {xs : List α} : xs.min? = Option.map Subtype.val xs.attach.min?

theorem List.min?_eq_some_iff_subtype {α : Type u_1} {a : α} [Min α] [LE α] {xs : List α} [Std.MinEqOr α] [Std.IsLinearOrder { x : α // x ∈ xs }] [Std.LawfulOrderMin { x : α // x ∈ xs }] : xs.min? = some a ↔ a ∈ xs ∧ ∀ (b : α), b ∈ xs → a ≤ b

theorem List.min?_replicate {α : Type u_1} [Min α] [Std.IdempotentOp min] {n : Nat} {a : α} : (replicate n a).min? = if n = 0 then none else some a

@[simp]

theorem List.min?_replicate_of_pos {α : Type u_1} [Min α] [Std.MinEqOr α] {n : Nat} {a : α} (h : 0 < n) : (replicate n a).min? = some a

theorem List.foldl_min {α : Type u_1} [Min α] [Std.IdempotentOp min] [Std.Associative min] {l : List α} {a : α} : foldl min a l = min a (l.min?.getD a)

This lemma is also applicable given the following instances:

[LE α] [Min α] [IsLinearOrder α] [LawfulOrderMin α]

min

@[simp]

theorem List.min_singleton {α : Type u_1} [Min α] {x : α} : [x].min ⋯ = x

theorem List.min_cons_cons {α : Type u_1} [Min α] {a b : α} {l : List α} : (a :: b :: l).min ⋯ = (min a b :: l).min ⋯

theorem List.min_cons {α : Type u_1} [Min α] [Std.Associative min] {a : α} {l : List α} {h : a :: l ≠ []} : (a :: l).min h = l.min?.elim a fun (x : α) => min a x

@[simp]

theorem List.min_cons_cons_nil {α : Type u_1} [Min α] {a b : α} : [a, b].min ⋯ = min a b

theorem List.min?_eq_some_min {α : Type u_1} [Min α] {l : List α} (hl : l ≠ []) : l.min? = some (l.min hl)

theorem List.min_eq_get_min? {α : Type u_1} [Min α] (l : List α) (hl : l ≠ []) : l.min hl = l.min?.get ⋯

@[simp]

theorem List.get_min? {α : Type u_1} [Min α] {l : List α} {h : l.min?.isSome = true} : l.min?.get h = l.min ⋯

theorem List.min_eq_head {α : Type u} [Min α] {l : List α} (hl : l ≠ []) (h : Pairwise (fun (a b : α) => min a b = a) l) : l.min hl = l.head hl

theorem List.min_mem {α : Type u_1} [Min α] [Std.MinEqOr α] {l : List α} (hl : l ≠ []) : l.min hl ∈ l

theorem List.min_le_of_mem {α : Type u_1} [Min α] [LE α] [Std.IsLinearOrder α] [Std.LawfulOrderMin α] {l : List α} {a : α} (ha : a ∈ l) : l.min ⋯ ≤ a

theorem List.le_min_iff {α : Type u_1} [Min α] [LE α] [Std.LawfulOrderInf α] {l : List α} (hl : l ≠ []) {x : α} : x ≤ l.min hl ↔ ∀ (b : α), b ∈ l → x ≤ b

theorem List.min_eq_iff {α : Type u_1} {a : α} [Min α] [LE α] {l : List α} [Std.IsLinearOrder α] [Std.LawfulOrderMin α] (hl : l ≠ []) : l.min hl = a ↔ a ∈ l ∧ ∀ (b : α), b ∈ l → a ≤ b

@[simp]

theorem List.min_replicate {α : Type u_1} [Min α] [Std.MinEqOr α] {n : Nat} {a : α} (h : replicate n a ≠ []) : (replicate n a).min h = a

theorem List.foldl_min_eq_min {α : Type u_1} [Min α] [Std.IdempotentOp min] [Std.Associative min] {l : List α} (hl : l ≠ []) {a : α} : foldl min a l = min a (l.min hl)

max?

@[simp]

theorem List.max?_nil {α : Type u_1} [Max α] : [].max? = none

@[simp]

theorem List.max?_singleton {α : Type u_1} [Max α] {x : α} : [x].max? = some x

theorem List.max?_cons' {α : Type u_1} {x : α} [Max α] {xs : List α} : (x :: xs).max? = some (foldl max x xs)

@[simp]

theorem List.max?_cons {α : Type u_1} {x : α} [Max α] [Std.Associative max] {xs : List α} : (x :: xs).max? = some (xs.max?.elim x (max x))

@[simp]

theorem List.max?_eq_none_iff {α : Type u_1} {xs : List α} [Max α] : xs.max? = none ↔ xs = []

@[simp]

theorem List.isSome_max?_iff {α : Type u_1} [Max α] {xs : List α} : xs.max?.isSome = true ↔ xs ≠ []

theorem List.isSome_max?_of_mem {α : Type u_1} {l : List α} [Max α] {a : α} (h : a ∈ l) : l.max?.isSome = true

theorem List.isSome_max?_of_ne_nil {α : Type u_1} [Max α] {l : List α} (hl : l ≠ []) : l.max?.isSome = true

theorem List.max?_eq_head? {α : Type u} [Max α] {l : List α} (h : Pairwise (fun (a b : α) => max a b = a) l) : l.max? = l.head?

theorem List.max?_mem {α : Type u_1} {a : α} [Max α] [Std.MaxEqOr α] {xs : List α} : xs.max? = some a → a ∈ xs

theorem List.max?_le_iff {α : Type u_1} {a : α} [Max α] [LE α] [Std.LawfulOrderSup α] {xs : List α} : xs.max? = some a → ∀ {x : α}, a ≤ x ↔ ∀ (b : α), b ∈ xs → b ≤ x

theorem List.max?_eq_some_iff {α : Type u_1} {a : α} [Max α] [LE α] {xs : List α} [Std.IsLinearOrder α] [Std.LawfulOrderMax α] : xs.max? = some a ↔ a ∈ xs ∧ ∀ (b : α), b ∈ xs → b ≤ a

theorem List.max?_eq_max?_attach {α : Type u_1} [Max α] [Std.MaxEqOr α] {xs : List α} : xs.max? = Option.map Subtype.val xs.attach.max?

theorem List.max?_eq_some_iff_subtype {α : Type u_1} {a : α} [Max α] [LE α] {xs : List α} [Std.MaxEqOr α] [Std.IsLinearOrder { x : α // x ∈ xs }] [Std.LawfulOrderMax { x : α // x ∈ xs }] : xs.max? = some a ↔ a ∈ xs ∧ ∀ (b : α), b ∈ xs → b ≤ a

@[deprecated List.max?_eq_some_iff (since := "2025-08-01")]

theorem List.max?_eq_some_iff_legacy {α : Type u_1} {a : α} [Max α] [LE α] [anti : Std.Antisymm fun (x1 x2 : α) => x1 ≤ x2] (le_refl : ∀ (a : α), a ≤ a) (max_eq_or : ∀ (a b : α), max a b = a ∨ max a b = b) (max_le_iff : ∀ (a b c : α), max b c ≤ a ↔ b ≤ a ∧ c ≤ a) {xs : List α} : xs.max? = some a ↔ a ∈ xs ∧ ∀ (b : α), b ∈ xs → b ≤ a

theorem List.max?_replicate {α : Type u_1} [Max α] [Std.IdempotentOp max] {n : Nat} {a : α} : (replicate n a).max? = if n = 0 then none else some a

@[simp]

theorem List.max?_replicate_of_pos {α : Type u_1} [Max α] [Std.MaxEqOr α] {n : Nat} {a : α} (h : 0 < n) : (replicate n a).max? = some a

theorem List.foldl_max {α : Type u_1} [Max α] [Std.IdempotentOp max] [Std.Associative max] {l : List α} {a : α} : foldl max a l = max a (l.max?.getD a)

This lemma is also applicable given the following instances:

[LE α] [Min α] [IsLinearOrder α] [LawfulOrderMax α]

max

@[simp]

theorem List.max_singleton {α : Type u_1} [Max α] {x : α} : [x].max ⋯ = x

theorem List.max_cons_cons {α : Type u_1} [Max α] {a b : α} {l : List α} : (a :: b :: l).max ⋯ = (max a b :: l).max ⋯

theorem List.max_cons {α : Type u_1} [Max α] [Std.Associative max] {a : α} {l : List α} {h : a :: l ≠ []} : (a :: l).max h = l.max?.elim a fun (x : α) => max a x

@[simp]

theorem List.max_cons_cons_nil {α : Type u_1} [Max α] {a b : α} : [a, b].max ⋯ = max a b

theorem List.max?_eq_some_max {α : Type u_1} [Max α] {l : List α} (hl : l ≠ []) : l.max? = some (l.max hl)

theorem List.max_eq_get_max? {α : Type u_1} [Max α] (l : List α) (hl : l ≠ []) : l.max hl = l.max?.get ⋯

@[simp]

theorem List.get_max? {α : Type u_1} [Max α] {l : List α} {h : l.max?.isSome = true} : l.max?.get h = l.max ⋯

theorem List.max_eq_head {α : Type u} [Max α] {l : List α} (hl : l ≠ []) (h : Pairwise (fun (a b : α) => max a b = a) l) : l.max hl = l.head hl

theorem List.max_mem {α : Type u_1} [Max α] [Std.MaxEqOr α] {l : List α} (hl : l ≠ []) : l.max hl ∈ l

theorem List.max_le_iff {α : Type u_1} [Max α] [LE α] [Std.LawfulOrderSup α] {l : List α} (hl : l ≠ []) {x : α} : l.max hl ≤ x ↔ ∀ (b : α), b ∈ l → b ≤ x

theorem List.max_eq_iff {α : Type u_1} {a : α} [Max α] [LE α] {l : List α} [Std.IsLinearOrder α] [Std.LawfulOrderMax α] (hl : l ≠ []) : l.max hl = a ↔ a ∈ l ∧ ∀ (b : α), b ∈ l → b ≤ a

theorem List.le_max_of_mem {α : Type u_1} [Max α] [LE α] [Std.IsLinearOrder α] [Std.LawfulOrderMax α] {l : List α} {a : α} (ha : a ∈ l) : a ≤ l.max ⋯

@[simp]

theorem List.max_replicate {α : Type u_1} [Max α] [Std.MaxEqOr α] {n : Nat} {a : α} (h : replicate n a ≠ []) : (replicate n a).max h = a

theorem List.foldl_max_eq_max {α : Type u_1} [Max α] [Std.IdempotentOp max] [Std.Associative max] {l : List α} (hl : l ≠ []) {a : α} : foldl max a l = max a (l.max hl)