/-! # Lecture example: `add_all` `add_all xs c` adds `c` to every element of `xs`. Adding `a` and then adding `b` is the same as adding `a + b` once. -/ namespace LecEgOct10 def add_all (xs : List Int) (c : Int) : List Int := match xs with | [ ] => [ ] | hd::tl => (hd+c)::add_all tl c example : add_all [1, 2, 3] 10 = [11, 12, 13] := by rfl theorem add_all_nil (c : Int) : add_all [] c = [] := by rfl theorem add_all_cons (hd : Int) (tl : List Int) (c : Int) : add_all (hd :: tl) c = (hd+c) :: add_all tl c := by rfl theorem add_all_add_all (xs : List Int) (a b : Int) : add_all (add_all xs a) b = add_all xs (a+b) := by induction xs with | nil => -- Goal: add_all (add_all [] a) b = add_all [] (a+b) -- -- = add_all [ ] b (by evaluation of add_all) rw [add_all_nil a] -- = [ ] (by evaluation of add_all) rw [add_all_nil b] -- = add_all [ ] (a + b) (by evaluation of add_all) rw [add_all_nil (a+b)] | cons hd tl ih => -- ih : add_all (add_all tl a) b = add_all tl (a+b) -- Goal: add_all (add_all (hd :: tl) a) b = add_all (hd :: tl) (a+b) -- -- = add_all ((hd+a) :: add_all tl a) b (by eval inner add_all) rw [add_all_cons hd tl a] -- = (hd+a+b) :: (add_all (add_all tl a) b) (by eval outer add_all) rw [add_all_cons (hd+a) (add_all tl a) b] -- = (hd+a+b) :: add_all tl (a+b) (by IH) rw [ih] -- = (hd+(a+b)) :: add_all tl (a+b) (associativity of +) rw [Int.add_assoc] -- = add_all (hd::tl) (a+b) (by (reverse) eval of add_all) rw [← add_all_cons hd tl (a+b)] /-- The same theorem, with `dsimp` evaluating `add_all` instead of rewriting step by step with `add_all_nil` and `add_all_cons`. -/ theorem add_all_add_all' (xs : List Int) (a b : Int) : add_all (add_all xs a) b = add_all xs (a+b) := by induction xs with | nil => -- add_all (add_all [] a) b = [] = add_all [] (a+b) rfl | cons hd tl ih => -- ih : add_all (add_all tl a) b = add_all tl (a+b) -- dsimp only [add_all] only evaluates add_all and not the other -- functions such as + in the goal -- dsimp will evaluate multiple occurrences of add_all in the goal, -- so we don't have to rewrite multiple times -- dsimp also evaluates match statements and a few other basic things dsimp only [add_all] -- goal: (hd + a + b) :: add_all (add_all tl a) b -- = (hd + (a + b)) :: add_all tl (a + b) rw [ih] rw [Int.add_assoc] /-! ## Mapping over trees -/ inductive Tree (α : Type) | leaf | node (x : α) (l r : Tree α) def tm {α β : Type} (f : α → β) (t : Tree α) : Tree β := match t with | .leaf => .leaf | .node x l r => .node (f x) (tm f l) (tm f r) /-- Function composition. Lean's built-in `f ∘ g` (`Function.comp`) is defined exactly this way, so below we use `∘`. -/ def comp {α β γ : Type} (f : β → γ) (g : α → β) : α → γ := fun x => f (g x) -- f ∘ g example {α β γ : Type} (f : β → γ) (g : α → β) : comp f g = f ∘ g := by rfl theorem tm_leaf {α β : Type} (f : α → β) : tm f .leaf = .leaf := by rfl theorem tm_node {α β : Type} (f : α → β) (v : α) (l r : Tree α) : tm f (.node v l r) = .node (f v) (tm f l) (tm f r) := by rfl /-- Evaluating a composition applied to an argument. -/ theorem comp_eval {α β γ : Type} (f : β → γ) (g : α → β) (v : α) : (f ∘ g) v = f (g v) := by rfl theorem tm_tm {α β γ : Type} (f : β → γ) (g : α → β) (t : Tree α) : tm f (tm g t) = tm (f ∘ g) t := by induction t with | leaf => -- No inductive hypothesis to use. -- (leaf doesn't contain any smaller components with type Tree α.) -- -- tm f (tm g leaf) -- = tm f leaf (eval) rw [tm_leaf g] -- = leaf (eval) rw [tm_leaf f] -- = tm (f ∘ g) leaf (reverse eval) rw [← tm_leaf (f ∘ g)] | node v l r ih1 ih2 => -- IH1: tm f (tm g l) = tm (f ∘ g) l -- IH2: tm f (tm g r) = tm (f ∘ g) r -- -- tm f (tm g (node v l r)) -- = tm f (node (g v) (tm g l) (tm g r)) (eval inner tm) rw [tm_node g v l r] -- = node (f (g v)) (tm f (tm g l)) (tm f (tm g r)) (eval) rw [tm_node f (g v) (tm g l) (tm g r)] -- = node ((f ∘ g) v) (tm f (tm g l)) (tm f (tm g r)) (eval reverse) rw [← comp_eval f g v] -- = node ((f ∘ g) v) (tm (f ∘ g) l) (tm f (tm g r)) (IH1) rw [ih1] -- = node ((f ∘ g) v) (tm (f ∘ g) l) (tm (f ∘ g) r) (IH2) rw [ih2] -- = tm (f ∘ g) (node v l r) (eval reverse) rw [← tm_node (f ∘ g) v l r] end LecEgOct10