In mathematics, functions have no side effects. Consider the classic function sin(x):

y = sin(x)

No matter how much work sin(x) does, all the results are returned and assigned to y. No global state of any kind is modified internally by sin(x). Hence, we say that such a function is free of side effects, or pure.

This property simplifies enormously the challenge of analyzing, testing, and debugging a function. You can do these things without having to know anything about the context in which the function is invoked, except for any other functions it might call. However, you can analyze them in the same way, working bottom up to verify the whole “stack.”

This obliviousness to the surrounding context is known as Referential Transparency. You can call such a function anywhere and be confident that it will always behave the same way. If no global state is modified, concurrent invocation of the function is straightforward and reliable.

In functional programming, you can compose functions from other functions. For example, tan(x) = sin(x)/cos(x). An implication of composability is that functions can be treated as values. In other words, functions are first-class, just like data. You can assign functions to variables. You can pass functions to other functions. You can return functions as values from functions. In the functional paradigm, functions become a primitive type, a building block that’s just as essential to the work of programming as integers or strings.

When a function takes other functions as arguments or returns a function, it is called a higher-order function. In mathematics, two examples of higher-order functions from calculus are derivation and integration.

The word “variable” takes on a new meaning in functional programming. If you come from a procedural or object-oriented programming background, you are accustomed to variables that are mutable. In functional programming, variables are immutable.

This is another consequence of the mathematical orientation. In the expression y = sin(x), once you pick x, then y is fixed. As another example, if you increment the integer 3 by 1, you don’t “modify the 3 object,” you create a new value to represent 4.

To be more precise, it is the values that are immutable. Functional programming languages prevent you from assigning a new value to a variable that already has a value.

Immutability is difficult when you’re not used to it. If you can’t change a variable, then you can’t have loop counters, for example. We’re accustomed to objects that change their state when we call methods on them. Learning to think in immutable terms takes some effort.

However, immutability has enormous benefits for concurrency. Almost all the difficulty of multithreaded programming lies in synchronizing access to shared, mutable state. If you remove mutability, then the problems essentially go away. It is the combination of referentially transparent functions and immutable values that make functional programming compelling as a better way to write concurrent software.

These qualities benefit programs in other ways. Almost all the constructs we have invented in 60-odd years of computer programming have been attempts to manage complexity. Higher-order functions and referential transparency provide very flexible building blocks for composing programs.

Immutability greatly reduces regression bugs, many of which are caused by unintended state changes in one part of a program due to intended changes in another part. There are other contributors to such non-local effects, but mutability is one of the most important.

It’s common in object-oriented designs to encapsulate access to data structures in objects. If these structures are mutable, we can’t simply share them with clients. We have to add special accessor methods to control access, so clients can’t modify them outside our control. These additions increase code size, which increases the testing and maintenance burden, and they increase the effort required by clients to understand the ad hoc features of our APIs.

In contrast, when we have immutable data structures, many of these problems simply go away. We can provide access to collections without fear of data loss or corruption. Of course, the general principles of minimal coupling still apply; should clients care if a Set or List is used, as long foreach is available?

Immutable data also implies that lots of copies will be made, which can be expensive. Functional data structures optimize for this problem (see [Okasaki1998]) and many of the built-in Scala types are efficient at creating new copies from existing copies.

It’s time to dive into the practicalities of functional programming in Scala. We’ll discuss other aspects and benefits of the approach as we proceed.

Let’s expand our previous map example a bit:

// code-examples/FP/basics/list-map-closure-example-script.scala

var factor = 3
val multiplier = (i:Int) => i * factor

val l1 = List(1, 2, 3, 4, 5) map multiplier

factor = 5
val l2 = List(1, 2, 3, 4, 5) map multiplier

println(l1)
println(l2)

We defined a variable, factor, to use as the multiplication factor, and we pulled out the previous anonymous function into a value called multiplier that now uses factor. Then we map over a list of integers, as we did before. After the first call to map, we change factor and map again. Here is the output:

List(3, 6, 9, 12, 15)
List(5, 10, 15, 20, 25)

Even though multiplier was an immutable function value, its behavior changed when factor changed.

There are two free variables in multiplier: i and factor. One of them, i, is a formal parameter to the function. Hence, it is bound to a new value each time multiplier is called.

