scala - 递归集联合 : how does it work really?

Question

我目前正在下类后的空闲时间参加 Coursera 上的 Scala 类(class)，试图最终尝试函数式编程。我目前正在处理一项任务，我们应该“计算”包含某个对象的两个集合的并集。我有意省略了细节，因为这对我在这里要问的内容并不重要。然而，相关的是集合被定义为二叉树，每个节点包含一个元素和两个子树。

既然如此；示例 union讲座内容如下:

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

问题1:坦率地说，即使在阅读了相关的常见问题解答和其他论坛主题之后，我仍然不明白该功能如何以及为什么起作用。在联合实现中，除了在头节点添加( incl 调用)元素之外，这里绝对没有“ Action ”，它只是一遍又一遍地调用自己。我会非常感谢一些解释......

问题2:类(class)论坛包含许多帖子，指出该解决方案根本没有效率，而且还不够好。看到我不明白它是如何工作的，我真的不明白为什么它不够好。

请注意，我不会以任何方式要求对作业解决方案进行剧透。我非常愿意“为年级做工作”，但我根本不明白我应该在这里做什么。我认为类(class)中提供的说明和指导不足以让您了解函数式编程的怪癖，因此我欢迎任何关于如何正确思考而不是如何正确编码的评论/答案。

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

一步一步写出来就好了。现在您看到 union 简化为一组应用于右侧参数的 incl 语句。