Fundamental

Primitive Types

Primitive types in Scala are like the ones in Java, but they are capitalized

• Int: 32-bit integers
• Long: 32-bit integers
• Float: 32-bit floating point numbers
• Double: 64-bit floating point numbers
• Char: 16-bit unicode characters
• Short: 16-bit integers
• Byte: 8-bit integers
• Boolean: boolean values true and false

scala> val x = 23
val x: Int = 23

Expression

Scala supports functional programming quite well. Many items are expressions in Scala, though in many other languages they are not treated as expressions. For example the if...then...else expression

val x = if true then 10 else 20

A block is denoted by a pair of curly braces {}. A block is an expression, and it uses the last expression as its value.

val x = {
  val y = 10
  y + 5
}
// the block is evaluated to 15, so x is 15

In Scala 3, braces are optional, so below code snippet is valid.

scala> val x2 =
     |  val y2 = 20
     |  y2 * 3
     |
val x2: Int = 60

To declare a variable, use var. However, following functional programming style, mutation is encouraged, and use val in immutation case.

val x = 1
val y: Int = 2
var sum = 0

Evaluation

To evaluate an expression

1. Take the leftmost operator.
2. Evaluate its operands, left to right for multiple operands case.
3. Apply the operator to the operands.

There are two evaluation strategies regarding function invocation

• Applicative order(call by value): reduce function arguments to values before rewriting function application
  • by default used in Scala
  • the expression evaluates at most once
• Normal order(call by name): apply function directly without reducing arguments first
  • use => to indicate normal order before parameters in function signature
  • no need to do unnecessary evaluation

The two evaluation strategies reduce to the same final result as long as

• The reduce expression consists of pure function.
• Both evaluations terminate.

Below is an example showing how ‘impure’ function evaluates to different results in applicative order and normal order.

import scala.util.Random

def squareA(x: Int): Int = x * x
def squareN(x: => Int): Int = x * x

@main
def main = {
  val rnd = new Random()
  val resultA = squareA(rnd.nextInt(10)) 
  println(s"Got a square(A) value: $resultA")
  // below evaluates to `rnd.nextInt(10) * rnd.nextInt(10)`
  val resultN = squareN(rnd.nextInt(10)) 
  println(s"Got a square(N) value: $resultN")
}

Normal order evaluation does NOT do unnecessary evaluation.

// define infinite loop
def loop: Boolean = loop

// define normal order function
def constOne(x: Int, y: => Boolean) = 1

// y follows normal order evaluation, so it is NOT evaluated at all.
constOne(2, loop) // won't trigger infinite loop

Scala uses short-circuit evaluation for && and ||. As a result, true || loop terminates.

Recursion

Recursion is widely used in FP, but it prevents the compiler from inferring the function’s return type, requiring an explicit type declaration in the function signature.

def fact(n: Int): Int =
  require(n >= 0, "parameter should NOT be negative")
  if n == 0 then 1 else n * fact(n-1)

Tail Recursion

Tail recursion is supported in Scala. The @tailrec annotation is more like a reminder, because even if the annotation is not present, the Scala compiler will still try to make recursion tail-recursive whenever possible

def fact(n: Int): Int =
  require(n >= 0, "parameter should NOT be negative")

  @tailrec
  def factTR(curr: Int, accu: Int): Int = 
    if curr == 0 then accu else factTR(curr-1, accu*curr)
  factTR(n, 1)

Higher Order Function

Functions are treated as first-class citizens in Scala. That means functions can be parameters and return values of functions. Functions that take other functions as parameters or return functions as return values are called higher order functions(HOF).

But why does that matter? HOF provides a flexible way to compose functions.

def sumOfSquare(lowerBound: Int, upperBound: Int): Int =
  require(lowerBound <= upperBound, "Lower bound should NOT exceed upper bound.")
  if lowerBound == upperBound then lowerBound*lowerBound else lowerBound*lowerBound + sumOfSquare(lowerBound+1, upperBound)

def sumOfDouble(lowerBound: Int, upperBound: Int): Int =
  require(lowerBound <= upperBound, "Lower bound should NOT exceed upper bound.")
  if lowerBound == upperBound then upperBound*2 else lowerBound*2 + sumOfDouble(lowerBound+1, upperBound)
  

The behavior of above two functions is very similar to each other. We can ’extract’ the different part, and introduce a function to ‘abstract’ the behavior like below

def sumOfFn(lowerBound: Int, upperBound: Int, fn: Int => Int): Int =
  require(lowerBound <= upperBound, "Lower bound should NOT exceed upper bound.")
  if lowerBound == upperBound then fn(lowerBound) else fn(lowerBound) + sumOfFn(lowerBound+1, upperBound, fn)

# to get sum of square from 3 to 6
sumOfFn(3, 6, x => x*x)

There is still hard code in above implementation, the + operation. If we extract that part, and introduce a function, we actually implement the map-reduce operation.

def mapReduce(lowerBound: Int, upperBound: Int, map: Int => Int, reduce: (Int, Int) => Int): Int =
  require(lowerBound <= upperBound, "Lower bound should NOT exceed upper bound.")
  if lowerBound == upperBound then map(lowerBound)
  else reduce(map(lowerBound), mapReduce(lowerBound+1, upperBound, map, reduce))

