Lemmas about association lists

Each operation on AssocList is specified by a lemma relating it to the corresponding operation on List (α × β), transported along AssocList.toList.

@[simp]

theorem Batteries.AssocList.empty_eq {α : Type u_1} {β : Type u_2} : ∅ = nil

@[simp]

theorem Batteries.AssocList.isEmpty_eq {α : Type u_1} {β : Type u_2} (l : AssocList α β) : l.isEmpty = l.toList.isEmpty

@[simp]

theorem Batteries.AssocList.length_nil {α : Type u_1} {β : Type u_2} : nil.length = 0

@[simp]

theorem Batteries.AssocList.length_cons {α✝ : Type u_1} {a : α✝} {β✝ : Type u_2} {b : β✝} {t : AssocList α✝ β✝} : (cons a b t).length = t.length + 1

theorem Batteries.AssocList.length_toList {α : Type u_1} {β : Type u_2} (l : AssocList α β) : l.toList.length = l.length

@[simp]

theorem Batteries.AssocList.forM_eq {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_4} [Monad m] (f : α → β → m PUnit) (l : AssocList α β) : forM f l = l.toList.forM fun (x : α × β) => match x with | (a, b) => f a b

@[simp]

theorem Batteries.AssocList.toList_mapKey {α : Type u_1} {δ : Type u_2} {β : Type u_3} (f : α → δ) (l : AssocList α β) : (mapKey f l).toList = List.map (fun (x : α × β) => match x with | (a, b) => (f a, b)) l.toList

@[simp]

theorem Batteries.AssocList.length_mapKey {α✝ : Type u_1} {α✝¹ : Type u_2} {f : α✝ → α✝¹} {β✝ : Type u_3} {l : AssocList α✝ β✝} : (mapKey f l).length = l.length

@[simp]

theorem Batteries.AssocList.toList_mapVal {α : Type u_1} {β : Type u_2} {δ : Type u_3} (f : α → β → δ) (l : AssocList α β) : (mapVal f l).toList = List.map (fun (x : α × β) => match x with | (a, b) => (a, f a b)) l.toList

@[simp]

theorem Batteries.AssocList.length_mapVal {α✝ : Type u_1} {β✝ : Type u_2} {β✝¹ : Type u_3} {f : α✝ → β✝ → β✝¹} {l : AssocList α✝ β✝} : (mapVal f l).length = l.length

@[simp]

theorem Batteries.AssocList.filterMapVal_nil {α✝ : Type u_1} {β✝ : Type u_2} {α✝¹ : Type u_3} {f : α✝ → β✝ → Option α✝¹} : filterMapVal f nil = nil

theorem Batteries.AssocList.filterMapVal_cons {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : α → β → Option γ) (k : α) (v : β) (t : AssocList α β) : filterMapVal f (cons k v t) = match f k v with | none => filterMapVal f t | some d => cons k d (filterMapVal f t)

@[simp]

theorem Batteries.AssocList.toList_filterMapVal {α : Type u_1} {β : Type u_2} {δ : Type u_3} (f : α → β → Option δ) (l : AssocList α β) : (filterMapVal f l).toList = List.filterMap (fun (x : α × β) => match x with | (a, b) => Option.map (fun (v : δ) => (a, v)) (f a b)) l.toList

theorem Batteries.AssocList.length_filterMapVal_le {α✝ : Type u_1} {β✝ : Type u_2} {α✝¹ : Type u_3} {f : α✝ → β✝ → Option α✝¹} {l : AssocList α✝ β✝} : (filterMapVal f l).length ≤ l.length

@[simp]

theorem Batteries.AssocList.findEntryP?_eq {α : Type u_1} {β : Type u_2} (p : α → β → Bool) (l : AssocList α β) : findEntryP? p l = List.find? (fun (x : α × β) => match x with | (a, b) => p a b) l.toList

@[simp]

theorem Batteries.AssocList.findEntry?_eq {α : Type u_1} {β : Type u_2} [BEq α] (a : α) (l : AssocList α β) : findEntry? a l = List.find? (fun (x : α × β) => x.fst == a) l.toList

theorem Batteries.AssocList.find?_eq_findEntry? {α : Type u_1} {β : Type u_2} [BEq α] (a : α) (l : AssocList α β) : find? a l = Option.map (fun (x : α × β) => x.snd) (findEntry? a l)

@[simp]

theorem Batteries.AssocList.find?_eq {α : Type u_1} {β : Type u_2} [BEq α] (a : α) (l : AssocList α β) : find? a l = Option.map (fun (x : α × β) => x.snd) (List.find? (fun (x : α × β) => x.fst == a) l.toList)

