We need a recursive datatype with a basis data constructor, say Int , to wrap integers, and an inductive data constructor, say Thing , to wrap a list of things. Here is a typical value of the datatype thing .
R is included in the set of reached nodes that is eventually returned.
The idea is to form the set of integers into as balanced a binary tree as we can. The longest paths will then be proportional to the logarithm of the size of S . We leave as an interesting challenge a function that will take a list of integers and form them into a binary search tree that is as balanced as possible. We test whether x is at the root, and if not, test whether it is either in the first subtree or in the tree obtained by removing the first subtree. Then, foldr is applied to the function that takes the OR of its arguments, an initial value false , and the list of booleans that resulted from the application of map .