However, factor is not a formal parameter, but a reference to a variable in the enclosing scope. Hence, the compiler creates a closure that encompasses (or “closes over”) multiplier and the external context of the unbound variables multiplier references, thereby binding those variables as well.

This is why the behavior of multiplier changed after changing factor. It references factor and reads its current value each time. If a function has no external references, then it is trivially closed over itself. No external context is required.

If we called sin(x) thousands of times with the same value of x, it would be wasteful if it calculated the same value every single time. Even in “pure” functional libraries, it is common to perform internal optimizations like caching previously computed values (sometimes called memoization). Caching introduces side effects, as the state of the cache is modified.

However, this lack of purity should be opaque to the user (except perhaps in terms of the performance impact). If you are designing functional libraries, ensure that they preserve the purity of their abstractions, including the behavior of referential transparency and its implications for concurrency.

You can see examples of functional libraries with mutable internals in the Scala library. The methods in List often use mutable local variables for efficient traversal. The local variables are thread-safe, as are the traversals, since Lists themselves are immutable.

A trampoline is a loop that works through a list of functions, calling each one in turn. The metaphor of bouncing the functions off a trampoline is the source of the name.

Consider a kind of recursion where a function A doesn’t call itself recursively, but instead it calls another function B, which calls A, which calls B, etc. This kind of back-and-forth recursion can also be converted into a loop using a trampoline. Note that trampolines impose a performance overhead, but they are ideal for pure functional recursions (versus an imperative equivalent) that would otherwise exhaust the stack.

Support for this optimization is planned for Scala version 2.8, although it has not yet been implemented at the time of this writing.

Lists are the most common data structure in functional programming. They are the core of the first functional programming language, Lisp.

In the interest of immutability, a new list is created when you add an element to a list. It is conventional to prepend the new element to the list, as we’ve seen before:

// code-examples/FP/datastructs/list-script.scala

val list1 = List("Programming", "Scala")
val list2 = "People" :: "should" :: "read" :: list1
println(list2)

Because the :: operator binds to the right, the definition of list2 is equivalent to both of the following variations:

val list2 = ("People" :: ("should" :: ("read" :: list1)))
val list2 = list1.::("read").::("should").::("People")

In terms of performance, prepending is O(1). We’ll see why when we dive into Scala’s implementation of List in A Closer Look at Lists, after we have learned more about parameterized types in Scala.

Unlike some of the other collections, Scala only defines an immutable List. However, it also defines some mutable list types, such as ListBuffer and LinkedList

Perhaps the second most common data structure is the map, referred to as a hash or dictionary in other languages, and not to be confused with the map function we saw earlier. Maps are used to hold pairs of keys and values.

In the interest of minimalism, maps could be implemented with lists. Every even element in the list (counting from zero) could be a key, followed by the value in the next odd position. In practice, maps are usually implemented in other ways for efficiency.

Scala supports the special initialization syntax we saw previously:

val stateCapitals = Map(
  "Alabama" -> "Montgomery",
  "Alaska"  -> "Juneau",
  // ...
  "Wyoming" -> "Cheyenne")

The scala.collection.Map[A,+B] trait only defines methods for reading the Map. There are derived traits for immutable and mutable maps, scala.collection.immutable.Map[A,+B] and scala.collection.mutable.Map[A,B], respectively. They define + and - operators for adding and removing elements, and ++ and -- operators for adding and removing elements defined in Iterators of Pairs, where each Pair is a key-value pair.

Sets are like lists, but they require each element to be unique. Sets could also be implemented using lists, as long as the equivalent of the list “cons” operator (::) first checks that the element doesn’t already exist in the storage list. This property means that element insertion would be O(N) if a storage list were used, and the order of the elements in the set wouldn’t necessarily match the order of “insertion” operations. In practice, sets are usually implemented with more efficient data structures.

Just as for Map, the scala.collection.Set[A] trait only defines methods for reading the Set. There are derived traits for immutable and mutable sets, scala.collection.immutable.Set[A] and scala.collection.mutable.Set[A], respectively. They define + and - operators for adding and removing elements, and ++ and -- operators for adding and removing elements defined in Iterators (which could be other sets, lists, etc.).

Other familiar data structures, like Tuples and Arrays, will appear in functional languages. Typically, they’re used to provide some convenient feature not supported by a more common functional type. In most cases they could be replaced with lists.

