haskell - How do you implement "show" tail-recursively? -

haskell's show 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 implement show using tail recursion?

using cps, mentioned m. shaw.

show' :: tree -> string show' = \tree -> go tree id         go (node left right) c =        go left (\l -> go right (\r -> c ("(node " ++ l ++ " " ++ r ++ ")")))     go leaf c = c "leaf" 

it's important keep in mind haskell's laziness obviates need tail recursion in many cases. in case, tail recursive version has traverse entire tree before part of input can returned. try showing infinite tree each version. when returning lazy structure such string in lazy language, better corecursive (which original implementation is) tail recursive.

most of time of function eaten left-nested (++) calls, o(n) in left argument. solution use difference list, form of continuation-passing style itself.

see continuation-based program transformation strategies, talks how arrive @ efficient algorithms converting cps, transforming structure of continuations more concrete arrive @ tail-recursive solution.