(* Author: Tobias Nipkow *) section ‹Function \textit{lookup} for Tree2› theory Lookup2 imports Tree2 Cmp Map_Specs begin fun lookup :: "('a::linorder * 'b, 'c) tree ⇒ 'a ⇒ 'b option" where "lookup Leaf x = None" | "lookup (Node l (a,b) _ r) x = (case cmp x a of LT ⇒ lookup l x | GT ⇒ lookup r x | EQ ⇒ Some b)" lemma lookup_map_of: "sorted1(inorder t) ⟹ lookup t x = map_of (inorder t) x" by(induction t) (auto simp: map_of_simps split: option.split) end