How do you implement "show" tail-recursively?

Question

Haskell's show is usually implemented recursively as:

data Tree = Node Tree Tree | Leaf

show' (Node left right) = "(Node " ++ show' left ++ " " ++ show' right ++ ")"
show' Leaf              = "Leaf"

main = putStrLn $ show' (Node (Node Leaf Leaf) Leaf)

How can you implement show using tail recursion?

Answer 1

Using CPS, as mentioned by M. Shaw.

show' :: Tree -> String
show' = \tree -> go tree id
    where
    go (Node left right) c = 
      go left (\l -> go right (\r -> c ("(Node " ++ l ++ " " ++ r ++ ")")))
    go Leaf c = c "Leaf"

It's important to keep in mind that Haskell's laziness obviates the need for tail recursion in many cases. In this case, the tail recursive version has to traverse the entire tree before any part of the input can be returned. Try showing an infinite tree with each version. When returning a lazy structure such as String in a lazy language, it is better to be corecursive (which your original implementation is) than tail recursive.

Most of the time of this function will be eaten up by left-nested (++) calls, which is O(n) in its left argument. The solution is to use a difference list, which is a form of continuation-passing style itself.

See also Continuation-Based Program Transformation Strategies, which talks about how to arrive at efficient algorithms by converting to CPS, then transforming the structure of the continuations into something more concrete to arrive at a tail-recursive solution.