Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 2 / b / Solution 2026-10-31
View more
Pass an already constructed suffix through the traversal:
convert :: Expr -> RPolish
convert e = go e []
  where
    go :: Expr -> RPolish -> RPolish
    go (Num n) rest = Number n : rest
    go (App op left right) rest =
      go left (go right (Operator op : rest))
The invariant is that go e rest is the reverse Polish notation of e followed by rest. It holds at a numeric leaf. At an application, the result is the left subtree's tokens, then the right subtree's tokens, then the operator, then rest, exactly as required.
Each vertex of the abstract syntax tree creates one output list cell and performs constant local work. Thus producing the complete result takes time for an expression with vertices. No repeated list concatenation copies a previously traversed subtree. This suffix-passing construction is a difference list traversal.
Read the full article