Splitting a BinTree with tail recursion in Haskell

4
votes

So this week we learned about union types, tail recursion and binary trees in Haskell. We defined our tree data type like so:

data BinTree a = Empty
           | Node (BinTree a) a (BinTree a)
           deriving (Eq, Show)

leaf :: a -> BinTree a
leaf x = Node Empty x Empty

Now we were asked to write a function to find the most left node, return it, cut it out and also return the remaining tree without the node we just cut.

We did something like this, which worked quite well:

splitleftmost :: BinTree a -> Maybe (a, BinTree a)
splitleftmost Empty = Nothing
splitleftmost (Node l a r) = case splitleftmost l of
                                 Nothing -> Just (a, r)
                                 Just (a',l') -> Just (a', Node l' a r)

Now I need to make this function tail recursive. I think I understood what tail recursion is about, but found it hard to apply it to this problem. I was told to write a function which calls the main function with the fitting arguments, but was still not able to solve this.

3
haskellrecursionbinary-treetail-recursion
so what have you tried (show the code) - I somewhat wonder why you should but in this case a natural approach seems to be using continuations – Random Dev
do you think that the purpose of homework is to go find help on the internet? – d8d0d65b3f7cf42
@d8d0d65b3f7cf42: I think since the OP showed his/her attempt and simply has questions about a specific topic - in this case tail recursion, that it is acceptable question. – Willem Van Onsem
@GabbaGandalf: are tail-recursive helper functions allowed? – Willem Van Onsem
Related SO thread: stackoverflow.com/questions/14805700/… – ErikR

3 Answers

4
votes

Since nodes do not have a parent link, one approach would be to maintain root-to-leaf path within a list. At the end the modified tree can be constructed using a left fold:

slm :: BinTree a -> Maybe (a, BinTree a)
slm = run []
    where
    run _ Empty = Nothing
    run t (Node Empty x r) = Just (x, foldl go r t)
        where go l (Node _ x r) = Node l x r

    run t n@(Node l _ _) = run (n:t) l
2
votes

As others have hinted, there is no reason, in Haskell, to make this function tail-recursive. In fact, a tail-recursive solution will almost certainly be slower than the one you have devised! The main potential inefficiencies in the code you've provided involve allocation of pair and Just constructors. I believe GHC (with optimization enabled) will be able to figure out how to avoid these. My guess is that its ultimate code will probably look something like this:

splitleftmost :: BinTree a -> Maybe (a, BinTree a)
splitleftmost Empty = Nothing
splitleftmost (Node l a r) =
  case slm l a r of
    (# hd, tl #) -> Just (hd, tl)

slm :: BinTree a -> a -> BinTree a
    -> (# a, BinTree a #)
slm Empty a r = (# a, r #)
slm (Node ll la lr) a r =
  case slm ll la lr of
    (# hd, tl' #) -> (# hd, Node tl' a r #)

Those funny-looking (# ..., ... #) things are unboxed pairs, which are handled pretty much like multiple return values. In particular, no actual tuple constructor is allocated until the end. By recognizing that every invocation of splitleftmost with a non-empty tree will produce a Just result, we (and thus almost certainly GHC) can separate the empty case from the rest to avoid allocating intermediate Just constructors. So this final code only allocates stack frames to handle the recursive results. Since some representation of such a stack is inherently necessary to solve this problem, using GHC's built-in one seems pretty likely to give the best results.

2
votes

Here, not to spoil anything, are some "tail recursive" definitions of functions for summing along the left and right branches, at least as I understand "tail recursion":

sumLeftBranch tree = loop 0 tree where
  loop n Empty        = n
  loop n (Node l a r) = loop (n+a) l

sumRightBranch tree = loop 0 tree where
  loop n Empty        = n
  loop n (Node l a r) = loop (n+a) r

You can see that all the recursive uses of loop will have the same answer as the first call loop 0 tree - the arguments just keep getting put into better and better shape, til they are in the ideal shape, loop n Empty, which is n, the desired sum.

If this is the kind of thing that is wanted, the setup for splitleftmost would be 

splitLeftMost tree = loop Nothing tree 
  where
  loop m              Empty        = m
  loop Nothing        (Node l a r) = loop ? ? 
  loop (Just (a',r')) (Node l a r) = loop ? ?

Here, the first use of loop is in the form of loop Nothing tree, but that's the same as loop result Empty - when we come to it, namely result. It took me a couple of tries to get the missing arguments to loop ? ? right, but, as usual, they were obvious once I got them.