# sum of square from 3 to 6
mapReduce(3, 6, x => x*x, (a, b) => a+b)

Anonymous Functions

In above sumOfFn and mapReduce cases, anonymous functions are passed as arguments to the functions.

val doubleFn = (x: Int) => x * 2

Note

• To explicitly declare the return type of function like (x: Int): Int => x*2 is NOT legal.
• Usually the return type of the function can be inferred, but if we’d like to explicitly denote the return type, we declare it on the identifier like val cube: Int => Int = x => x*x*x

Function Currying

When invoking above mapreduce function, we need to provide all four parameters. Think about below cases

• sum of square from 3 to 5
• sum of double from 2 to 6
• sum of cube from 5 to 7

In above cases, the reduce function is sum, and we need to repeatedly provide it in each invocation. It would be better if we can make an ‘intermediate’ function that is fixed to sum as reduce logic. To do that we utilize function currying.

// mapReduce via function currying
def mapReduce(reduce: (Int, Int) => Int) (map: Int => Int) (lowerBound: Int, upperBound: Int): Int =
  require(lowerBound <= upperBound, "Lower bound should NOT exceed upper bound.")
  if lowerBound == upperBound then map(lowerBound)
  else reduce(map(lowerBound), mapReduce(reduce)(map)(lowerBound+1, upperBound))

// As usual we can provide all the parameters
mapReduce((a: Int, b: Int)=>a+b) ((x:Int)=>x*x) (3,5)

The mapReduce function has type ((Int, Int) => Int) => (Int => Int) => (Int, Int) => Int, which forms a chain of functions.

scala> mapReduce
val res0: ((Int, Int) => Int) => (Int => Int) => (Int, Int) => Int = Lambda/0x0000026581544c10@5b74902c

That makes partial application available. Partial application returns an ‘intermediate’ function. Note

• Function types associate to the right, so Int => Int => Int means Int => (Int => Int).
• Function invocation assoticates to the left, so myFun(1)(2) means (myFun(1))(2).

// partial application with `reduce` function provided
scala> val sumOfFn = mapReduce((a: Int, b: Int) => a+b)
val sumOfFn: (Int => Int) => (Int, Int) => Int = Lambda/0x0000026581570410@1397b141

scala> sumOfFn((x: Int) => x*x)(3,5)
val res1: Int = 50

scala> sumOfFn((x: Int) => x*x*x)(3,5)
val res2: Int = 216

// further partial applicaiton with `map` function provided
scala> val sumOfQuad = sumOfFn((x: Int) => x*4)
val sumOfQuad: (Int, Int) => Int = Lambda/0x0000026581572000@2bc8caa7

scala> sumOfQuad(3, 6)
val res3: Int = 72

scala> sumOfQuad(5, 9)
val res4: Int = 140

Object Oriented Programming with Scala

Scala can be used in functional programming style, but it also supports object oriented programming well.

Simple Introduction to Classes

To define a class

class Robot(val robotName: String, height: Int):
  val robotHeight = height
  def introSelf(target: Robot) : String =
    s"Hello ${target.robotName}, I am ${this.robotName}"
    
@main
def main =
  val arale = new Robot("Arale", 139)
  val wallE = new Robot("wallE", 100)
  println(arale.introSelf(wallE))
  println(s"WallE's height is ${wallE.robotHeight}")

Note

• Don’t forget the colon : at the end of the ‘class definition’ line.
• val robotName: String makes robotName a public field and available from outside of the class.
  • Without val in front of robotName, robotName would not be treated as a filed, it’s only visible inside of the class, and target.robotName would cause syntax error.
• robotHeight is defined as a value, which represents one attribute of the class.
• this keyword represents the current object of the class.

Data Abstraction with Classes

Classes can be used to describe data and behavior. For example, below class represents a rational number

// define a class without explicit class body
class Rational(val numerator: Int, val denominator: Int)

// try it in Scala REPL
scala> val r1 = Rational(15, 55)
val r1: Rational = Rational@a4dcede

scala> r1.numerator
val res10: Int = 15

scala> r1.denominator
val res11: Int = 55

Explanation

• val before the class parameters (numerator and denominator) make those parameters available to the outside of the class. Otherwise, they can only be visited inside of the class.

Reduction of fraction is a common operation to rational numbers.

class Rational(val numerator: Int, val denominator: Int):
  // greatest common divisor
  private def gcd(a: Int, b: Int): Int =
    if b == 0 then a else gcd(b, a%b)
  def numer = numerator/gcd(numerator, denominator)
  def denom = denominator/gcd(numerator, denominator)
  override def toString = s"$numerator/$denominator[$numer/$denom]"

// try in REPL
scala> val r1 = Rational(15, 55)
val r1: Rational = 15/55[3/11]

In above implementation, gcd is repeatedly called each time numer or denom is called. To prevent that, refine the implementation as

