Sunday, December 24, 2023

Functional Programming Scala - Coursera NonEmpty Union

 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): IntSet
def contains(x: Int): Boolean
def union(s: IntSet): IntSet

class Empty() extends IntSet:
def contains(x: Int): Boolean = false
def incl(x: Int): NonEmpty(x, Empty(), Empty())
def union(s: IntSet): IntSet = s

class 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 true

def 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 this
def 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
         /     \                   /      \
        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)
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
                                   /      \
                                 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.


Taller de ingeniería de Big Data

Los siguientes procedimientos corresponden al material complementarío del taller de ingeniería de Big Data que será dado de forma presencial...