theorem Batteries.AssocList.find?_mapVal {α : Type u_1} {β : Type u_2} {γ : Type u_3} [BEq α] [LawfulBEq α] (f : α → β → γ) (a : α) (l : AssocList α β) : find? a (mapVal f l) = Option.map (f a) (find? a l)

@[simp]

theorem Batteries.AssocList.any_eq {α : Type u_1} {β : Type u_2} (p : α → β → Bool) (l : AssocList α β) : any p l = l.toList.any fun (x : α × β) => match x with | (a, b) => p a b

@[simp]

theorem Batteries.AssocList.all_eq {α : Type u_1} {β : Type u_2} (p : α → β → Bool) (l : AssocList α β) : all p l = l.toList.all fun (x : α × β) => match x with | (a, b) => p a b

@[simp]

theorem Batteries.AssocList.contains_eq {α : Type u_1} {β : Type u_2} [BEq α] (a : α) (l : AssocList α β) : contains a l = l.toList.any fun (x : α × β) => x.fst == a

@[simp]

theorem Batteries.AssocList.toList_replace {α : Type u_1} {β : Type u_2} [BEq α] (a : α) (b : β) (l : AssocList α β) : (replace a b l).toList = List.replaceF (fun (x : α × β) => bif x.fst == a then some (a, b) else none) l.toList

@[simp]

theorem Batteries.AssocList.length_replace {α : Type u_1} {β✝ : Type u_2} {b : β✝} {l : AssocList α β✝} [BEq α] {a : α} : (replace a b l).length = l.length

@[simp]

theorem Batteries.AssocList.toList_eraseP {α : Type u_1} {β : Type u_2} (p : α → β → Bool) (l : AssocList α β) : (eraseP p l).toList = List.eraseP (fun (x : α × β) => match x with | (a, b) => p a b) l.toList

@[simp]

theorem Batteries.AssocList.toList_erase {α : Type u_1} {β : Type u_2} [BEq α] (a : α) (l : AssocList α β) : (erase a l).toList = List.eraseP (fun (x : α × β) => x.fst == a) l.toList

@[simp]

theorem Batteries.AssocList.toList_modify {α : Type u_1} {β : Type u_2} {f : α → β → β} [BEq α] (a : α) (l : AssocList α β) : (modify a f l).toList = List.replaceF (fun (x : α × β) => match x with | (k, v) => bif k == a then some (a, f k v) else none) l.toList

@[simp]

theorem Batteries.AssocList.length_modify {α : Type u_1} {β✝ : Type u_2} {f : α → β✝ → β✝} {l : AssocList α β✝} [BEq α] {a : α} : (modify a f l).length = l.length

@[simp]

theorem Batteries.AssocList.forIn_eq {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_4} {δ : Type u_1} [Monad m] (l : AssocList α β) (init : δ) (f : α × β → δ → m (ForInStep δ)) : forIn l init f = forIn l.toList init f

@[simp]

theorem List.toList_toAssocList {α : Type u_1} {β : Type u_2} (l : List (α × β)) : l.toAssocList.toList = l

@[simp]

theorem Batteries.AssocList.toList_toAssocList {α : Type u_1} {β : Type u_2} (l : AssocList α β) : l.toList.toAssocList = l

@[simp]

theorem List.length_toAssocList {α : Type u_1} {β : Type u_2} (l : List (α × β)) : l.toAssocList.length = l.length

@[simp]

theorem Batteries.AssocList.beq_nil₂ {α : Type u_1} {β : Type u_2} [BEq α] [BEq β] : (nil == nil) = true

@[simp]

theorem Batteries.AssocList.beq_nil_cons {α : Type u_1} {β : Type u_2} {a : α} {b : β} {t : AssocList α β} [BEq α] [BEq β] : (nil == cons a b t) = false

@[simp]

theorem Batteries.AssocList.beq_cons_nil {α : Type u_1} {β : Type u_2} {a : α} {b : β} {t : AssocList α β} [BEq α] [BEq β] : (cons a b t == nil) = false

@[simp]

theorem Batteries.AssocList.beq_cons₂ {α : Type u_1} {β : Type u_2} {a : α} {b : β} {t : AssocList α β} {a' : α} {b' : β} {t' : AssocList α β} [BEq α] [BEq β] : (cons a b t == cons a' b' t') = (a == a' && b == b' && t == t')

instance Batteries.AssocList.instLawfulBEq {α : Type u_1} {β : Type u_2} [BEq α] [LawfulBEq α] [BEq β] [LawfulBEq β] : LawfulBEq (AssocList α β)

theorem Batteries.AssocList.beq_eq {α : Type u_1} {β : Type u_2} [BEq α] [BEq β] {l m : AssocList α β} : (l == m) = (l.toList == m.toList)