Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 5 / 5 / a

Assuming p is an ordinary total Boolean predicate, replace success by true and the search's failure exception by false:The Standard ML handler in the printed function belongs to the else expression: it tries the left subtree and, only if that search raises Blair, tries the right. It does not catch a failing label test at the current node. This scope follows the Standard ML grammar, Appendix B. Short-circuit andalso rejects the current label before visiting either child; short-circuit orelse visits the right child only after the left search fails. Structural induction on the binary tree proves that tony returns true exactly when gordonPlain does, and otherwise raises the exception converted by gordon to false. The exception-free test is the root predicate conjoined with the disjunction of the two subtree tests.

The total-predicate assumption matters: if p itself raises Blair, the original handler can catch it, whereas an implementation with no exception handling cannot in general convert that event to a Boolean result. The displayed replacement implements the intended Boolean tree property, not an exception-catching wrapper for arbitrary exceptional predicates.

For a finite binary tree, gordon p t expresses the existence of a root-to-Lf path on which every branch-node label satisfies p. The empty tree has a length-zero path and returns true. At Br(x,left,right), such a path exists precisely when p x holds and at least one child admits such a path. This is the recursive Boolean equation derived in part (i).

The property is neither “all labels in the tree satisfy p” nor “some label satisfies p”. A bad label in an unchosen subtree does not prevent success, but a bad root label prevents every root-to-leaf path. The traversal performs a left-first search for a qualifying path.