This file contains a collection definitions and theorems about lists that are not part of Lean's standard library. At least when initially writing some of these, suitable variants did not exist or I simply did not find them.

Some cleanup is certainly needed here.

def CustomBasicDatastructures.List.toSet {α : Type u_1} (l : List α) : Set α

We can convert a list to a set by defining membership in the set through membership in the list.

Equations

• CustomBasicDatastructures.List.toSet l e = (e ∈ l)

@[simp]

theorem CustomBasicDatastructures.List.mem_toSet {α : Type u_1} {l : List α} {e : α} : e ∈ toSet l ↔ e ∈ l

Membership does not change across the toSet conversion.

theorem CustomBasicDatastructures.List.getElem_mem_toSet {α : Type u_1} (l : List α) (i : Fin l.length) : l[i] ∈ toSet l

For each valid index, the list element at that index is also in toSet.

@[simp]

theorem CustomBasicDatastructures.List.map_toSet_eq_toSet_map {α : Type u_1} {β : Type u_2} {l : List α} {f : α → β} : (toSet l).map f = toSet (List.map f l)

Converting a list to a set and then applying a function to each element is the same as first applyign the function and then converting to the set.

theorem CustomBasicDatastructures.List.mem_toSet_map_of_mem_toSet {α : Type u_1} {β : Type u_2} {l : List α} {e : α} {f : α → β} : e ∈ toSet l → f e ∈ toSet (List.map f l)

For each element of l.toSet, the mapped version of that element is in the set obtained from the mapped list.

theorem CustomBasicDatastructures.List.sum_take_le_sum (l : List Nat) (i : Fin (l.length + 1)) : (List.take (↑i) l).sum ≤ l.sum

The sum of taking any number of elements from a list cannot exceed the sum over the whole list.

theorem CustomBasicDatastructures.List.neg_all_of_any_neg {α : Type u_1} (l : List α) (p : α → Bool) : (l.any fun (a : α) => decide ¬p a = true) = true → ¬l.all p = true

Converts any with a negated predicate into a negated call to all with a positive predicate.

theorem CustomBasicDatastructures.List.append_args_eq_of_append_eq_of_same_length {α : Type u_1} {as bs cs ds : List α} (h : as.length = cs.length) : as ++ bs = cs ++ ds → as = cs ∧ bs = ds

Components of two append calls are equal if the appended lists are equal and the first components have the same length.

theorem CustomBasicDatastructures.List.append_eq_append_of_parts_eq {α : Type u_1} (as bs cs ds : List α) : as = cs → bs = ds → as ++ bs = cs ++ ds

Two lists resulting from append calls are equal if the individual components are equal.

theorem CustomBasicDatastructures.List.append_left_same_length_of_append_eq_append_of_right_same_length {α : Type u_1} {as bs cs ds : List α} : as ++ bs = cs ++ ds → bs.length = ds.length → as.length = cs.length

If two lists resulting from append calls are equal and the second components have the same length, then the first components also have the same length.

theorem CustomBasicDatastructures.List.head_cons_tail_of_ne_nil {α : Type u_1} {l : List α} (h : l ≠ []) : l = l.head h :: l.tail

A non-empty list can be split into its head and tail.

theorem CustomBasicDatastructures.List.mem_iff_append_and_not_in_first {α : Type u_1} [DecidableEq α] (l : List α) (e : α) : e ∈ l ↔ ∃ (as : List α), ∃ (bs : List α), l = as ++ e :: bs ∧ ¬e ∈ as

An element is in a list if and only if the list is composable such the element has its first occurrence in this composition.

theorem CustomBasicDatastructures.List.map_id_of_id_on_all_mem {α : Type u_1} (l : List α) (f : α → α) (id_on_all_mem : ∀ (e : α), e ∈ l → f e = e) : List.map f l = l

Mapping over list produces the same list if the mapping function maps each list member to itself. Note that this is very close to List.map_id'' but that List.map_id'' has a stronger assumption. Namely it requires the function to be the id not only on list elements but on every representant of the element type.

theorem CustomBasicDatastructures.List.filter_eq_of_all_eq {α : Type u_1} (l : List α) (p q : α → Bool) : (∀ (e : α), e ∈ l → p e = q e) → List.filter p l = List.filter q l

Filtering a list based on two predicates yields the same list if the predicates behave the same on all elements.

@[simp]

theorem CustomBasicDatastructures.List.eq_iff_unattach_eq {α : Type u} {p : α → Prop} {as bs : List { x : α // p x }} : as.unattach = bs.unattach ↔ as = bs

Lists over subtypes are equal if and only if their unattached versions are equal.

theorem CustomBasicDatastructures.List.contains_dup_of_exceeding_nodup_list_with_same_elements {α : Type u_1} [DecidableEq α] (as bs : List α) (nodup_as : as.Nodup) (len_lt : as.length < bs.length) (contains_all : bs ⊆ as) : ¬bs.Nodup

A list that is longer than a list without duplicates but only contains the same elements must have a duplicate.

theorem CustomBasicDatastructures.List.filter_eq_of_eq {α : Type u_1} {as bs : List α} : as = bs → ∀ (f : α → Bool), List.filter f as = List.filter f bs

For two equal lists, filter does the same.

theorem CustomBasicDatastructures.List.map_eq_of_eq {α : Type u_1} {β : Type u_2} {as bs : List α} : as = bs → ∀ (f : α → β), List.map f as = List.map f bs

For two equal lists, map does the same.

theorem CustomBasicDatastructures.List.flatten_eq_of_eq {α : Type u_1} {as bs : List (List α)} : as = bs → as.flatten = bs.flatten

For two equal lists, flatten does the same.

theorem CustomBasicDatastructures.List.getElem_eq_getElem_of_idx_eq {α : Type u_1} {l : List α} {i j : Nat} {i_lt : i < l.length} (idx_eq : i = j) : l[i] = l[j]

Elements at equal indices are the same.

theorem CustomBasicDatastructures.List.getElem_idxOf_of_mem {α : Type u_1} [BEq α] [LawfulBEq α] {l : List α} {e : α} (mem : e ∈ l) : l[List.idxOf e l] = e

We getting the element at the index of a given element e, we obtain exactly e. Note that this depends on LawfulBEq.

theorem CustomBasicDatastructures.List.idxOf_getElem {α : Type u_1} [DecidableEq α] {l : List α} {i : Nat} {lt : i < l.length} (nodup : l.Nodup) : List.idxOf l[i] l = i

The index of an element that we get from given index is exactly this index. Note that this uses DecidableEq.