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的结果

Yup - 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为根的树，并将左子树中所有小于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)

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

好吧，我想这回答了我的问题:有时描述性名称也会让人感到困惑！