Theory Lookup2

theory Lookup2
imports Tree2 Cmp Map_by_Ordered
(* Author: Tobias Nipkow *)

section ‹Function \textit{lookup} for Tree2›

theory Lookup2
imports
  Tree2
  Cmp
  Map_by_Ordered
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