Recursive union: how does it really work?

Question

I am currently taking a Scala course on Coursera in my free time, trying to finally try functional programming. I am currently working on a task where we must “calculate” the union of two sets containing an object. I intentionally miss out on details, as this is not very important for what I'm trying to ask here. However, it matters that sets are defined as binary trees, with each node containing an element and two subtrees.

This is true; The union example in the lecture is as follows:

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

Question1: Quite frankly, even after reading the relevant FAQ and other forum topics, I still do not understand how and why this function works. In the implementation of the union there is absolutely no “action”, except for adding (calling incl ) an element in the head of the node, it simply calls itself again and again. I would really appreciate some explanation ...

Question2: There are many posts in the course forum that say that this solution is inefficient and that it is not enough. Seeing how I do not understand how this works, I do not quite understand why this is not enough.

PLEASE NOTE that I do not in any way require a spoiler to solve the task. I am more than ready to "do the work for the class", but I just don’t understand what I should do here. I do not believe that the instructions and recommendations provided in the course are sufficient to turn around the quirks of functional programming, so I welcome any comments / answers that relate to how to think correctly and not how to code correctly.

Answer 1

  A / \ union D BC ((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 down step by step. Now you see that the union comes down to a bunch of included statements applied to the right arguments.

Answer 2

I understand that incl inserts an element into an existing set? If so, where all the real work is going on.

A union definition is a set that includes everything in any input set. If two sets are saved as binary trees, if you take the unions of the first set with the branches of the second, the only element that may not be the result is the element in the root directory of the node of the second tree, so if you insert this element, you have a union of both input sets.

This is just a very inefficient way to insert each element from both sets into a new set that starts empty. Presumably duplicates are discarded incl , so the result is a union of the two inputs.

---

Perhaps this would help to ignore the tree structure at the moment; this is not very important for the main algorithm. Say we have abstract math sets. Given a set of input with unknown elements, we can do two things:

• Add an element to it (which does nothing if the element is already present)
• Check if the set is not empty and, if so, decompose it into one element and two disjoint subsets.

To take the union of the two sets {1,2} and {2,3}, we start by decomposing the first set into element 1 and the subsets {} and {2}. We recursively use the union of {}, {2} and {2,3} using the same process, then insert 1 into the result.

At each step, the problem boils down from one join operation to two joint operations on the smaller inputs; standard separation and rest algorithm. Upon reaching the union of the one-point set {x} and the empty set {}, the union is trivial {x}, which then returns back to the chain.

The tree structure is used only to allow case analysis / decomposition into smaller sets and to make the insertion more efficient. The same can be done using other data structures, such as lists, bisected for decomposition and with an insert made with an exhaustive check for uniqueness. To effectively use a union, an algorithm is needed that is a little smarter and uses the structure used to store items.

Answer 3

Therefore, based on all the answers above, I think that the real workhorse is incl , and the recursive way to call union is to just go through all the elements in the sets.

I came up with the following implementation of the union, is this better?

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

Answer 4

  2 / \ union 4 1 3 ((1 union 3) union 4) incl 2 ^^^^^^^^^......................................assume it works (((E union E) union 3 incl 1) union 4) incl 2 ^^^^^^^^^.....................................still E (E union E) union 3 incl 1 = E union 3 incl 1 = 3 incl 1 

The next subtree should be 3 , including 1

 ( 3 ) ( \ union D ) incl 2 ( 1 ) (((1 union E) union 4) incl 3) incl 2 ^^^^^^^^^.......................................expand (((( (E union E) union E) incl 1) union 4) incl 3) incl 2 ^^^^^^^^^^^^^^^^^^^^^^^^^^..................still 1 ((1 union 4) incl 3) incl 2 ^^^^^^^^......................................continue ((((E union E) union 4) incl 1) incl 3) incl 2 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^..........expand 1 union 4 ((4 incl 1) incl 3) incl 2 ^^^^^^^^^^^^^^^^^^^^^^^^^............Final union result 

Thanks @Rex Kerr crosses out the steps. I am replacing the second step with an actual execution step, which can provide a clearer description of the Scala union function.

Answer 5

You cannot understand recursive algorithms unless you look at the base case. In fact, often the key to understanding is understanding the underlying case. Since the base case is not shown (perhaps because you did not notice it in the first place) there is no understanding.

Answer 6

I am doing the same course, and the union implementation given above turned out to be extremely inefficient.

I came up with the following not very functional solution for creating a union of sets of binary trees, which is more efficient:

 def union(that: BTSet): BTSet = { var result:BTSet = this that.foreach(element => result = result.incl(element)) result }