// refine Rational implementation to remove duplicate call on gcd
class Rational(val numerator: Int, val denominator: Int):
  private def gcd(a: Int, b: Int): Int =
    if b == 0 then a else gcd(b, a%b)
  private val divisor = gcd(numerator, denominator)
  def numer = numerator/divisor
  def denom = denominator/divisor
  override def toString = s"$numerator/$denominator[$numer/$denom]"

// try in REPL
scala> val r2 = Rational(27, 90)
val r2: Rational = 27/90[3/10]

From the caller perspective, it may not realize the refinement at all, because the way how it interacts with Rational remains the same. The ability to choose different implementations of the data without affecting clients is called data abstraction.

Extension Methods

Extension methods allow use toe expand the behavior of a class. Some typical cases are

• Operations that feel like they “should” be part of a type but aren’t.
• Domain-specific operations on thrid-party or standard library types, when we cannot modify the original class but want to add domain-specific behavior.

For example, in above Rational case, suppose Rational class is defined as a standard library class. We cannot modify the “original” standard libraray code, but we can utilize extention methods to implement operations like abs, min and etc., so that we “expand” the feature of Rational.

class Rational(val numerator: Int, val denominator: Int):
  private def gcd(a: Int, b: Int): Int =
    if b == 0 then a else gcd(b, a%b)
  private val divisor = gcd(numerator, denominator)
  def numer = numerator/divisor
  def denom = denominator/divisor
  override def toString = s"[$numer/$denom]"

extension (r: Rational)
  def abs: Rational = Rational(r.numer.abs, r.denom.abs)
end extension

// run in REPL
scala> val myNumber = new Rational(-2, 5)
val myNumber: Rational = [-2/5]

scala> myNumber.abs
val res0: Rational = [2/5]

Note

• Unlike class, there is no trailing colon on extension line.
• r in extension(r: Rational) is known as extension parameter.
• Define parameterless function abs without a pair of empty parentheses to indicate no side effect.
• Extentions can only add new members, not override existing ones.

Different people may define extensions in different modules so that they can have their own versions of enhancement that don’t run into others. Extensions of a class become available if they are

• defined or imported in the current scope
• listed in the companion object

Infix Notation

Operators like +, - and etc. are identifiers, and they can be used as function names.

class Rational(val numerator: Int, val denominator: Int):
  private def gcd(a: Int, b: Int): Int =
    if b == 0 then a else gcd(b, a%b)
  private val divisor = gcd(numerator, denominator)
  def numer = numerator/divisor
  def denom = denominator/divisor
  override def toString = s"[$numer/$denom]"
  def +(o: Rational): Rational =
    new Rational(numer*o.denom+denom*o.numer, denom*o.denom)

extension (r: Rational)
  def abs: Rational = Rational(r.numer.abs, r.denom.abs)
  def -(o: Rational) = 
    new Rational(r.numer*o.denom-r.denom*o.numer, r.denom*o.denom)
end extension

With above + method and - method defined, they can be used as infix notation

// run in REPL
scala> val r1 = new Rational(2,3)
val r1: Rational = [2/3]

scala> val r2 = new Rational(1,5)
val r2: Rational = [1/5]

scala> r1 + r2
val res0: Rational = [13/15]

scala> r1 - r2
val res1: Rational = [7/15]

Explanation

• Those infix notation functions can be defined in either classes or extensions.
• If the identifier is not symbolic, such as min, the leading infex modifer is mandatory.

extension (r: Rational)
  def abs: Rational = Rational(r.numer.abs, r.denom.abs)
  def -(o: Rational) = 
    new Rational(r.numer*o.denom-r.denom*o.numer, r.denom*o.denom)
  infix def min(o: Rational) =
    if r.numer * o.denom <= o.numer * r. denom
    then r
    else o
end extension

Abstraction and Class Hierarchies

Programming to abstractions rather than concrete implementations is a cornerstone principle behind most design patterns. In Scala, we can define abstract classes to follow that principle. Suppose we need a type to represent a set of integer numbers. We can have below abstraction.

abstract class IntSet:
  def include(x: Int): IntSet
  def contains(x: Int): Boolean

One implementation for above IntSet is binary trees. For instance, if we have the IntSet {1, 2, 4, 5}, below is the corresponding binary tree

Obviously two types of nodes are needed.

• Empty node
• NonEmpty node

class Empty() extends IntSet:
  def include(x :Int): IntSet = NonEmpty(x, Empty(), Empty())
  def contains(x: Int): Boolean = false
  override def toString = "<E>"

class NonEmpty(elem:Int, left: IntSet, right: IntSet) extends IntSet:
  def include(x: Int): IntSet =
    if x > elem then NonEmpty(elem, left, right.include(x))
    else if x < elem then NonEmpty(elem, left.include(x), right)
    else this
  def contains(x: Int): Boolean =
    if x > elem then right.contains(x)
    else if x < elem then left.contains(x)
    else true
  override def toString = s"($elem, ${left.toString}, ${right.toString})"

Explanation

• extends keyword denotes the subclass-superclass relationship.
  • A class defined without extends actually extends Objct class, which is java.lang.Object.
  • The direct or indirect superclass of a class is called base class. For instance, IntSet and Object are base classes of Empty class.
