Splitting a BinTree with tail recursion in Haskell

Question

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.

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, Jun 05 '16 at 16:55
do you think that the purpose of homework is to go find help on the internet? — d8d0d65b3f7cf42, Jun 05 '16 at 17:23
@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, Jun 05 '16 at 17:38
@d8d0d65b3f7cf42 homework is no problem on SO - it should just show a bit of own effort but just because the question itself will be really bad otherwise — Random Dev, Jun 05 '16 at 17:47
Related SO thread: http://stackoverflow.com/questions/14805700/how-to-do-tail-recursion-for-a-binary-tree — ErikR, Jun 05 '16 at 17:47
thanks for your help everyone. We managed to solve it with a bit of help by our tutor. @d8d0d65b3f7cf42 No, i think the purpose of homework is to help me teaching myself, but in this case i got stuck. — GabbaGandalf, Jun 06 '16 at 12:02
@WillemVanOnsem no, since we are working just with ghci, we are not allowed to get any help by the compiler or other functions.. — GabbaGandalf, Jun 06 '16 at 12:04

score 4 · Accepted Answer · answered Jun 05 '16 at 18:21

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

Michael · Answer 2 · 2016-06-06T12:19:58.063

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.

very interesting solution. Now ill try to understand it.. ^^ Thanks for the help! — GabbaGandalf, Jun 06 '16 at 12:23

score 2 · Answer 3 · answered Jun 05 '16 at 23:07

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.

Sadly we are only working with ghci, writing everything in .lhs files. So i guess thats why we were asked to do something like this.But for some reason ghci tells me it cant parse the pattern in line 5. : `(# hd, ...` . — GabbaGandalf, Jun 06 '16 at 12:16
@GabbaGandalf, this sounds more like an exercise to teach a corrupt — dfeuer, Jun 07 '16 at 02:23

Splitting a BinTree with tail recursion in Haskell

3 Answers3