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.


No comments:

Post a Comment

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...