• override is a modifer, instead of an annotation in Scala. It denotes to override the exsiting method defined in base class.

// run in REPL
scala> val intSetA = Empty().include(1).include(4).include(5).include(2)
val intSetA: IntSet = (1, <E>, (4, (2, <E>, <E>), (5, <E>, <E>)))

scala> val intSetB = Empty().include(4).include(1).include(5).include(2)
val intSetB: IntSet = (4, (1, <E>, (2, <E>, <E>)), (5, <E>, <E>))

object for Singleton

In above IntSet implementation, Empty is defined as a class, meaning multiple instances of Empty will be created, and that’s a waste. To fix that defect, use object type to implement singleton.

object Empty extends IntSet:
  def include(x :Int): IntSet = NonEmpty(x, Empty, Empty)
  def contains(x: Int): Boolean = false
  override def toString = "<E>"
end Empty // optional end marker

Note

• Empty now is object type and we cannot create instance of it anymore. To reference it, simply use Empty.
• Singleton objects are values, so Empty evaluates to itself.

Companion object

When a class type and an object type are defined in the same source file with the same name, they are called companions. Note

• The companion object must be defined in the same source file as its companion class.
• If they are defined in separate files, they are just a regular class and a regular objct that happen to have the same name.

A companion object of a class plays a role similar to static class definitions in Java.

object for Program Entry Point

To build a standalone application/program, create an object type with main method

object Hello:
  def main(args: Array[String]): Unit =
    println("Hello from Scala!")

A common best practice is to name the source file after the object it defines, so name the source file Hello.scala

To execute the program

C:\sandbox\ScalaLab\Scripts> scala run Hello.scala
Compiling project (Scala 3.7.4, JVM (21))
Compiled project (Scala 3.7.4, JVM (21))
Hello from Scala!

Alternatively, we can compile the source to class files using scala compile, and then run the program. Notice in Scala 3, powered by Scala CLI, a unifed scala command with subcommands like compile, run, repl, test, etc. are introduced. The old scalac and scala still exist for backward compatibility.

Using scala compile, class files are generated under .scala-build/ directory by default.

Dynamic Method Binding

Method invocation depends on the runtime type of the object.

class Robot(val name: String):
  def greet(target: String): String =
    s"Hi $target, this is Robot[$name]."

class CleaningRobot(name: String) extends Robot(name):
  override def greet(target: String): String =
    s"Greeting from CleaningRobot[$name]: Hello $target."

@main
def main() =
  val wallE: Robot = new CleaningRobot("Wall-E")
  println(wallE.greet("EVE"))

Explanation

• wallE is declared as Robot type, but assigned to an instance of CleaningRobot.
• The method invocation depends on the runtime type, so the greet defined in CleaningRobot is invoked.

Organize Classes with Packages

Classes and objects are organized in packages. To place a class/object type inside a package, use package keyword at the top of the source file. For example

package id.my.cxu.examples

object Hello:
  def main(args: Array[String]): Unit =
    println("Hello from Scala!")
    
  def sayHello(target: String) = s"Hello, $target"

Now compile the source file.

C:\sandbox\ScalaLab\Scripts> scala compile Hello.scala
Compiling project (Scala 3.7.4, JVM (21))
Compiled project (Scala 3.7.4, JVM (21))

C:\sandbox\ScalaLab\Scripts> fd -H .*Hello
.scala-build/.bloop/Scripts_86c27f223b-f4d7975d63/bloop-internal-classes/main-3F_GeVW0Sx2WzkmaZblELw==/id/my/cxu/examples/Hello$.class
.scala-build/.bloop/Scripts_86c27f223b-f4d7975d63/bloop-internal-classes/main-3F_GeVW0Sx2WzkmaZblELw==/id/my/cxu/examples/Hello.class
.scala-build/.bloop/Scripts_86c27f223b-f4d7975d63/bloop-internal-classes/main-3F_GeVW0Sx2WzkmaZblELw==/id/my/cxu/examples/Hello.tasty
.scala-build/Scripts_86c27f223b-f4d7975d63/classes/main/id/my/cxu/examples/Hello$.class
.scala-build/Scripts_86c27f223b-f4d7975d63/classes/main/id/my/cxu/examples/Hello.class
.scala-build/Scripts_86c27f223b-f4d7975d63/classes/main/id/my/cxu/examples/Hello.tasty
Hello.scala

Explanation

• One common best practice is to construct the same directory structure for srouce file. So in above case, the Hello.scala is supposed to be put under id/my/cxu/examples, but that’s not mandatory.
• In above example, the ‘qualified name’ of the Hello is id.my.cxu.examples.Hello. The compilation operation generates the directories according to the package.

To reference to the type, use the qualified name including both package name and class name.

@main
def main() =
  val greeting = id.my.cxu.examples.Hello.sayHello("Wall-E")
  println(greeting)
  

Execute above script file (namely lab.scala) with -cp to indicate the path of the dependent class file.