The standard traversal method for Scala containers is foreach, which is defined by the Iterable traits that the containers mix in. It is O(N) in the number of elements. Here is an example of its use for lists and maps:

// code-examples/FP/datastructs/foreach-script.scala

List(1, 2, 3, 4, 5) foreach { i => println("Int: " + i) }

val stateCapitals = Map(
  "Alabama" -> "Montgomery",
  "Alaska"  -> "Juneau",
  "Wyoming" -> "Cheyenne")

stateCapitals foreach { kv => println(kv._1 + ": " + kv._2) }

The signature of foreach is the following:

trait Iterable[+A] {
  ...
  def foreach(f : (A) => Unit) : Unit = ...
  ...
}

foreach is a higher-order function that takes a function argument: the operation to perform on each element. Note that for a map, A is actually a tuple, as shown in the example. Also, foreach returns Unit. foreach is not intended to create new collections; we’ll see examples of operations that create collections shortly.

Once you have foreach, you can implement all the other traversal operations we’ll discuss next, and more. A look at Iterable will show that it supports methods for filtering collections, finding elements that match specified criteria, calculating the number of elements, and so forth.

The methods we’ll discuss next are hallmarks of functional programming: mapping, filtering, folding, and reducing.

We’ve encountered the map method before. It returns a new collection of the same size as the original collection. It is also a member of Iterable, and its signature is:

trait Iterable[+A] {
  ...
  def map[B](f : (A) => B) : Iterable[B] = ...
  ...
}

The passed-in function (f) can transform an original element of type A to a new type B. Here is an example:

// code-examples/FP/datastructs/map-script.scala

val stateCapitals = Map(
  "Alabama" -> "Montgomery",
  "Alaska"  -> "Juneau",
  "Wyoming" -> "Cheyenne")

val lengths = stateCapitals map { kv => (kv._1, kv._2.length) }
println(lengths)

This script produces the output ArrayBuffer((Alabama,10), (Alaska,6), (Wyoming,8)). That is, we convert the Pair[String,String] elements to an ArrayBuffer of Pair[String,Int] elements. Where did the ArrayBuffer come from? It turns out that Iterable.map creates and returns an ArrayBuffer as the new Iterable collection.

This brings up a general conflict between immutable types and object-oriented type hierarchies. If a base type creates a new instance on modification, how does it know what kind of type to create?

You could solve this problem two ways. First, you could have each type in the hierarchy override methods like map to return an instance of their own type. This approach is error-prone, though, as it would be easy to forget to override all such methods when a new type is added.

Even if you always remember to override each method, you have the dilemma of how to implement the override. Do you call the super method to reuse the algorithm, then iterate through the returned instance to create a new instance of the correct type? That would be inefficient. You could copy and paste the algorithm into each override, but that creates issues of code bloat, maintainability, and skew.

There’s an alternative approach: don’t even try. How is the new instance that is returned actually used? Do we really care if it has the “wrong” type? Keep in mind that all we usually care about are the low-level abstractions like lists, maps, and sets. In the case of functional data structures, the derived types we might implement using object-oriented inheritance are most often implementation optimizations. The Scala type hierarchy for containers does have a few levels of abstractions at the bottom, e.g., Collection extends Iterable extends AnyRef, but above Collection are Seq (parent of List), Map, Set, etc.

That said, if you really need a Map, you can create one easily enough:

// code-examples/FP/datastructs/map2-script.scala

val stateCapitals = Map(
  "Alabama" -> "Montgomery",
  "Alaska"  -> "Juneau",
  "Wyoming" -> "Cheyenne")

val map2 = stateCapitals map { kv => (kv._1, kv._2.length) }

// val lengths = Map(map2)  // ERROR: won't work
val lengths = Map[String,Int]() ++ map2

println(lengths)

The commented-out line suggests that it would be nice if you could simply pass the new Iterable to Map.apply, but this doesn’t work. Here is the signature of Map.apply:

object Map {
  ...
  def apply[A, B](elems : (A, B)*) : Map[A, B] = ...
  ...
}

It expects a variable argument list, not an Iterable. However, we can create an empty map of the right type and then add the new Iterable to it, using the ++ method, which returns a new Map.

