Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 2 / b / Solution 2026-10-31
View more
Compute either the common depth of the leaves of a rooted tree, or failure when the depths differ. A tree fold can return a Maybe Integer: Just h means that the rose tree is a perfect rose tree with all leaves at depth relative to its root; Nothing means it is not perfect.
perfect :: RTree a -> Bool
perfect t =
  case foldRTree step t of
    Nothing -> False
    Just _  -> True
  where
    step :: a -> [Maybe Integer] -> Maybe Integer
    step _ [] = Just 0
    step _ (Nothing : _) = Nothing
    step _ (Just h : hs)
      | all (== Just h) hs = Just (h + 1)
      | otherwise        = Nothing
A leaf has depth zero. An internal vertex has equally deep leaves exactly when every child rose tree is perfect and their returned depths agree; adding one accounts for the edge to each child. This proves the stated meaning of the result by structural induction. In particular, unary branching is allowed, and a single leaf is perfect. perfect returns precisely the required Boolean. Its time complexity is linear in the number of vertices, assuming unit-cost depth arithmetic; labels are never compared or evaluated.
Read the full article