C:\sandbox\ScalaLab\Scripts> scala run -cp .scala-build\Scripts_86c27f223b-f4d7975d63\classes\main lab.scala
Compiling project (Scala 3.7.4, JVM (21))
Compiled project (Scala 3.7.4, JVM (21))
Hello, Wall-E

Arguably, a better way to run the script is to provide both the entry point and the dependent files together. However, in above case, there are two ’entry points’. To prove that point, use the command scala run --main-class-ls <scala_files> to list the available entry points of the scala files.

C:\sandbox\ScalaLab\Scripts> scala run --main-class-ls Hello.scala lab.scala
Warning: setting C:\Sandbox\ScalaLab\Scripts as the project root directory for this run.
Compiling project (Scala 3.7.4, JVM (21))
Compiled project (Scala 3.7.4, JVM (21))
id.my.cxu.examples.Hello main

Explanation: the command returns two entry points

• id.my.cxu.examples.Hello
  • Now we need to use the qualified name, instead of simply Hello to refer to the Hello object.
• main

The desired entry point in this case is main, so we execute the command scala run -M main Hello.scala lab.scala

C:\sandbox\ScalaLab\Scripts> scala run -M main Hello.scala lab.scala
Warning: setting C:\Sandbox\ScalaLab\Scripts as the project root directory for this run.
Hello, Wall-E

Explanation

• -M option denotes the ’entry point’/‘main class’ to run. In above script case, namely that’s main.

Import Classes

Using the qualified name of a class seems combersome, and we can ‘import’ the class to simplify the reference form. There are two types import

• named import, such as import id.my.cxu.examples.Hello to just import the Hello object
• wildcard import, such as import id.my.cxu.examples._ to import everything in the id.my.cxu.examples package.
  • Notice the wildcard is underscore, NOT asterisk.

We can import types from either of the following:

• a package
  • conceptually, a package is a ’large’ object that contains many members in several individual source files.
• an object

So refine above script file as

@main
def main() =
  import id.my.cxu.examples.Hello
  val greeting = Hello.sayHello("Arale")
  println(greeting)
  

Notice some items are automatically imported in every Scala program.

• members of package scala
• members of package java.lang
• members of the singleton object scala.Prefe

That’s the reason why some types and functions seem available ’natually’, for example

• Int (defined inscala.Int)
• Boolean (defined in scala.Boolean)
• Object (defined in java.lang.Object)
• require (defined in scala.Predef.require)
• assert (defined in scala.Predef.assert)

Traits

A class may have several natural supertypes, and that is implemented with traits in Scala. A class can inherit from

• at most one class
• arbitrary many traits

A trait is declared like an abstract class

trait Movable:
  def move(): Unit

trait Soundable:
  def sound: String

class Robot extends Movable, Soundable:
  def move() = println("Robot is moving")
  def sound = "Robot is talking"

@main
def main =
  val arale = new Robot()
  arale.move()
  println(arale.sound)

Explanation

• Class Robot extends two traits in above example.

Class Hierarchy

Explanation

• scala.AnyVal is the super type of all the primitive types.
• scala.AnyRef is the synonym of java.lang.Object, and it’s the super type of the user defined class.
• Root type of the type system is scala.Any.
  • Methods like ==, !=, equals, hashCode, toString are defined there.
• Bottom type of the type system is scala.Nothing.
  • Nothing is the subtype of every other type.
  • Nothing is a type, and there is no value of type Nothing, so we cannot assign Nothing to an identifier.
  • Use case of Nothing type: as an element type of empty collections.
• Notice two types of arrows
  • Solid line arrows: conform to the super class
  • Dashed line arrows: implicit conversion

A Tricky Type Question

Given below expression, what’s the type of it?

if true then 1 else false

In Scala 2, we get the common supertype of Int and Boolean, so we end up getting type AnyVal. However in Scala 3, we get Int | Boolean, the union type, which represents a value that can be either an Int or Boolean.

By design, the compiler does NOT look into the condition, although it’s even fixed as true.

Polymorphism

Polymorphism is one of the pillars of OOP. To help understand and remember the word

• poly: it means many
• morphism: it means forms

In programming, polymorphism means

• the identify of a certain instance can be viewed as many different types
• the function can be applied to arguments of many types

class Robot(val name: String, val model: String):
  def move(): Unit = println("Robot is moving...")

class HumanoidRobot(name: String, model: String) extends Robot(name, model):
  def talk(): Unit = println(s"HumanoidRobot[$name] is talking...")

class Arale(robotID: String) extends HumanoidRobot("Arale-"+robotID, "Arale"):
  override def move(): Unit = println(s"$name is running...")

@main
def main() =
  val a01: Robot = new Arale("a01")
  a01.move()
  val a02: HumanoidRobot = new Arale("a02")
  a02.talk()
  a02.move()


// running above program and we get
scala run PolyLab.scala
Compiling project (Scala 3.7.4, JVM (21))
Compiled project (Scala 3.7.4, JVM (21))
Arale-a01 is running...
HumanoidRobot[Arale-a02] is talking...
Arale-a02 is running...

Explanation

