Basic Functional Programming in Scala

A Functional Manifesto

Here are a few tenants of the functional programming paradigm:

·       Functions are like any other kind of data. In particular, functions can be inputs and outputs of other functions. In fact, we don't really need other kinds of data. Numbers, strings, arrays, objects, etc., can all be considered special kinds of functions.

·       Variables are evil. In multi-threaded programs they can cause race conditions and deadlocks.

·       Mutable data structures are evil. This is just a corollary of the above. For example, to remove an element, x, from a list, L, create a new list just like L but without x.

·       Objects are evil, if they are mutable.

·       Procedures are evil. Because their purpose is to update evil variables.

·       Loops are evil. This is because they often require an explicit or implicit evil loop control variable.

·       Recursion is good.

·       Higher order functions (i.e., functions that process other functions such as combinators) are good.

·       Control structures should be implemented as higher order functions.

·       Lazy evaluation is good. Expressions should only be evaluated if and when they are needed.

·       Static scoping is good. Non-locals in a function get their values from the functions defining environment, not its calling environment. A function that remembers its defining environment is called a closure.

Scala does have variables, loops, procedures, and all that other evil stuff, so programmers who want to write functional programs should simply avoid these temptations.

Functions as Data

Here's a simple function:

scala> def foo(x: Int, y: Int) = 3 * x + 4 * y
foo: (x: Int, y: Int)Int

We can call it:

scala> foo(6, 7)
res1: Int = 46

Or we can reference it without calling it by placing an _ after its name:

scala> foo _
res2: (Int, Int) => Int = <function2>

This means we can assign foo (not its output) to a constant or variable:

scala> val bar = foo _
bar: (Int, Int) => Int = <function2>

Now the new constant can be called:

scala> bar(3, 4)
res6: Int = 25

Combinators (aka Higher-order functions, Meta-functions)

A simple example of a combinator is the compose function, which takes two functions, f and g, as input and returns the result of composing f with g:

def compose(f: Int=>Int, g: Int=>Int): Int=>Int = {
   def r(x: Int): Int = f(g(x))
   r _

Scala infers the type of compose:

compose: (f: Int => Int, g: Int => Int)Int => Int

To test compose, we fine two simple functions:

scala> def triple(x: Int): Int = 3 * x
triple: (x: Int)Int

scala> def square(x: Int) = x * x
square: (x: Int)Int

A third function is defined by compose:

scala> val squareTriple = compose(square ­_, triple _)
squareTriple: Int => Int

Here's a sample call:

scala> squareTriple(2)
res18: Int = 36

Lambda Notation

A lambda is an anonymous function. It has the form:

(parameters)=> expression

For example:

((x: Int) => x * x)(4)
   //> res2: Int = 16
((x: String, y: Int) => x + y)("arg", 5)
   //> res3: String = arg5

compose((x: Int) => x * x, (x: Int) => 3 * x))

Here's a shorter definition of compose:

def compose(f: Int => Int, g: Int => Int) = (x: Int) => f(g(x))


Meta-programming is the practice of writing meta-programs.

A meta-program is a program that processes or generates programs.

Examples include compilers, interpreters, parsers, type checkers, debuggers, and operating systems.

A meta-function, like compose, can be viewed as a type of meta-program.

The ultimate meta-program generates a program from a specification.

The ultimate meta-program is a programmer!

Static Scoping and closures

A programmers (and meta-programs) have no control over the executing environment of their programs, but they do have control over the defining environments.

For example, assume isSmall is defined in an environment where delta is tiny:

val delta = 1e-10 // a global constant

def isSmall(x: Double) = {
   math.abs(x) <= delta

However, it may be called in an environment where delta is big:

def testIsSmall = {
   val delta = 100
   isSmall(delta/2) // 50 <= delta?

What should the correct output be: true or false?

The static scope rule says the defining environment should be searched for non-locals.

The dynamic scope rule says the calling environment should be searched for non-locals.

For example, delta is used by isSmall, but not declared in isSmall. Therefore delta is non-local for isSmall.

In the defining environment delta is 1e-10, but in the calling environment delta is 100.

The dynamic scope rule is a bad idea. Programmers have no control over how their functions will be called.

Scala uses the static scope rule. But how?

A closure is a function together with a reference to its defining environment:

closure = (parameters, body, def-env)

All Scala functions are, in fact, closures. When the body of a Scala function is executed, the defining environment is consulted each time a non-local is encountered.

Lazy Evaluation and Thunks

Scala allows programmers to postpone the evaluation of an expression until it's needed, which may be never. For example:

scala> def noisySquare(x: Int) = { println("squaring " + x); square(x)};
noisySquare: (x: Int)Int

scala> lazy val hundred = noisySquare(10)
hundred: Int = <lazy>

Notice that the type of hundred is a lazy Int. This means that hundred is actually a parameterless function that will return 100 if and when it's called.

We can see the call to noisySquare when we first use hundred:

scala> 3 + hundred
squaring 10
res0: Int = 103

This could be inefficient if noisySquare must be called every time hundred is referenced. Fortunately, thunks in Scala are memoized. This means the value of noisySquare is cached the first time it is called. The value of the cache is returned on subsequent calls:

scala> 5 + hundred
res1: Int = 105 // no "squaring 10" message this time

Generic Functions

Functions can also have type parameters:

def id[T](x: T) = x

id("hello")      > res0: String = hello
id(10)           > res1: Int = 10
id(id _)         > res2: Nothing => Nothing = <function1>

def reverse[T, S](x: (T, S)): (S, T) = (x._2, x._1)
reverse(2, "rat") > ("rat", 2)