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