So, we can get the Map we want when we must have one. While it would be nice if methods like map returned the same collection type, we saw that there is no easy way to do this. Instead, we accept that map and similar methods return an abstraction like Iterable and then rely on the specific subtypes to take Iterables as input arguments for populating the collection.

A related Map operation is flatMap, which can be used to “flatten” a hierarchical data structure, remove “empty” elements, etc. Hence, unlike map, it may not return a new collection of the same size as the original collection:

// code-examples/FP/datastructs/flatmap-script.scala

val graph = List(
  "a", List("b1", "b2", "b3"), List("c1", List("c21", Nil, "c22"), Nil, "e")
)

def flatten(list: List[_]): List[_] = list flatMap {
  case head :: tail => head :: flatten(tail)
  case Nil => Nil
  case x => List(x)
}

println(flatten(graph))

This script reduces the hierarchical graph to List(a, b1, b2, b3, c1, c21, c22, e). Notice that the Nil elements have been removed. We used List[_] because we won’t know what the type parameters are for any embedded lists when we’re traversing the outer list, due to type erasure.

Here is the signature for flatMap, along with map, for comparison:

trait Iterable[+A] {
  ...
  def map[B]    (f : (A) => B) : Iterable[B] = ...
  def flatMap[B](f : (A) => Iterable[B]) : Iterable[B]
  ...
}

Each pass must return an Iterable[B], not a B. After going through the collection, flatMap will “flatten” all those Iterables into one collection. Note that flatMap won’t flatten elements beyond one level. If our function literal leaves nested lists intact, they won’t be flattened for us.

It is common to traverse a collection and extract a new collection from it with elements that match certain criteria:

// code-examples/FP/datastructs/filter-script.scala

val stateCapitals = Map(
  "Alabama" -> "Montgomery",
  "Alaska"  -> "Juneau",
  "Wyoming" -> "Cheyenne")

val map2 = stateCapitals filter { kv => kv._1 startsWith "A" }

println( map2 )

There are several different kinds of methods defined in Iterable for filtering or otherwise returning part of the original collection (comments adapted from the Scaladocs):

trait Iterable[+A] {
  ...
  // Returns this iterable without its n first elements. If this iterable
  // has less than n elements, the empty iterable is returned.
  def drop (n : Int) : Collection[A] = ...

  // Returns the longest suffix of this iterable whose first element does
  // not satisfy the predicate p.
  def dropWhile (p : (A) => Boolean) : Collection[A] = ...

  // Apply a predicate p to all elements of this iterable object and
  // return true, iff there is at least one element for which p yields true.
  def exists (p : (A) => Boolean) : Boolean = ...

  // Returns all the elements of this iterable that satisfy the predicate p.
  // The order of the elements is preserved.
  def filter (p : (A) => Boolean) : Iterable[A] = ...

  // Find and return the first element of the iterable object satisfying a
  // predicate, if any.
  def find (p : (A) => Boolean) : Option[A] = ...

  // Returns index of the first element satisying a predicate, or -1.
  def findIndexOf (p : (A) => Boolean) : Int = ...

  // Apply a predicate p to all elements of this iterable object and return
  // true, iff the predicate yields true for all elements.
  def forall (p : (A) => Boolean) : Boolean = ...

  // Returns the index of the first occurence of the specified object in
  // this iterable object.
  def indexOf [B >: A](elem : B) : Int = ...

  // Partitions this iterable in two iterables according to a predicate.
  def partition (p : (A) => Boolean) : (Iterable[A], Iterable[A]) = ...

  // Checks if the other iterable object contains the same elements.
  def sameElements [B >: A](that : Iterable[B]) : Boolean = ...

  // Returns an iterable consisting only over the first n elements of this
  // iterable, or else the whole iterable, if it has less than n elements.
  def take (n : Int) : Collection[A] = ...

  // Returns the longest prefix of this iterable whose elements satisfy the
  // predicate p.
  def takeWhile (p : (A) => Boolean) : Iterable[A] = ...
}

Types like Map and Set have additional methods.

We’ll discuss folding and reducing in the same section, as they’re similar. Both are operations for “shrinking” a collection down to a smaller collection or a single value.

Folding starts with an initial “seed” value and processes each element in the context of that value. In contrast, reducing doesn’t start with a user-supplied initial value. Rather, it uses the first element as the initial value:

