Scala notes II -- Functions

2019-05-26 programming

Function Syntax

Scala is a functional programming language, which means that functions are first-class citizens and you can pass them around as parameters or values.

def add(x: Int, y: Int): Int = {
  return x + y;
}
println(add(21, 19));
// Other variants
def multiply(x: Int, y: Int): Int = x * y  // simplified version
def divide(x: Int, y: Int) = x / y  // can ignore the output type if it's obvious
def substract(x: Int = 10, y: Int = 2) = x - y  // set default values

You can define the function names as operator, e.g. +, *, /, -

def +(x: Int, y: Int) = x + y

Partially applied functions

val sum = (a: Int, b: Int, c: Int) => a+b+c
val f = sum(10, 20, _:Int)
println(f(100)) // returns 130

import java.util.Date
def log(date: Date, message: String) = {
  println(date + "   " + message);
}
val date = new Date;
val newLog = log(date, _ :String);
newLog("The message 1.")
newLog("The message 2.")

Closures

A closure is a function which uses one or more variables declared outside this function.

var number = 10;

//Example 1
val add = (x:Int) => x + number;
println(add(20))

number = 100
println(add(20))  // If the value of the variable changes, the result changes too.

//Example 2
val add2 = (x:Int) => {
  number = x+number;
  number
}
println(add2(20))
println(number)  // numbder is 120 now

//Example 3
val number = 10;  // The result won't change since number is fixed.

Blocks and Lexical Scope

We can write nested functions in blocks to avoid name-space pollution. A block is delimited by braces { … } and it contains a sequence of definitions or expressions. The definitions inside a block are only visible from within the block. The definitions inside a block shadow definitions of the same names outside the block.

val x = 0
def f(y: Int) = y + 1
val result = {
  val x = f(3)  // x = 4, f() is visible inside the block
  x * x         // 16, x shadows the x outside the block
} + x           // + 0
// return 16

Recursive functions

Example:

def factorial(n: Int): Int =
  if (n == 0) 1 else n * factorial(n - 1)

This function has a buildup of intermediate results that we have to keep until we can compute the final value so it is not a tail recursive function.

Tail Recursion

If a function calls itself as its last action, the function’s stack frame can be reused. This is called tail recursion. In general, if the last action of a function consists of calling a function (which may be the same), one stack frame would be sufficient for both functions. Such calls are called tail-calls.

One can require that a function is tail-recursive using a @tailrec annotation. If the annotation is given and the implementation of a function is not tail recursive, an error would be issued.

Example:

@tailrec
def factorial(n: Int): Int = {
  def loop(acc: Int, n: Int): Int = 
    if (n == 0) acc 
    else loop(acc * n, n-1)
  loop(1, n)
}

The interest of tail recursion is mostly to avoid very deep recursive chains. If your input data are such that deep recursive chains could happen, then it’s a good idea to reformulate your function to be tail recursive, to run in constant stack frame, so as to avoid stack overflow exceptions.

On the other hand, if your input data are not susceptible to deep recursive chains then write your function the clearest way you can, which often is not tail recursive, and don’t worry about the stack frames that are spent. For example, the tail recursive function of factorial above grows very quickly even after very low number of recursive steps. So it is not worth making factorial a tail recursive function.

Higher-order functions

An important concept in functional programming is called higher-order function. It lets you pass functions as arguments and return them as results. For example,

def sum(a: Int, b: Int, f: Int => Int): Int = {
  if(a > b) 0
  else f(a) + sum(a+1, b, f)
}
def sumInts(a: Int, b: Int) = sum(a, b, x => x);  
def sumCubes(a: Int, b: Int) = sum(a, b, x => x * x * x)

The Int => Int is a function type that maps Int to Int.
The x => x and x => x * x * x are anonymous functions (aka function literals) that do not contain function names. Instead of defining a function cube, for example
```
def cube(x: Int): Int = x * x * x
```
the anonymous function x => x * x * x provides a lightweight function definition and is useful when we want to create an inline function.
More examples of anonymous functions:
```
(x, y) => _+_   // i.e. (x, y) => x+y
(x, y) => _min _   // i.e. (x, y) => x min y
(x, y) => _max _   // i.e. (x, y) => x max y
// Anonymous functions with parameters
var add = (x: Int, y: Int) => x + y
// Anonymous functions without parameters
var word = () => {"Hello world."}
```

Currying

Currying is a special form of higher-order function. It can transform a function that takes multiple parameters into a function that consists of (nested) anonymous functions with each taking one parameter.

For example, we can rewrite the sum function which takes three parameters (a, b, f) to a function that returns a function

def sum(f: Int => Int): (Int, Int) => Int = {
  def sumF(a: Int, b: Int): Int =
    if(a > b) 0
    else f(a) + sumF(a+1, b)
  sumF
}
def sumInts = sum(x => x);
def sumCubes = sum(x => x * x * x) 
println( sumCubes(1, 3) )

Here the sum function takes one argument f and returns a function sumF of type (Int, Int) => Int. This allows us to get rid of those parameters a and b in sumInts and sumCubes. We can also avoid defining sumInts and sumCubes by applying sum to a function directly, for example, sum(cube)(1, 3) is equivalent to sumCubes(1, 3).

In Scala, functions that return functions are so useful that there is a special syntax for them. For example, the sum function with the nested sumF function can be simplified as

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

The function type of sum is (Int => Int) => (Int, Int) => Int or (Int => Int) => ( (Int, Int) => Int )

scala big-data

Tingting Yu

Developer, Data Scientist

My research interests include time-series analysis, longitudinal analysis, image analysis …