递归集合联合:它是如何工作的？

Question

我目前正在下班后的空闲时间参加Coursera的Scala课程,试图最终尝试函数式编程.我目前正在进行一项任务,我们应该"计算"包含一些对象的两个集合的并集.我故意省略细节,因为这对我在这里要问的内容并不重要.然而,相关的是集合被定义为二叉树,每个节点包含一个元素和两个子树.

既然如此; union讲座中的例子如下:

def union(other:BTSet) :BTSet = ((left union right) union other) incl element

问题1:坦率地说,即使在阅读了相关的FAQ和其他论坛帖子之后,我仍然不明白这个功能的工作原理和原因.除了incl在头节点添加(调用)元素之外,在union实现中绝对没有完成"动作" ,它只是一遍又一遍地调用自身.我会非常感谢一些解释......

问题2:课程论坛包含许多帖子,说明这个解决方案根本没有效率,而且还不够好.看到我不明白它是如何工作的我开始并不真正理解为什么它不够好.

请注意,我不以任何方式要求为分配解决方案提供扰流板.我更愿意"为年级做好工作",但我根本不明白我应该在这里做些什么.我不相信课程中提供的说明和指导足以让您了解函数式编程的怪癖,因此我欢迎任何有关如何正确思考而不是如何正确编码的评论/答案.

Answer 1

  A
 / \  union  D
B   C

((B union C) union D) incl A
  ^^^^^^^^^......................................assume it works

(  B             )
(    \   union D ) incl A
(     C          )

(((0 union C) union D) incl B) incl A
   ^^^^^^^^^.....................................just C

(((C union D) incl B) incl A
   ^^^^^^^^^.....................................expand

((((0 union 0) union D) incl C) incl B) incl A
    ^^^^^^^^^....................................just 0

(((0 union D) incl C) incl B) incl A
   ^^^^^^^^^.....................................just D

((D incl C) incl B) incl A
^^^^^^^^^^^^^^^^^^^^^^^^^^.......................all incl now

只需逐步写出来.现在你看到联合减少了一堆应用于右手参数的incl语句.

Answer 2

我收集incl将元素插入现有集合？如果是这样，那就是所有真正的工作发生的地方。

联合的定义是包含任一输入集中所有内容的集合。给定存储为二叉树的两个集合，如果将第一个集合与第二个的分支取并集，则结果中唯一可能丢失的元素是第二个树的根节点处的元素，因此如果您插入该元素，您将拥有两个输入集的并集。

这只是将两个集合中的每个元素插入到以空开始的新集合中的一种非常低效的方式。可能重复项被 丢弃incl，因此结果是两个输入的并集。

也许暂时忽略树结构会有所帮助；它对基本算法并不重要。假设我们有抽象的数学集。给定一个包含未知元素的输入集，我们可以做两件事：

• 向其中添加一个元素（如果该元素已经存在，则不执行任何操作）
• 检查集合是否为非空，如果是，则将其分解为单个元素和两个不相交的子集。

为了取两个集合 {1,2} 和 {2,3} 的并集，我们首先将第一个集合分解为元素 1 和子集 {} 和 {2}。我们使用相同的过程递归地取 {}、{2} 和 {2,3} 的并集，然后将 1 插入到结果中。

在每一步，问题从一个联合操作减少到两个较小输入的联合操作；标准的分而治之算法。当到达单例集 {x} 和空集 {} 的并集时，该并集很简单 {x}，然后返回到链上。

树结构仅用于允许案例分析/分解为更小的集合，并使插入更有效。使用其他数据结构也可以做到这一点，例如将列表分成两半进行分解，并通过彻底检查唯一性来完成插入。要有效地进行联合，需要一种更聪明的算法，并利用用于存储元素的结构。