Haskell Tree splitting: Can someone please explain this line?

Question

split s (Root x lst rst)
 | s < x = let (nlt, nrt) = split s lst in
     (nlt, Root x nrt rst)

Can someone please explain this line? I don't really get the let part.

I tried thinking about it, I have no idea if I got it right: we bind (nlt, nrt), to the result of split s lst; and split s lst itself will be (nlt, Root x nrt rst)

Is that it?

Here's the complete code:

split :: Ord a => a -> Tree a -> (Tree a, Tree a)
split _ Empty = (Empty, Empty)
split s (Root x lst rst)
 | s < x = let (nlt, nrt) = split s lst in
     (nlt, Root x nrt rst)
 | s > x = let (nlt, nrt) = split s rst in
         (Root x lst nlt, nrt)

Answer 1

we bind (nlt, nrt), to the result of split s lst

Yup - split s lst is a pair, and we're giving the names nlt and nrt to the two elements of the pair.

and split s lst itself will be (nlt, Root x nrt rst)

No, split s (Root x lst rst) (the result of the whole function) will be (nlt, Root x nrt rst).

But what does the whole function do?

split :: Ord a => a -> Tree a -> (Tree a, Tree a)
split _ Empty = (Empty, Empty)
split s (Root x lst rst)
 | s < x = let (nlt, nrt) = split s lst in
     (nlt, Root x nrt rst)
 | s > x = let (nlt, nrt) = split s rst in
         (Root x lst nlt, nrt)

Let's try that on some sample data:

> split 300 (Root 512 (Root 256 (Root 128 Empty Empty) (Root 384 Empty Empty)) Empty)
(Root 256 (Root 128 Empty Empty) Empty,Root 512 (Root 384 Empty Empty) Empty)

So we took a tree that had 512 as its root, and all the items smaller than it in the left subtree, and split it so that the first tree is made up of entries below 300, with those over 300 in the second. That looks like this:

How does the line in question work?

First let's rewrite the code with expanded names:

split :: Ord a => a -> Tree a -> (Tree a, Tree a)
split _ Empty = (Empty, Empty)
split s (Root x left_subtree right_subtree)
 | s < x = let (new_left_tree, new_right_tree) = split s left_subtree in
     (new_left_tree, Root x new_right_tree right_subtree)
 | s > x = let (new_left_tree, new_right_tree) = split s right_subtree in
         (Root x left_subtree new_left_tree, new_right_tree)

The guard |s < x means we're in the case that this x should go on the right.

First we split the left subtree split s left_subtree, givning us a new_left_tree and new_right_tree. The new_left_tree is the stuff that should go left, but the new_right_tree is combined with x and the original right_subtree to make up the bits that go on the right of s.

What can we learn about the function from that?

The right_subtree gets left alone, because s belongs on the left of x, so the function is assuming the tree is already sorted in the sense that in Root x l r, everything in l is below x and everything in r is above x.

The left_subtree gets split, because some of it may be less than s and other bits more than s.

The part of split s left_subtree that now belongs on the right (because it's more than s) is called new_right_tree, and because the whole left_subtree was less than x and the right_subtree, all of the new_right_tree should still be to the left of both x and right_subtree. That's why we make Root x new_right_tree right_subtree to be the right hand answer in the pair (and new_left_tree on the left of the pair).

Here's a before and after diagram:

Why not have more descriptive names then?

Good question. Let's do it:

split :: Ord a => a -> Tree a -> (Tree a, Tree a)
split _ Empty = (Empty, Empty)
split s (Root this below_this above_this)

 | s < this = let (below_this_below_s, below_this_above_s) = split s below_this in
     (below_this_below_s,  Root  this  below_this_above_s  above_this)

 | s > this = let (above_this_below_s, above_this_above_s) = split s above_this in
         (Root  this  below_this above_this_below_s,  above_this_above_s)

OK, I think that answers my question: sometimes descriptive names can be confusing too!