• a01 is declared as type Robot, but in fact it is an instance of Arale. Due to dynammic method binding, the effective method for a01.move() invocation is the one defined in Arale.
• a02 is an instance of Arale, and it can be recognized as an instance of HumanoindRobot as well, so a02.talk() works.

Generics

Suppose we need to implement the linked list data structure. Below is a simple design

• Nil to represent the empty list
• Cons to represent a cell containing an element, and the remainder (tail) of the list

For a list like List(1, 2, 3), above design looks like

The implementation can be

import java.{util => ju}

trait IntList:
  def isEmpty: Boolean
  def head: Int
  def tail: IntList

class Cons(val head: Int, val tail: IntList) extends IntList:
  def isEmpty: Boolean = false
  override def toString = s"$head | ${tail.toString}"

object Nil extends IntList:
  def isEmpty = true
  def head = throw new ju.NoSuchElementException()
  def tail = throw new ju.NoSuchElementException()
  override def toString = "<Nil>"

@main
def main() =
  val myList = Cons(1, Cons(2, Cons(3, Nil)))
  println(myList)


// execute and we get
scala run IntList.scala
Compiling project (Scala 3.7.4, JVM (21))
Compiled project (Scala 3.7.4, JVM (21))
1 | 2 | 3 | <Nil>

Explanation

• val head: Int and val tail: IntList of Cons fulfill the head and tail methods defined in IntList.
• To create multiple instances of Nil does NOT make a lot of sense, so define it as object type.

It’s easy to create types like BooleanList, StringList, etc. In fact, the only difference among those types is the type of the inner stored elements. To ‘generalize the type’, we can use Type Parameters.

import java.{util => ju}

trait MyList[+T]:
  def isEmpty: Boolean
  def head: T
  def tail: MyList[T]

class Cons[T](val head: T, val tail: MyList[T]) extends MyList[T]:
  def isEmpty: Boolean = false
  override def toString = s"$head | ${tail.toString}"

object Nil extends MyList[Nothing]:
  def isEmpty = true
  def head = throw new ju.NoSuchElementException()
  def tail = throw new ju.NoSuchElementException()
  override def toString = "<Nil>"

@main
def main() =
  val myNumList: MyList[Int] = Cons(1, Cons(2, Cons(3, Nil)))
  println(myNumList)
  val myStrList : MyList[String] = Cons("Hello", Cons("From", Cons("Scala", Nil)))
  println(myStrList)

Explanation

• The plus sign in MyList[+T] makes MyList covariant, which means an instance of MyList[DerivedType] can be considered as an instance of MyList[BaseType].
• object Nil extends MyList[Nothing] makes Nil to be an sub-type of MyList[Nothing], which in turn makes Nil an sub-type of any MyList[+T].
  • Technically, object Nil extends MyList also works, but explicitly denoting Nothing makes the type relationship crystal clear.

Objects for OOP

In pure object-oriented programming language, every value is an object. To understand the point, let’s follow this idea to create an ideal version of Boolean type and values.

abstract class IdealBoolean:
  def ifThenElse[T](t: => T, e: => T): T
  
  def &&(x: => IdealBoolean): IdealBoolean =
    ifThenElse(x, IdealFalse)
    
  def ||(x: => IdealBoolean): IdealBoolean = 
    ifThenElse(IdealTrue, x)
    
  def unary_! : IdealBoolean =
    ifThenElse(IdealFalse, IdealTrue)
    
  def ==(x: => IdealBoolean): IdealBoolean =
    ifThenElse(x, x.unary_!)
    
  def !=(x: => IdealBoolean): IdealBoolean =
    ifThenElse(x.unary_!, x)

object IdealTrue extends IdealBoolean:
  def ifThenElse[T](t: => T, e: => T): T = t
  
object IdealFalse extends IdealBoolean:
  def ifThenElse[T](t: => T, e: => T): T = e

Explanation

• IdealBoolean is an abstract class defining the behavior of the type.
• There are only two possible values for IdealBoolean type, IdealTrue and IdealFalse. It doesn’t make a lot of sense to create different instances of IdealTrue and IdealFalse, so they are defined as object

Functions as Objects

In Scala, a function can be treated as an object. The function type A => B is just an abbreviation of the type scala.Function[A, B], just as below

package scala

trait Function1[A, B]:
  def apply(x: A): B

Explanation

• Functions are objects with apply methods.
• The name of the trait in above example is Function1, and there are traits named as Function2, Function3, etc., for functions which have more parameters.

Let’s create equivalent integer sum functions using anonymous function and Function2 trait

@main
def main() =
  val intSumFn: (Int, Int) => Int = (a, b) => a + b
  val intSumFn2: Function2[Int, Int, Int] = new Function2[Int, Int, Int]:
      def apply(a: Int, b: Int): Int = a + b

  val cmpr = intSumFn(2,3) == intSumFn2(2,3)
  println(cmpr) // true
  println(intSumFn == intSumFn2) // false

Explanation

• Funciton2 is an trait, so it’s impossible to create a ‘direct’ instance. As a result, ‘anonymous class’ is used to create an ‘indirect’ instance of Function2.
• Although logically intSumFn and intSumFn2 are the same thing, they are not equivalent.

