Scala - A pure object oriented language too

A language is purely object oriented if

• every value is an object,
• they type of every value is a class and
• all operations as method calls on objects

Scala is also a pure object oriented language. You can argue that there are exceptions like primitive types and functions which are not objects. But let's have a closer look.

Primitive types as Objects

Primitive types such as Int and Boolean are conceptually treated same as any other class in Scala. Here I will explain how Boolean can be expressed as a class rather than a primitive type.

Primitive boolean to Boolean type

Boolean can be of two types viz. true or false. Lets define a class hierarchy as follows.

Boolean is an abstract class. It has an abstract method ifThenElse as follows.

package com.techmights
abstract class Boolean {
def ifThenElse[T](i: =>T,e: =>T):T
}

The ifThenElse method takes two arguments i and e. i represents the value to be returned when the if condition is satisfied and e represents the else value i.e.

if(condition)
i
else
e

Which can be expresses here as

condition.ifThenElse(i,e)

Where condition is a subtype of Boolean. Let's define the True and False objects. Both these objects are Boolean, therefore will extend abstract class Boolean and will provide the definition of ifThenElse method as follows.

object True extends Boolean{
    def ifThenElse[T](i: =>T,e: =>T) = i
}

object False extends Boolean {
    def ifThenElse[T](i: =>T,e: =>T) = e
}

The implementations are straight forward. The True object returns the true value and False object returns the false(else) value.

There are certain operations that can be performed on Boolean values viz. AND(&&), OR(||), NOT(!), EQUAL(==), NOT_EQUAL(!=) etc. As these operations are common for True and False, hence we can add these to the abstract class Boolean.

The truth table for && is as follows.

A	B	Result
True	True	True
True	False	False
False	True	False
False	False	False

From the above table, we can create a summary table as follows.

A	B	Result
True	x	x
False	x	False

The summary table says that  

• when && method is called on a True object, then the result is the argument passed i.e. x
• when && method is called on a Flase object, then the result is False regradles of the argument passed

Based on the above explanation, we can add && method as follows.

abstract class Boolean {
  def ifThenElse[T](i: =>T,e: =>T):T  
  def && (x: =>Boolean) = ifThenElse(x,False)  
}

Similarly || for True will always be True and for False, it will be the argument passed. Therefore,

abstract class Boolean {
  def ifThenElse[T](i: =>T,e: =>T):T
  
  def && (x: =>Boolean) = ifThenElse(x,False)
  def || (x: =>Boolean) = ifThenElse(True,x)  
}

For negation(!), when it is called on True, it should return False and vice versa. Note that negation is a unary operation and hence no argument required. Therefore,

abstract class Boolean {
  def ifThenElse[T](i: =>T,e: =>T):T
  
  def && (x: =>Boolean) = ifThenElse(x,False)
  def || (x: =>Boolean) = ifThenElse(True,x)  
  def unary_! :Boolean = ifThenElse(False,True) 
}

In case of comparison(==) when True==x, then the result depends on x. But when False==x then result is True if x=False else otherwise i.e. !x. The != operation will be opposite of ==. Therefore,

abstract class Boolean {
  def ifThenElse[T](i: =>T,e: =>T):T
  
  def && (x: =>Boolean) = ifThenElse(x,False)
  def || (x: =>Boolean) = ifThenElse(True,x)  
  def unary_! :Boolean = ifThenElse(False,True)
  def ==(x: =>Boolean):Boolean= ifThenElse(x, x.unary_!)
  def !=(x: =>Boolean):Boolean= ifThenElse(x.unary_!,x)
}

This completes the Boolean class and we learnt to represent a primitive type as an object in Scala with all its operations.

Binary Search Tree in Scala

In this post we are going to make a structure which is similar to Binary Search Tree (BST).

Each node contains an integer element and two child nodes. All the nodes having value less than the current node will be on the left and all nodes having value greater will be on right. If a node doesn't have any child then it will have empty node at that place.

From the description, we can deduce that there are two types on integer nodes - Empty and Non Empty. The operations can be to add a new node or to check if a node exists in the current tree. Hence lets define an abstract class IntNode with these two abstract functions.

IntNode.scala

abstract class IntNode {
  def incl(x: Int): IntNode
  def contains(x: Int): Boolean
}

This abstract class will have its first concrete implementation as Empty node. This is empty node, hence its contains function will always return false. The incl function will take an integer value and create a non-empty node. The code is as follows.

Empty.scala

class Empty extends IntNode {
  def incl(x: Int): IntNode = new NonEmpty(x, new Empty, new Empty)
  def contains(x: Int): Boolean = false
  override def toString = " . "
}

Another concrete implementation of IntNode is NonEmpty node which is as follows.

NonEmpty.scala

class NonEmpty(elem: Int, left: IntNode, right: IntNode) extends IntNode {

