= Solution
Fold into a membership <predicate>:
``
find :: Ord a => Tree a -> a -> Bool
find = foldTree node (const False)
where
node left x right q = case compare q x of
LT -> left q
EQ -> True
GT -> right q
``
At an empty tree the <predicate> is always false. At a nonempty <binary search tree>, an unequal query can occur only in the indicated child, while equality finds the root. This proves correctness inductively. Under <lazy evaluation>, the unused folded child is not demanded; lookup follows one root-to-leaf route and takes $O(h+1)$ comparisons in a tree of height $h$. Defining the <predicate> by a fold does not require visiting both subtrees for each query.
Back to article page
