Menu
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.
754
We saw in Lecture 5: Union Data types that a union data type is used to represent data that is one of several different forms. Sometimes, some of those forms refer to themselves or other forms of the union data type. This is a recursive union.
A recursive definition: A list is either. • empty, written [], or • constructed, written x:xs, with head x (an element), and tail xs (a list). Cons (:) is special: any list can be written using : and [], in only one way.
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.
83
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
