(* CS 212, Spring 2001 *)
(* Jeannette Wing and Joshua Dunfield *)

(* Code for Recitation 7 (28 Feb 2001) *)

datatype 'a tree = Leaf of 'a | Node of 'a tree * 'a tree
datatype path = H          (* "here" -- end of the path *)
              | L of path  (* L(p) means "go left, then follow path p" *)
              | R of path  (* R(p) means "go right, then follow path p" *)

(*
val t1 = Node(Node(Leaf 1, Leaf 2), Node(Leaf 3, Leaf 4))

    t1
   /  \
  /\  /\ 
 1 2 3 4

findPath t1 1   `-->   L(L(H))
findPath t1 3   `-->   R(L(H))
*)
(* val findPath : ''a tree -> ''a -> path option
  (findPath tree key) returns a path to the leaf containing the integer `key',
   or NONE if there is no such leaf 

val fp : ''a tree -> (path -> 'b) -> (unit -> 'b) -> 'b
    fp t sc fc:  sc is a continuation accumulating the path from the root to t;
                 fc is what to do if we don't find a leaf with `key' in t *)

fun findPath tree key =
   let fun fp (Leaf k) sc fc =  if k = key then sc H else fc()
	 | fp (Node(l,r)) sc fc =
	       fp l (sc o L) (fn () => fp r (sc o R) fc)
        (* Recall:  sc o L =  fn p => sc(L(p))  *)
        fun retNONE() = NONE
   in
      fp tree SOME retNONE
 (* SOME (same as fn p => SOME p): The success continuation:
         If we succeed in finding a path p to (Leaf key) within `tree',
         return SOME(p).
     retNONE (same as fn () => NONE): The failure continuation:
       If we don't find it in `tree', return NONE. *)
   end

val t1 = Node(Node(Leaf 1, Leaf 2), Node(Leaf 3, Leaf 4));
val t2 = Node(Node(Node(Leaf 4, Leaf 5), Leaf 6),
               Node(Node(Leaf 7, Node(Leaf 8, Leaf 9)),
               Leaf 10));