// code-examples/FP/datastructs/foldreduce-script.scala

List(1,2,3,4,5,6) reduceLeft(_ + _)

List(1,2,3,4,5,6).foldLeft(10)(_ * _)

This script reduces the list of integers by adding them together, returning 21. It then folds the same list using multiplication with a seed of 10, returning 7,200.

Reducing can’t work on an empty collection, since there would be nothing to return. In this case, an exception is thrown. Folding on an empty collection will simply return the seed value.

Folding also offers more options for the final result. Here is a “fold” operation that is really a map operation:

// code-examples/FP/datastructs/foldleft-map-script.scala

List(1, 2, 3, 4, 5, 6).foldLeft(List[String]()) {
  (list, x) => ("<" + x + ">") :: list
}.reverse

It returns List(<1>, <2>, <3>, <4>, <5>, <6>). Note that we had to call reverse on the result to get back a list in the same order as the input list.

Here are the signatures for the various fold and reduce operations in Iterable:

trait Iterable[+A] {
  ...
  // Combines the elements of this iterable object together using the
  // binary function op, from left to right, and starting with the value z.
  def foldLeft [B](z : B)(op : (B, A) => B) : B

  // Combines the elements of this list together using the binary function
  // op, from right to left, and starting with the value z.
  def foldRight [B](z : B)(op : (A, B) => B) : B

  // Similar to foldLeft but can be used as an operator with the order of
  // list and zero arguments reversed. That is, z /: xs is the same as
  // xs foldLeft z
  def /: [B](z : B)(op : (B, A) => B) : B

  // An alias for foldRight. That is, xs : z is the same as xs foldRight z
  def : [B](z : B)(op : (A, B) => B) : B

  // Combines the elements of this iterable object together using the
  // binary operator op, from left to right
  def reduceLeft [B >: A](op : (B, A) => B) : B

