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)
we bind
(nlt, nrt)
, to the result ofsplit 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)
.
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:
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
.
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:
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!
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With