  def incl(x: Int): IntNode =
    if (x < elem)
      new NonEmpty(elem, left incl x, right)
    else if (x > elem)
      new NonEmpty(elem, left, right incl x)
    else
      this

  def contains(x: Int): Boolean =
    if (x < elem)
      left contains x
    else if (x > elem)
      right contains x
    else
      true

  override def toString = " { " + left + elem + right + " } "
}

The toString function is overridden to print Empty node as dot(.) and non-empty node in the order of left, element and then right node(s).

Let's first take the contains function. It compares the element x passed to it with current node element and takes a decision based on the BST property. If an element doesn't exists in the tree then it recursively reaches the Empty node of which the contains function returns false.

The incl function also uses the property of BST to add a new node. If the element already present in the list, then it avoids duplication by returning this reference. Otherwise it accordingly reconstruct the tree.

The sample Main class and its output are as follows.

Main.scala

object Main extends App {

  val t1 = new Empty
  println("t1 = " + t1)

  val t2 = t1 incl 4
  println("t2 = " + t2)

  val t3 = t2 incl 1
  println("t3 = " + t3)

  val t4 = t3 incl 5
  println("t4 = " + t4)

  val t5 = t4 incl 2 incl 7 incl 0
  println("t5 = " + t5)

  println("t1 contains 4 = " + (t1 contains 4))
  println("t2 contains 4 = " + (t2 contains 4))
  println("t5 contains 4 = " + (t5 contains 4))
  println("t5 contains 0 = " + (t5 contains 0))
  println("t5 contains 9 = " + (t5 contains 9))

  val t6 = t5 incl 1
  println("t6 = " + t6)

}

Output

t1 =  . 
t2 =  {  . 4 .  } 
t3 =  {  {  . 1 .  } 4 .  } 
t4 =  {  {  . 1 .  } 4 {  . 5 .  }  } 
t5 =  {  {  {  . 0 .  } 1 {  . 2 .  }  } 4 {  . 5 {  . 7 .  }  }  } 
t1 contains 4 = false
t2 contains 4 = true
t5 contains 4 = true
t5 contains 0 = true
t5 contains 9 = false
t6 =  {  {  {  . 0 .  } 1 {  . 2 .  }  } 4 {  . 5 {  . 7 .  }  }  } 

Higher Order Functions in Functional Programming

Function programming paradigm treats functions as its first class citizens which means

• you can pass a function as an argument to another function
• you can return a function from a function and
• you can compose a function inside another function and assign it to a variable too just as we do with any other value or reference type.

This provides a flexible way to compose programs.

To build up this concept, consider a summation function which gives sum of elements in the range a to b.

This can be written recursively as follows.

def summation(a: Int, b: Int): Int = {
    if (a > b) 0
    else a + summation(a + 1, b)
  }                                               //> summation: (a: Int, b: Int)Int

  summation(3, 6)                                 //> res0: Int = 18

There are 2 problems with the above piece of code.

• The parameter b doesn't change, still I have to pass it to all the recursive calls as summation requires 2 parameters.
• The summation function is not tail recursive. If the range of a and b is huge then the piece of code may result into stack overflow.

If you think, summation is internally running a loop from a to b. So the new code with tail recursivenes will look like,

  def summation(a: Int, b: Int): Int = {

    def loop(a: Int, acc: Int): Int = {

      if (a > b) acc
      else
        loop(a + 1, a + acc)

    }

    loop(a,0);
  }                                               //> summation: (a: Int, b: Int)Int

  summation(3, 6)                                 //> res0: Int = 18

Note that you must always specify the return type of the recursive function, otherwise the Scala compiler will not be able to infer the type, as while doing the type inference it will end into a never ending recursive calls.

Taking this a step ahead, the requirement might be to

• find sum of squares of numbers between a and b
• find sum of cubes of numbers between a and b
• find sum of factorials of numbers between a and b

The final thing is to do sum of numbers between a and b, just the function f to be applied on the number is changing. This can be expressed mathematically as

where f can be
f(x) = x*x
f(x) = x*x*x
f(x) = factorial(x)

So the summation function will take one more argument f i.e. the function to be applied on each a before adding it to the accumulator. The function f takes an Int argument and returns an Int value. Hence the summation function can be redefined as,

  def summation(a: Int, b: Int, f: Int => Int): Int = {

    def loop(a: Int, acc: Int): Int =
      if (a > b) acc
      else
        loop(a + 1, f(a) + acc)

    loop(a, 0);
  }                                               //> summation: (a: Int, b: Int, f: Int => Int)Int

Summation of factorial of numbers between a to b - Define a function fact in tail recursive way to find factorial of a number and then pass it  to summation as an argument.

  def fact(a: Int): Int = {

    def f(a: Int, acc: Int): Int =
      if (a == 0) acc
      else f(a - 1, a * acc)

    f(a, 1)
  }                                               //> fact: (a: Int)Int

  summation(3, 5, fact)                           //> res0: Int = 150

