CODEWITHSUNDEEP
haskelltail-recursion
Chase
Chase

Reputation: 93

Tree traversal inorder tail recursion

Did I implement inorder level-order tree transversal using tail-recursion correctly?

inorder (Leaf n) temp = n:temp
inorder (Node (n, left, right)) temp = inorder left (n:inorder right temp)
inorder :: Tree a -> [a] -> [a]

Tree is declared as 

data Tree a = Leaf a | Node (a, Tree a, Tree a) deriving Show

and returns [2,1,3] on call inorder three [] where three = Node (1, Leaf 2, Leaf 3)

Upvotes: 0

Views: 2301

Answers (1)

daniel gratzer
daniel gratzer

Reputation: 53881

This technically isn't tail recursive because you have a recursive call inorder right temp in a nontail position. One way to fix this would be with continuations. You write a function which takes an accumulator like before, but rather than the accumulator being just a list it's actually a function representing the work left to do in the computation. This means that instead of making a non-tail call and just returning, we can always tail call because the context we need is saved to the continuation.

  inorder = go id
    where go :: ([a] -> r) -> Tree a -> r
          go k Leaf = k []
          go k (Node a l r) = go l (\ls -> go r (\rs -> k $ ls ++ n : rs))

Here every call is a tail call as required but it's quite innefficient because it requires a ++ operation at every level, pushing us into quadratic costs. A more efficient algorithm would avoid building up an explicit list and instead build up a difference list, delaying the construction on the concrete structure and giving a more efficient algorithm

type Diff a = [a] -> [a] -- A difference list is just a function

nil :: Diff a
nil xs = xs

cons :: a -> Diff a -> Diff a
cons a d = (:) a . d

append :: Diff a -> Diff a -> Diff a
append xs ys = xs . ys

toList :: Diff a -> a
toList xs = xs []

Note that all of these operations are O(1) except for toList which is O(n) in the number of entries. The important point here is that diff lists are cheap and easy to append so we'll construct these in our algorithm and construct the concrete list at the very end

 inorder = go toList
    where go :: (Diff a -> r) -> Tree a -> r
          go k Leaf = k nil
          go k (Node a l r) = 
             go l (\ls -> go r (\rs -> k $ ls `append` cons n rs))

And now, through gratuitous application of functions we've gotten a completely unidiomatic Haskell program. You see in Haskell we don't really care about tail calls because we generally want to handle infinite structures correctly and that's not really possible if we demand everything be tail recursive. In fact, I would say that while not tail recursive, the code you originally had is the most idiomatic, that's even how it's implemented in Data.Set! It has the property that we can lazily consume the result of that toList and it will work with us and lazily process the tree. So in your implementation, something like

min :: Tree a -> a
min = listToMaybe . toList

is going to be pretty darn close to how you would implement it by hand efficiency wise! It will not construct traverse the whole tree first like my version will have to. These sort of compositional effects of laziness pay more dividends in real Haskell code than syntactically making our code use only tail calls (which does nothing to actually guarantee space usage anyways).

Upvotes: 8

Related Questions