datatype tree = Leaf of int | Node of tree * tree
val t1 =
Node(Node(Node(Node(Node(Leaf 1,Leaf 2),Leaf 3),Leaf 4),Leaf 5),Leaf 6)
val t2 =
Node(Leaf 1,Node(Leaf 2,Node(Leaf 3,Node(Leaf 4,Node(Leaf 5,Leaf 6)))))
val t3 =
Node(Leaf 2,Node(Leaf 1,Node(Leaf 3,Node(Leaf 4,Node(Leaf 5,Leaf 6)))))
structure K = SMLofNJ.Cont
fun makeGenerator t =
let val caller = ref (K.isolate (fn _ => ()))
val generateLeavesRef = ref (fn () => ())
fun generateLeaves () =
let fun loop (Leaf n) =
K.callcc (fn genrest =>
((generateLeavesRef := (fn ()=> K.throw genrest ()));
K.throw (!caller) (SOME n)))
| loop (Node(t1,t2)) = (loop t1; loop t2)
in loop t
end
val _ = (generateLeavesRef := generateLeaves)
in fn () =>
K.callcc (fn k =>
(caller := k;
(!generateLeavesRef)();
K.throw (!caller) NONE))
end
fun sameFringe t1 t2 =
let val g1 = makeGenerator t1
val g2 = makeGenerator t2
fun loop () = let val leaf1 = g1()
val leaf2 = g2()
in case (leaf1,leaf2) of
(SOME a1,SOME a2) =>
(print ("Comparing " ^ Int.toString a1 ^ " and "
^ Int.toString a2 ^ "\n");
if a1 = a2 then loop () else false)
| (NONE,NONE) => true
| _ => false
end
in loop ()
end