Lambda expressions - For small functions, like square, cube of a number we can define the functions inline as lambda expressions while making summation function call.

summation(1,5,x=>x*x)                           //> res1: Int = 55
summation(1,3,x=>x*x*x)                         //> res2: Int = 36

Currying the function - In Currying, a function takes only one argument and returns a value. Let's apply some currying on summation function named as summation1.

def summation1(f:Int=>Int):((Int,Int)=>Int) = {
 def FSum(a:Int, b:Int):Int = {
  
  def loop(a:Int, acc:Int):Int = {
   if(a>b) acc
   else
    loop(a+1,f(a)+acc)
  } 
  loop(a,0)
 }  
 FSum
} 

The advantage is that we can create different flavors of summation function and then call them with proper arguments when required. The illustration is as follows.

def sqrSummation = summation1 (x=>x*x)    //> sqrSummation: => (Int, Int) => Int
sqrSummation(5,7)                         //> res1: Int = 110
  
def cubicSummation = summation1 (x=>x*x*x)//> cubicSummation: => (Int, Int) => Int
sqrSummation(1,3)                         //> res2: Int = 14
 
def factoSummation = summation1(fact)     //> factoSummation: => (Int, Int) => Int
factoSummation(3,5)                       //> res3: Int = 150

summation1(x=>x)(1,10)                    //> res4: Int = 55

Taking currying to the advanced level - Rather than having a sub function being returned by a function, we can logically aggregate the parameters into the same function by passing them in separate groups. This will help in reusing the function.

Q. Can we have a series function which will do operation x (instead of only summation) and at the same time apply a function (e.g. square, cube, factorial) on the element before adding it to the result? Most importantly can it be designed in a reusable fashion?

The answer is yes. Following is the series function where Op is a function which takes two arguments and returns an integer value. Op can be summation, product or any other operation. The acc value can be 0 for summation or 1 for product which represents the unit value with respect to the operation.

def series(Op: (Int, Int) => Int, acc: Int)(f: Int => Int)(a: Int, b: Int): Int =
    if (a > b) acc
    else series(Op, Op(f(a), acc))(f)(a + 1, b)

The function can be used to do summation of squares of numbers between 1 to 5.

series((x,y)=>x+y,0)(x=>x*x)(1,5)               //> res0: Int = 55

The function can be used to define factorial function.

def fact (n:Int):Int =
 series((x,y)=>x*y,1)(x=>x)(1,n)           //> fact: (n: Int)Int
 
fact(5)                                   //> res1: Int = 120

Scala program for Counting change for a given amount and denominations

Problem Statement

Write a recursive function that counts how many different ways you can make change for an amount, given a list of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomiation 1 and 2: 1+1+1+1, 1+1+2, 2+2.

How to think
First of all, sort the denomination set in ascending order.

Thumb Rule = Let a is the amount for which you have to find all the possible ways from a given denominations set S. Then the number of possible ways amount a can be achieved is equal to

• number of ways the amount a-S_max can be achieved using S +
• number of ways a can be achieved using S' = S - S_max i.e. removing the max element from S

Apart from the implementation of thumb rule, check that

1. if amount is negative, then we have crossed the limit and no way possible, so return 0
2. if amount is equal to 0, then the change has achieved through this branch, hence return 1
3. if max index is out of bound, then return 0

Program
Following function takes the amount and denomination's set, and returns the count of number of possible ways of getting change for the amount.

def countChange(money: Int, coins: List[Int]): Int = {

    val sortedCoins = coins.sorted

    def getCount(amount: Int, maxIndex: Int): Int = {

      if (amount < 0) 0
      else if (amount == 0) 1
      else if (maxIndex < 0) 0
      else getCount(amount - sortedCoins(maxIndex), maxIndex) + getCount(amount, maxIndex - 1)
    }

    getCount(money, coins.size - 1)
  }

Pascal's Triangle in Scala

To understand the recursive logic of Pascal's triangle, draw a sample triangle as follows.

r,c	0	1	2	3	4	5	6
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1

Now, pick a a column(c) and row(r) value. You will find that,

(c,r) = (c-1,r-1)+(c,r-1)

The program in Scala is as follows.

Program

object Main {
  def main(args: Array[String]) {
    println("Pascal's Triangle")
    for (row <- 0 to 10) {
      for (col <- 0 to row)
        print(pascal(col, row) + " ")
      println()
    }

  }

  def pascal(c: Int, r: Int): Int = {
    if (c == 0 || c == r) 1
    else
      pascal(c - 1, r - 1) + pascal(c, r - 1)
  }

Output

Pascal's Triangle
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 
1 10 45 120 210 252 210 120 45 10 1