Haskell树分裂:有人可以解释一下这行吗？

Question

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

有人可以解释这一行吗？我真的没有得到这个let部分.

我试着想一想,我不知道我是否做对了:我们绑定(nlt, nrt),结果split s lst; 而且split s lst本身就是(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)

Answer 1

我们绑定(nlt, nrt),结果split s lst

split s lst是的- 是一对,我们给出了这两个元素的名称nlt和nrt两个元素.

而且split s lst本身就是(nlt, Root x nrt rst)

不,split s (Root x lst rst)(整个功能的结果)将是(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)

让我们尝试一些示例数据:

> 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)

所以我们选择了一个以512为根的树,以及比左边子树小的所有项,并将其拆分,以便第一棵树由300以下的条目组成,第二棵树则超过300.看起来像这样:

有问题的线如何工作？

首先让我们用扩展名重写代码:

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)

警卫|s < x意味着我们的情况x应该在右边.

首先,我们拆分左边的子树split s left_subtree,给我们一个new_left_tree和new_right_tree.该new_left_tree是应该向左走的东西,但new_right_tree与合并x和原始right_subtree弥补该去右边的位s.

我们可以从中学到什么功能？

在right_subtree被单独留在家中,因为s在左所属x,因此函数是假设树在某种意义上已经排序,在Root x l r,一切都在l低于x,一切都在r为上面x.

在left_subtree被分裂,因为有些可能小于s和大于其他位s.

的一部分split s left_subtree,现在属于右边(因为它比s)被调用new_right_tree,并且因为整个left_subtree是小于x和right_subtree,所有的new_right_tree应该还是以两者的左边x和right_subtree.这就是为什么我们Root x new_right_tree right_subtree在对中(以及new_left_tree对的左侧)做出正确答案的原因.

这是一个前后图:

那么为什么没有更多的描述性名称呢？

好问题.我们开始做吧:

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)

好吧,我认为这回答了我的问题:有时候描述性的名字也会令人困惑!