In the third week of Coursera course Functional Programming Principles in Scala, there a method in one of the examples that was really hard for me to understand. I will describe step by step how the method Union of the Lecture 3.1 - Class hierarchies works:
Given the following code:
abstract class IntSet:def incl(x: Int): IntSetdef contains(x: Int): Booleandef union(s: IntSet): IntSetclass Empty() extends IntSet:def contains(x: Int): Boolean = falsedef incl(x: Int): NonEmpty(x, Empty(), Empty())def union(s: IntSet): IntSet = sclass NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet:def contains(x: Int): Boolean =if x < elem then left.contains(x)else if x > elem then right.contains(x)else truedef incl(x: Int): InSet =if x < elem then NonEmpty(elem, left.incl(x), right)else if x > elem then NonEmpty(elem, left, right.incl(x))else thisdef union(s: IntSet): InSet =left.union(right).union(s).incl(elem)
How the method union will resolve for Inset A and B :
A B
5 8
/ \ / \
5 8
/ \ / \
3 7 6 10
The nature of the algorithm is recursive, we need to read it from left to right and solve it that way too.
Conventions
N = NonEmpty (class)
E = Empty (class)
Green = left (class member)
Blue = right (class member)
Steps:
1)
1)
A.union(B)
2)
N(5, N(3, E, E), N(7, E, E)).union(B)
3)
N(3, E, E).union(N(7, E, E)).union(B).incl(5)
4)
E.union.E.union(N(7, E, E)).incl(3).union(B).incl(5)
5)
E.union(N(7, E, E)).incl(3).union(B).incl(5)
6)
N(7, E, E).incl(3).union(B).incl(5)
7)
N(7, N(3, E, E), E).union(B).incl(5)
8)
N(3, E, E).union(E).union(B).incl(5).incl(7)
9)
E.union(E).union(E).incl(3).union(B).incl(5).incl(7)
10)
N(3, E, E).union(B).incl(5).incl(7)
11)
E.union.E.union(B).incl(5).incl(7).incl(3)
12)
B.incl(5).incl(7).incl(3)
13)
B
8
/ \
8
/ \
6 10
/ \
3 7
\
5
What the algorithm does is:
- Add every element of A into B
- The order used for the insertion is first the most left element, then the most right element then the root, and repeat the cycle.
No comments:
Post a Comment