-- CS 212, Spring 2001 -- Notes for (part of) Recitation 7
-- Jeannette Wing and Joshua Dunfield

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   `-->   SOME(L(L(H)))
findPath t1 3   `-->   SOME(R(L(H)))
findPath t1 5   `-->   NONE
*)
(* 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

SAMPLE EVALUATION:

  findPath t1 3 ==> fp t1 SOME retNONE
      ==> fp (Node(Leaf 1, Leaf 2)) (SOME o L)
                                    (fn () => fp (Node(Leaf 3, Leaf 4)) }call this
                                                 (SOME o R)  retNONE) } "FC1"
   This means: Find a path to a leaf w/ 3 in the left subtree of t1;
      If we succeed with a path from leftchild(t1) to the leaf,
	 then prepend L to the path (since we're doing the *left* subtree of t1)
              & make it SOMEthing
      If we fail (i.e. there is no Leaf 3 in the left subtree), look in the
         right subtree; if *that* succeeds, prepend R (doing right subtree of t1)
                        and SOMEify it;
         if *that* fails, we've failed in both the left and right subtrees,
           so we've failed for the tree t1,
	   and we call the failure continuation that was passed, namely retNONE.

      ==> fp (Leaf 1) (SOME o L o L) (fn () => fp (Leaf 2) (SOME o L o R) FC1)
      ==> if 1=3 then (SOME o L o L) H
                 else (fn () => fp (Leaf 2) (SOME o L o R) FC1) ()
      ==> fp (Leaf 2) (SOME o L o R) FC1
      ==> if 2=3 then ... else FC1 ()
      ==> FC1()  ==>  fp (Node (Leaf 3, Leaf 4)) (SOME o R) retNONE
      ==> fp (Leaf 3) (SOME o R o L) (fn () => fp (Leaf 4) (SOME o R o R) retNONE)
      ==> if 3=3 then (SOME o R o L) H else ...
      ==> (SOME o R o L) H
      ==> SOME(R(L(H)))
...which means: there is a path: go right, then left, then you're done

EXERCISE: do the evaluation for findPath t2 7:

val t2 = Node(Node(Node(Leaf 4, Leaf 5), Leaf 6),
               Node(Node(Leaf 7, Node(Leaf 8, Leaf 9)),
               Leaf 10))
(draw t2)