With above concept in mind, we now have two ways to invoke a function

• regular function call such as fn(args)
• using apply like fn.apply(args)

@main
def main() =
  val intSumFn: (Int, Int) => Int = (a, b) => a + b
  println(intSumFn(5, 91))
  println(intSumFn.apply(5, 91))

  def intSumFn3(a: Int, b:Int): Int = a + b
  println(intSumFn3(5, 23))
  println(intSumFn3.apply(5, 23))

Exaplantion

• intSumFn is an anonymous function and intSumFn3 is a regular function. We can use either regular function call or the apply function of the function object.

OO Decomposition vs Pattern Matching

Suppose we need to build a dummy interpretor and for demo purpose, let’s consider below entities with integer nubmers for now

• Expr: the abstract type to represent expressions, and for now only consider integer numbers
• Number: to represent numbers, and for demo purpose only consider integer numbers for now
• Sum: to represent addition operation, and for now only consider integer numbers

OO Decomposition

One solution to build the interpretor is like below, via OO decomposition

trait Expr:
  def eval: Int

class Number(n: Int) extends Expr:
  def eval: Int = n

class Sum(left: Expr, right: Expr) extends Expr:
  def eval: Int = left.eval + right.eval

@main
def main() =
  val e1 = Number(2)
  val e2 = Sum(Number(2), Number(5))
  val r = Sum(e1, e2).eval
  print(r)

Explanation

• Expr is defined as a trait and it is abstract type.
• Number contains both data(n) and operation(eval).
• Similar to Number, Sum contains both data(left and right) and operation(eval)

But why is it called OO decomposition, given the fact that data is not separated from opertions?

• “Decomposition” here means to decompose a complex system into cohesive units with clear responsibilities. So in OO territory, it’s the idea of breaking a system down into objects, each representing a concept in the problem domain. An object encapsulates both state(data) and behavior(operations).

Above implementation decompose the problem domain into Expr trait, Number class and Sum class. The responsiblity is clear, so to some extent that’s a good design. Suppose we need to add new entities/data such as Prod to represent multiplication, it’s still quite easy.

class Prod(left: Expr, right: Expr) extends Expr:
  def eval: Int = left.eval * right.eval

However if we need to add a new behavior, such as a display method, now that’s a problem, because every type needs to be updated.

trait Expr:
  def eval: Int
  def display: String

class Number(n: Int) extends Expr:
  def eval: Int = n
  def display: String = n.toString

class Sum(left: Expr, right: Expr) extends Expr:
  def eval: Int = left.eval + right.eval
  def display: String = s"${left.display} + ${right.display}"

@main
def main() =
  val e1 = new Number(2)
  val e2 = new Sum(new Number(2), new Number(5))
  val e = new Sum(e1, e2)
  print(s"${e.display} = ${e.eval}")

Note: using OO decomposition, it’s

• easy to add new kinds of entities/data
• hard to add new operations

FP Decomposition - Pattern Matching

Another approach to implement the interpretor is to utilize pattern matching.

trait Expr
case class Number(n: Int) extends Expr
case class Sum(left: Expr, right: Expr) extends Expr

def eval(expr: Expr): Int = expr match
  case Number(n: Int) => n
  case Sum(left: Expr, right: Expr) => eval(left) + eval(right)

@main
def main() =
  val e1 = Number(91)
  val e2 = Sum(Number(2), Number(3))
  val e = Sum(e1, e2)
  println(s"${eval(e)}")

Explanation

• We use case classes to represent numbers and operations, because classes have below ‘automatic’ features
  • immutability by default: all constuctor parameters are automatically val fields (public and immutable).
  • proper equals() and hashCode(): automatically get proper euqals() and hashCode() to compare based on field values, not object identity.
  • pattern matching support: can be used in pattern matching with automatically generated unapply method.
  • companion object: automatically get a companion object with an apply method, so new keyword is not needed in instantiation.
  • copy method: automatically get a copy() method that creates modified copies while keeping other fields the same to support working with immutable data.
  • toString implementation: automatically get a readable toString implementation showing class name and field values.
• Pattern matching in above example
  • match is preceded by a selector expression, in above case expr.
  • A MatchError is thrown if no pattern matches the value of the selector expression.
  • Patterns are constructured from
    • constructors, e.g. Number(n)
    • variables, e.g. n, left
    • wildcard patterns, e.g. _ to match anything but don’t care about the value
    • constants, e.g. 1, true
    • type test, e.g. n: Int
  • some ruels and conventions of patterns
    • Variables always begin with a lowercase letter.
    • Names of constants begin with a Capital letter, with the exception of the reserved words like null, true, false.
    • The same variable name can only appear once in a pattern, so Sum(x, x) is NOT a valid pattern.

Now think about below bullets

• Move eval function into Expr trait to from a eval method.
• What if we’d like to add a display behavior?
• What if we’d like to add a Prod calculation?

trait Expr:
  
  def eval: Int = this match
    case Number(n: Int) => n
    case Sum(left: Expr, right: Expr) => left.eval + right.eval
    
  def display: String = this match
    case Number(n) => n.toString
    case Sum(l, r) => s"${l.display} + ${r.display}"
    
