= Solution
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 \b[$O(n)$ time] for an expression with $n$ vertices. No repeated <list concatenation> copies a previously traversed subtree. This suffix-passing construction is a <difference list> traversal.
Back to article page
