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

1 回答 1

43

我们绑定(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，所以该函数假设树已经在 in 的意义上排序，in 中的Root x l r所有内容都在l下面x，in 中的所有内容都在r上面x。

被left_subtree拆分，因为其中一些可能小于，s而其他位可能大于s.

现在属于右侧的部分split s left_subtree（因为它大于s）被称为new_right_tree，并且因为整体left_subtree小于x和right_subtree，所以所有的new_right_tree仍然应该在两者的左侧xand 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)

好的，我认为这回答了我的问题：有时描述性名称也会令人困惑！

于 2013-04-28T20:34:22.917 回答