case class Number(n: Int) extends Expr
case class Sum(left: Expr, right: Expr) extends Expr


@main
def main() =
  val e1 = Number(91)
  val e2 = Sum(Number(2), Number(3))
  val e = Sum(e1, e2)
  println(s"${e.display} = ${e.eval}")

Explanation

• eval is transformed from a function to a method of Expr trait. Instead of accepting the expr parameter for pattern matching, it use the current instance, namely this, directly.
• display is added to Expr trait as another method. It also utilizes pattern matching technique.

It’s not that difficult to implement the first two bullets. However, to add additional data/entities, in this case Prod, all the pattern matching logic needs to be updated to ‘include’ that new data.

trait Expr:
  
  def eval: Int = this match
    case Number(n: Int) => n
    case Sum(left: Expr, right: Expr) => left.eval + right.eval
    case Prod(left: Expr, right: Expr) => left.eval * right.eval
    
  def display: String = this match
    case Number(n) => n.toString
    case Sum(l, r) => s"${l.display} + ${r.display}"
    case Prod(l:Sum, r:Sum) => s"(${l.display}) * (${r.display})"
    case Prod(l, r:Sum) => s"${l.display} * (${r.display})"
    case Prod(l:Sum, r) => s"(${l.display}) * ${r.display}"
    case Prod(l, r) => s"${l.display} * ${r.display}"
    
case class Number(n: Int) extends Expr
case class Sum(left: Expr, right: Expr) extends Expr
case class Prod(left: Expr, right: Expr) extends Expr


@main
def main() =
  val e1 = Number(91)
  val e2 = Sum(Number(2), Number(3))
  val e = Prod(e1, e2)
  println(s"${e.display} = ${e.eval}")

Note: using FP decomposition, pattern matching, it’s

• easy to add new operations
• hard to add new kinds of entities/data

Back to the implementation. The 4 adjacent Prod patterns look a little awkard. To improve the implementation, we can do a further pattern matching like below

trait Expr:
  
  def eval: Int = this match
    case Number(n: Int) => n
    case Sum(left: Expr, right: Expr) => left.eval + right.eval
    case Prod(left: Expr, right: Expr) => left.eval * right.eval
    
  def display: String = this match
    case Number(n) => n.toString
    case Sum(l, r) => s"${l.display} + ${r.display}"
    case Prod(l, r) => s"${{addParenthesesIfNecessary(l)}} * ${{addParenthesesIfNecessary(r)}}"
    
case class Number(n: Int) extends Expr
case class Sum(left: Expr, right: Expr) extends Expr
case class Prod(left: Expr, right: Expr) extends Expr

def addParenthesesIfNecessary(e: Expr): String = e match
  case Sum(l, r) => s"(${l.display} + ${r.display})"
  case _ => e.display

@main
def main() =
  val e1 = Number(91)
  val e2 = Sum(Number(2), Number(3))
  val e = Prod(e2, e1)
  println(s"${e.display} = ${e.eval}")

Expalnation

• addParenthesesIfNecessary adds parentheses to Sum expression.
• _ pattern matches to any value.

Types to Support Pattern Matching

A list looks like an array, but there are two important fundamental differences

• Lists are immutable
• Lists are recursive

It’s easy to understand ‘immutable’ mentioned above, but what does ‘recursive’ mean? A non-empty list consists of an element and a sub list. The cons operator : separates the head(element) and the tail(sub list) of a list. For example

@main
def main() =
  val l1 = List("US", "CN", "RU")
  val l2 = "US" :: "CN" :: "RU" :: Nil
  println(l1 == l2) // true
  println(l1 eq l2) // false
  println(Nil == List()) //true

Explanation

• l1 and l2 are two equivalent lists, but they are indeed two different objects.
• == tests the value equality and eq tests the reference equality.
• Nil is simply an empty list. When using :: to construct lists, do not forget to put Nil at the end of the list to indicate there is no more sub list.

Below are the three commonly used methods of lists

• head: to get the first element of the list
• tail: to get the sub list
• isEmpty: to return true if the list is empty, and otherwise false

List can be effectively used in pattern matching with understanding the underlying structure. Below are some examples

• 1 :: 2 :: xs: the list starting with element 1 and 2
• x: Nil: the list with one element
• List(x): same as above x :: Nil
• List(): the empty list, same as Nil
• List(2 :: xs): the list containing another list as its element, and the inner list starts with element 2

Utilize pattern matching to implement the insertion sort of lists

def insertionSort(l: List[Int]): List[Int] = l match
  case Nil => Nil
  case h :: Nil => l
  case h :: t =>
    val sortedTail = insertionSort(t)
    if h > sortedTail.head then sortedTail.head :: insertionSort(h :: sortedTail.tail)
    else h :: sortedTail
    
@main
def main() =
  val l = List(5, 8, 2, 9, 7, 3)
  val sortedL = insertionSort(l)
  println(sortedL)

Exaplanation

• insertionSort is a recursive function so the return type should be declared explicitly.
• Lists are immutable so the sorted list is a new list.