递归组合：它是如何工作的？ [英] Recursive set union: how does it work really?

问题描述

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

既然如此，演讲中的例子 union 如下：

  def union其他：BTSet）：BTSet =（（左联合右）联合其他）incl元素
  

问题1：坦率地说，即使阅读了相关的FAQ和其他论坛主题后，我仍然不明白这个功能是如何以及为什么起作用的。除了在头节点添加（ incl 调用）元素之外，在联合实现中完全没有动作，它只是一遍又一遍地调用它自己。我会非常欣赏一些解释......

问题2：课程论坛包含很多帖子，指出此解决方案效率不高，而且还不够好。看到我不明白它是如何工作的，我不明白为什么它不够好。

请注意，我不以任何方式，要求分配解决方案的扰流板。我非常愿意为这个年级开展工作，但我根本不明白我应该在这里做什么。我不相信课程中提供的指导和指导足以让你将头脑放在函数式编程的怪癖中，因此我欢迎任何解决如何正确思考而不是

解决方案

  A 
 / \ union D 
 BC 
 
（（B union C）union D）incl A 
 ^^^^^^^^ ......... .............................假定它有效
 
（B）
（\工会D）包括A 
（C）
 
（（（0工会C）工会D）包括B）包括A 
 ^^^^^^^^^ .. ...................................只是C 
 
（（（C union D）包括B）包括A 
 ^^^^^^^^^ .............................. .......展开
 
（（（（0 union 0）union D）incl C）incl B）incl A 
 ^^^^^^^^^ .. ..................................只是0 
 
（（（0 union D ）含C）含B）含A 
 ^^^^^^^^^ ............................ .........强制t D 
 
（（D incl C）含B）包括A 
 ^^^^^^^^^^^^^^^^^^^^^^ ^ .......................全部包括现在
  

只需一步一步写出来。现在您可以看到，union会缩减为适用于右侧参数的一系列incl语句。

I am currently taking the Scala course on Coursera on my free time after work, in an attempt to finally give a try to functional programming. I am currently working on an assignment where we are supposed to "calculate" the union of two sets that contain some object. I am intentionally omitting details as it's not really important to what I am trying to ask here. What is relevant, however, is that the sets are defined as binary trees, with each node containing an element, and two subtrees.

That being the case; the example union in the lecture is as follows:

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

Question1: Quite frankly, even after having read the relevant FAQ and other forum threads, I still don't understand how and why this function works. There is absolutely no "action" done here in union implementation besides adding (the incl call) the element at the head node, it simply calls itself over and over again. I would be very appreciative of some explanation...

Question2: The course forum contains many posts stating that this solution is not efficient at all, and that it is not good enough. Seeing as I don't understand how it works to begin with I don't really understand why it's not good enough.

PLEASE NOTE that I do not, in any way, ask for a spoiler for the assignment solution. I am more than willing to "do the work for the grade" but I simply don't understand what I am supposed to do here. I don't believe the instructions and guidance provided in the course are adequate to wrap your head around the quirks of functional programming, thus I welcome any comments/answers that address how to think right rather than how to code right.

解决方案

  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

Just write it out step-by step. Now you see that union reduces to a bunch of incl statements applied to the right-hand argument.

这篇关于递归组合：它是如何工作的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！