  // Combines the elements of this iterable object together using the
  // binary operator op, from right to left
  def reduceRight [B >: A](op : (A, B) => B) : B

Many people consider the operator forms, : for foldRight and /: for foldLeft, to be a little too obscure and hard to remember. Don’t forget the importance of communicating with your readers when writing code.

Why are there left and right forms of fold and reduce? For the first examples we showed, adding and multiplying a list of integers, they would return the same result. Consider a foldRight version of our last example that used fold to map the integers to strings:

// code-examples/FP/datastructs/foldright-map-script.scala

List(1, 2, 3, 4, 5, 6).foldRight(List[String]()) {
  (x, list) => ("<" + x + ">") :: list
}

This script produces List(<1>, <2>, <3>, <4>, <5>, <6>), without having to call reverse, as we did before. Note also that the arguments to the function literal are reversed compared to the arguments for foldLeft, as required by the definition of foldRight.

Both foldLeft and reduceLeft process the elements from left to right. Here is the foldLeft sequence for List(1,2,3,4,5,6).foldLeft(10)(_ * _):

((((((10 * 1) * 2) * 3) * 4) * 5) * 6)
((((((10) * 2) * 3) * 4) * 5) * 6)
(((((20) * 3) * 4) * 5) * 6)
((((60) * 4) * 5) * 6)
(((240) * 5) * 6)
((1200) * 6)
(7200)

Here is the foldRight sequence:

(1 * (2 * (3 * (4 * (5 * (6 * 10))))))
(1 * (2 * (3 * (4 * (5 * (60))))))
(1 * (2 * (3 * (4 * (300)))))
(1 * (2 * (3 * (1200))))
(1 * (2 * (3600)))
(1 * (7200))
(7200)

It turns out that foldLeft and reduceLeft have one very important advantage over their “right-handed” brethren: they are tail-call recursive, and as such they can benefit from tail-call optimization.

If you stare at the previous breakdowns for multiplying the integers, you can probably see why they are tail-call recursive. Recall that a tail call must be the last operation in an iteration. For each line in the foldRight sequence, the outermost multiplication can’t be done until the innermost multiplications all complete, so the operation isn’t tail recursive.

In the following script, the first line prints 1784293664, while the second line causes a stack overflow:

// code-examples/FP/datastructs/reduceleftright-script.scala

println((1 to 1000000) reduceLeft(_ + _))
println((1 to 1000000) reduceRight(_ + _))

So why have both kinds of recursion? If you’re not worried about overflow, a right recursion might be the most natural fit for the operation you are doing. Recall that when we used foldLeft to map integers to strings, we had to reverse the result. That was easy enough to do in that case, but in general, the result of a left recursion might not always be easy to convert to the right form.

You’ll find the functional operations we’ve explored throughout the Scala library, and not exclusively on collection classes. The always handy Option container supports filter, map, flatMap, and other functionally oriented methods that are applied only if the Option isn’t empty (that is, if it’s a Some and not a None).

Let’s see this in practice:

// code-examples/FP/datastructs/option-script.scala

val someNumber = Some(5)
val noneNumber = None

for (option <- List(noneNumber, someNumber)) {
  option.map(n => println(n * 5))
}

In this example, we attempt to multiply the contents of two Options by five. Normally, trying to multiply a null value would result in an error. But because the implementation of map on Option only applies the passed-in function when it’s non-empty, we don’t have to worry about testing for the presence of a value or handling an exception when we map over the None.

Functional operations on Options save us from extra conditional expressions or pattern matching. Pattern matching, though, is a powerful tool within the context of functional programming, as we’ll explore in the next section.

Consider the following code fragment:

val name: String = "scala"
println(name.capitalize.reverse)

It prints the following:

alacS

We saw in The Predef Object that Predef defines the String type to be java.lang.String, yet the methods capitalize and reverse aren’t defined on java.lang.String. How did this code work?

The Scala library defines a “wrapper” class called scala.runtime.RichString that has these methods, and the compiler converted the name string to it implicitly using a special method defined in Predef called stringWrapper:

implicit def stringWrapper(x: String) = new runtime.RichString(x)

The implicit keyword tells the compiler it can use this method for an “implicit” conversion from a String to a RichString, whenever the latter is required. The compiler detected an attempt to call a capitalize method, and it determined that RichString has such a method. Then it looked within the current scope for an implicit method that converts String to RichString, finding stringWrapper.

As we’ll see in Views and View Bounds, these conversion methods are sometimes called views, in the sense that our stringWrapper conversion provides a view from String to RichString.

Predef defines many other implicit conversion methods, most of which follow the naming convention old2New, where old is the type of object available and New is the desired type. However, there is no restriction on the names of conversion methods. There are also a number of other Rich wrapper classes defined in the scala.runtime package.

Here is a summary of the lookup rules used by the compiler to find and apply conversion methods. For more details, see [ScalaSpec2009]:

What if you can’t define a conversion method in a companion object, to satisfy the third rule, perhaps because you can’t modify or create the companion object? In this case, define the method somewhere else and import it. Normally, you will define an object with just the conversion method(s) needed. Here is an example:

// code-examples/FP/implicits/implicit-conversion-script.scala
import scala.runtime.RichString

class FancyString(val str: String)

object FancyString2RichString {
    implicit def fancyString2RichString(fs: FancyString) =
        new RichString(fs.str)
}

import FancyString2RichString._

val fs = new FancyString("scala")
println(fs.capitalize.reverse)

We can’t modify RichString or Predef to add an implicit conversion method for our custom FancyString class. Instead, we define an object named FancyString2RichString and define the conversion method in it. We then import the contents of this object and the converter gets invoked implicitly in the last line. The output of this script is the following:

alacS

This pattern for effectively adding new methods to classes has been called Pimp My Library (see [Odersky2006]).

Implicits can be perilously close to “magic.” When used excessively, they obfuscate the code’s behavior for the reader. Also, be careful about the implementation of a conversion method, especially if the return type is not explicitly declared. If a future change to the method also changes the return type in some subtle way, the conversion may suddenly fail to work. In general, implicits can cause mysterious behavior that is hard to debug!

When deciding how to implement “default” values for method arguments, a major advantage of using default argument values (in Scala version 2.8) is that the method maintainer decides what to use as the default value. The implementation is more straightforward and you avoid the “magic” of implicit methods. However, a disadvantage of using default argument values is that it might be desirable to use a different “default” value based on the context in which the method is being called. Scala version 2.8 provides some flexibility, as you can use an expression for an argument, not just a constant value. However, that flexibility might not be enough, in which case implicits are a very flexible and powerful alternative.