Every decade or two, a major computing idea goes mainstream. These ideas may have lurked in the background of academic computer science research, or possibly in some lesser-known field of industry. The transition to mainstream acceptance comes in response to a perceived problem for which the idea is well suited. Object-oriented programming, which was invented in the 1960s, went mainstream in the 1980s, arguably in response to the emergence of graphical user interfaces, for which the OOP paradigm is a natural fit.
Functional programming appears to be experiencing a similar breakout. Long the topic of computer science research and even older than object-oriented programming, functional programming offers effective techniques for concurrent programming, which is growing in importance.
Because functional programming is less widely understood than object-oriented programming, we won’t assume that you have prior experience with it. We’ll start this chapter with plenty of background information. As you’ll see, functional programming is not only a very effective way to approach concurrent programming, which we’ll explore in depth in Chapter 9, but functional programming can also improve your objects.
Of course, we can’t provide an exhaustive introduction to functional programming. To learn more about it, [O’Sullivan2009] has a more detailed introduction in the context of the Haskell language. [Abelson1996], [VanRoy2004], and [Turbak2008] offer thorough introductions to general programming approaches, including functional programming. Finally, [Okasaki1998] and [Rabhi1999] discuss functional data structures and algorithms in detail.
Don’t all programming languages have
functions of some sort? Whether they are called methods, procedures, or
GOTOs
, programmers are always dealing in functions.
Functional programming is based on
the behavior of functions in the mathematical sense, with all the
implications that starting point implies.
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.
As a hybrid object-functional language, Scala does not require functions to be pure, nor does it require variables to be immutable. It does, however, encourage you to write your code this way whenever possible. You have the freedom to use procedural or object-oriented techniques when and where they seem most appropriate.
Though functional languages are all about eliminating side effects, a language that never allowed for side effects would be useless. Input and output (IO) are inherently about side effects, and IO is essential to all programming tasks. For this reason, all functional languages provide mechanisms for performing side effects in a controlled way.
Scala doesn’t restrict what you can do, but we encourage you to use immutable values and pure functions and methods whenever possible. When mutability and side effects are necessary, pursue them in a “principled” way, isolated in well-defined modules and focused on individual tasks.
If you’re new to functional programming, keep in mind that it’s easy to fall back to old habits. We encourage you to master the functional side of Scala and to learn to use it effectively.
A function that returns Unit
implies that the
function has pure side effects, meaning that if it does any useful work,
that work must be all side effects, since the function doesn’t return
anything.
We’ve seen many examples of
higher-order functions and composability in Scala. For example,
List.map
takes a function to transform each element of
the list to something else:
// code-examples/FP/basics/list-map-example-script.scala
List
(1
,2
,3
,4
,5
) map {_
*2
}
Recall that _ *
2
is a function literal that is shorthand
for i => i * 2
. For each argument to the function,
you can use _
if the argument is used only once. We
also used the infix operator notation to invoke map
.
Here’s an example that “reduces” the same list by multiplying all the
elements together:
// code-examples/FP/basics/list-reduceLeft-example-script.scala
List
(1
,2
,3
,4
,5
) reduceLeft {_
*_
}
The first _
represents the argument that is accumulating the value of the reduction,
and the second _
represents the current element of the
list.
Both examples successfully “looped” through the list without the use of a mutable counter to track iterations. Most containers in the Scala library provide functionally pure iteration methods. In other cases, recursion is the preferred way to traverse a data structure or perform an algorithm. We’ll return to this topic in Recursion.
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 * factorval
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.
Recursion plays a larger role in pure functional programming than in imperative programming, in part because of the restriction that variables are immutable. For example, you can’t have loop counters, which would change on each pass through a loop. One way to implement looping in a purely functional way is with recursion.
Calculating factorials provides a good example. Here is an imperative loop implementation:
// code-examples/FP/recursion/factorial-loop-script.scala
def
factorial_loop
(i:BigInt
):BigInt
= {var
result =BigInt
(1
)for
(j<-
2
to i.intValue) result *= j result }for
(i<-
1
to10
) format("%s: %s
"
, i, factorial_loop(i))
Both the loop counter
j
and the result
are mutable
variables. (For simplicity, we’re ignoring input numbers that are less
than or equal to zero.) The output of the script is the following:
1: 1 2: 2 3: 6 4: 24 5: 120 6: 720 7: 5040 8: 40320 9: 362880 10: 3628800
Here’s a first pass at a recursive implementation:
// code-examples/FP/recursion/factorial-recur1-script.scala
def
factorial
(i:BigInt
):BigInt
= imatch
{case
_
if
i ==1
=>
icase
_
=>
i * factorial(i -1
) }for
(i<-
1
to10
) format("%s: %s
"
, i, factorial(i))
The output is the same, but
now there are no mutable variables. Recursion not only helps us avoid
mutable variables, it is also the most natural way to express some functions, particularly mathematical
functions. The recursive definition in our second factorial
is structurally similar to a
definition for factorials that you might see in a mathematics book.
However, there are two potential problems with recursion: the performance overhead of repeated function invocations and the risk of stack overflow.
Performance problems in a recursive scenario can sometimes be addressed with memoization, but care should be taken that the space requirements of caching don’t outweigh the performance benefits.
Stack overflow can be avoided by converting the recursive invocation into a loop of some kind. In fact, the Scala compiler can do this conversion for you for some kinds of recursive invocations, which we describe next.
A particular kind of
recursion is called tail-call recursion, which occurs
when a function calls itself as its final operation. Tail-call recursion
is very important because it is the easiest kind of recursion to optimize
by conversion into a loop. Loops eliminate the potential of a stack
overflow, and they improve performance by eliminating the recursive
function call overhead. While tail recursion optimizations are not yet
supported natively on the JVM, scalac
can do
them.
However, our factorial
example is not a tail recursion, because factorial
calls itself and then does a multiplication with the
results. There is a way to implement factorial
in a
tail recursive way. We actually saw an implementation in Nesting Method Definitions. However, that example didn’t use
some constructs we’ve learned about since, such as for
comprehensions and pattern matching. So, here’s a new implementation of
factorial
, calculated with tail-call recursion:
// code-examples/FP/recursion/factorial-recur2-script.scala
def
factorial
(i:BigInt
):BigInt
= {def
fact
(i:BigInt
, accumulator:BigInt
):BigInt
= imatch
{case
_
if
i ==1
=>
accumulatorcase
_
=>
fact(i -1
, i * accumulator) } fact(i,1
) }for
(i<-
1
to10
) format("%s: %s
"
, i, factorial(i))
This script produces the same output as
before. Now, factorial
does all the work with a nested
method, fact
, that is tail recursive because it passes
an accumulator
argument to hold the computation in
progress. This argument is computed with a multiplication
before the recursive call to fact
,
which is now the very last thing that is done. In our previous
implementation, this multiplication was done after
the call to fact
. When we call
fact(1)
, we simply return the accumulated value.
If you call our original
non-tail recursive implementation of factorial
with a
large number—say 10,000—you’ll cause a stack overflow on a typical desktop
computer. The tail-recursive implementation works successfully, returning
a very large number.
This idiom of nesting a
tail-recursive function that uses an accumulator is a very useful
technique for converting many recursive algorithms into tail recursions
that can be optimized into loops by scalac
.
The tail-call optimization won’t be applied when a method that
calls itself might be overridden in a derived type. The method must be
private or final, defined in an object
, or nested in
another method (like fact
earlier). The new
@tailrec
annotation in version 2.8 will trigger an
error if the compiler can’t optimize the annotated method. (See Annotations.)
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.
There are several data structures that are common in functional programming, most of which are containers, like collections. Languages like Erlang rely on very few types, while other functional languages provide a richer type system.
The common data structures support the same subset of higher-order functions for read-only traversal and access to the elements in the data structures. These features make them suitable as “protocols” for minimizing the coupling between components, while supporting data exchange.
In fact, these data
structures and their operations are so useful that many languages support
them, including those that are not considered functional languages, like
Java and Ruby. Java doesn’t support higher-order functions directly.
Instead, function values have to be wrapped in objects. Ruby uses
procs
and lambdas
as function
values.
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.
You might have noticed that the +
does not
appear in front of the B
type parameters for
scala.collection.mutable.Map
. You’ll see why in
Variance of Mutable Types.
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.).
The functional collections we
just discussed—lists, maps, sets, as well as tuples and arrays—all support
several common operations based on read-only traversal. In fact, this
uniformity can be exploited if any “container” type also supports these
operations. For example, an Option
contains zero or one
elements, if it is a None
or Some
,
respectively.
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] = ... }
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
to1000000
) reduceLeft(_
+_
)) println((1
to1000000
) 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
).
// 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.
We’ve seen many examples of pattern matching throughout this book. We got our first taste in A Taste of Concurrency, where we used pattern matching in our Actor that drew geometric shapes. We discussed pattern matching in depth in Pattern Matching.
Pattern matching is a fundamental tool in functional programming. It’s just as important as polymorphism is in object-oriented programming, although the goals of the two techniques are very different.
Pattern matching is an elegant way to decompose objects into their constituent parts for processing. On the face of it, pattern matching for this purpose seems to violate the goal of encapsulation that objects provide. Immutability, though, largely rectifies this conflict. The risk that the parts of an object might be changed outside of the control of the enclosing object is avoided.
For example, if we have a
Person
class that contains a list of addresses, we
don’t mind exposing that list to clients if the list is immutable. They
can’t unexpectedly change the list.
However, exposing
constituent parts potentially couples clients to the
types of those parts. We can’t change how the parts
are implemented without breaking the clients. A way to minimize this risk
is to expose the lowest-level abstractions possible. When clients access a
person’s addresses, do they really need to know that they are stored in a
List
, or is it sufficient to know that they are stored
in an Iterable
or Seq
? If so, then
we can change the implementation of the addresses as long as they still
support those abstractions. Of course, we’ve known for a long time in
object-oriented programming that you should only couple to abstractions,
not concrete details (for example, see [Martin2003]).
Functional pattern matching
and object-oriented polymorphism are powerful complements to each other. We saw this in
the Actor example in A Taste of Concurrency, where we
matched on the Shape
abstraction, but called the
polymorphic draw
operation.
You’ve seen partially applied functions, or partial functions, throughout this book. When you’ve seen an underscore passed to a method, you’ve probably seen partial application at work.
Partial functions are expressions in which not all of the arguments defined in a function are supplied as parameters to the function. In Scala, partial functions are used to bundle up a function, including its parameters and return type, and assign that function to a variable or pass it as an argument to another function.
This is a bit confusing until we see it in practice:
// code-examples/FP/partial/partial-script.scala
def
concatUpper
(s1:String
, s2:String
):String
= (s1 +" "
+ s2).toUpperCaseval
c = concatUpper_
println(c("short"
,"pants"
))val
c2 = concatUpper("short"
,_
:String
) println(c2("pants"
))
Calling
concatUpper
with an underscore (_
)
turns the method into a function value. In
the first part of the example, we’ve assigned a partially applied
version of concatUpper
to the
value c
. We then apply it,
implicitly calling the apply
method on
c
by passing parameters to it directly. The returned
value is then printed.
In the second part, we’ve
specified the first parameter to concatUpper
but not
the second, although we have specified the type of the second parameter.
We’ve assigned this variant to a second value, c2
. To
produce the same output as we saw before, we need only pass in a single
value when we apply c2
. We’ve applied part of the
function in the assignment to c2
, and we “fill in the
blanks” when we call c2
on the next line.
We’ve seen partially applied functions without the underscore syntax as well:
List
("short"
,"pants"
).map(println)
In this example,
println
is the partially applied function. It’s applied
when invoked by mapping over each element in the list. Because the map
operation expects a function as an argument, we don’t need to write
map(println _)
. The trailing underscore that turns
println
into a function value is implied, in this
context.
Another way of thinking of
partial functions is as functions that will inform you when you supply
them with parameters that are out of their domain. Every partial function
is, as you might guess, of the type PartialFunction
.
This trait defines a method orElse
that takes another
PartialFunction
. Should the first partial function not
apply, the second will be invoked.
Again, this is easier understood in practice:
// code-examples/FP/partial/orelse-script.scala
val
truthier:PartialFunction[Boolean, String]
= {case
true
=>
"truthful"
}val
fallback:PartialFunction[Boolean, String]
= {case
x=>
"sketchy"
}val
tester = truthier orElse fallback println(tester(1
==1
)) println(tester(2
+2
==5
))
In this example,
tester
is a partial function composed of two other
partial functions, truthier
and
fallback
. In the first println
statement, truthier
is executed because the partial
function’s internal case matches. In the second,
fallback
is executed because the value of the
expression is outside of the domain of truthier
.
The case
statements we’ve seen through our exploration of Scala are expanded
internally to partially applied functions. The functions provide the
abstract method isDefinedAt
, a
feature of the PartialFunction
trait used to specify
the boundaries of a partial function’s domain:
// code-examples/FP/partial/isdefinedat-script.scala
val
pantsTest:PartialFunction[String, String]
= {case
"pants"
=>
"yes, we have pants!"
} println(pantsTest.isDefinedAt("pants"
)) println(pantsTest.isDefinedAt("skort"
))
Here, our partial function
is a test for the string "pants"
. When we inquire as to
whether the string "pants"
is defined for this
function, the result is true
. But for the string
"skort"
, the result is false
. Were
we defining our own partial function, we could provide an implementation
of isDefinedAt
that performs any arbitrary test for the
boundaries of our function.
Just as you encountered partially applied functions before we defined them, you’ve also seen curried functions. Named after mathematician Haskell Curry (from whom the Haskell language also get its name), currying transforms a function that takes multiple parameters into a chain of functions, each taking a single parameter.
In Scala, curried functions are defined with multiple parameter lists, as follows:
def
cat
(s1:String
)(s2:String
) = s1 + s2
Of course, we could define more than two parameters on a curried function, if we like.
We can also use the following syntax to define a curried function:
def
cat
(s1:String
) = (s2:String
)=>
s1 + s2
While the previous syntax is more readable, in our estimation, using this syntax eliminates the requirement of a trailing underscore when treating the curried function as a partially applied function.
Calling our curried string concatenation function looks like this in the Scala REPL:
scala> cat("foo")("bar") res1: java.lang.String = foobar
We can also convert methods
that take multiple parameters into a curried form with the
Function.curried
method:
scala> def cat(s1: String, s2: String) = s1 + s2 cat: (String,String)java.lang.String scala> val curryCat = Function.curried(cat _) curryCat: (String) => (String) => java.lang.String = <function> scala> cat("foo", "bar") == curryCat("foo")("bar") res2: Boolean = true
In this example, we
transform a function that takes two arguments, cat
,
into its curried equivalent that takes multiple parameter lists. If
cat
had taken three parameters, its curried equivalent
would take three lists of arguments, and so on. The two forms are
functionally equivalent, as demonstrated by the equality test, but
curryCat
can now be used as the basis of a partially
applied function as well:
scala> val partialCurryCat = curryCat("foo")(_) partialCurryCat: (String) => java.lang.String = <function> scala> partialCurryCat("bar") res3: java.lang.String = foobar
In practice, the primary use for currying is to specialize functions for particular types of data. You can start with an extremely general case, and use the curried form of a function to narrow down to particular cases.
As a simple example of this approach, the following code provides specialized forms of a base function that handles multiplication:
def
multiplier
(i:Int
)(factor:Int
) = i * factorval
byFive = multiplier(5
)_
val
byTen = multiplier(10
)_
We start with
multiplier
, which takes two parameters: an integer, and
another integer to multiply the first one by. We then curry two special
cases of multiplier
into function values. Note the
trailing underscores, which indicate to the compiler that the preceding
expression is to be curried. In particular, the wildcard underscores
indicate that the remaining arguments (in this example, one argument) are
unspecified.
In the Scala console, we get predictable output when calling our curried functions:
scala> byFive(2) res4: Int = 10 scala> byTen(2) res5: Int = 20
We’ll revisit the
curry
method in Function Types.
As you can see, currying and partially applied functions are closely related concepts. You may see them referred to almost interchangeably, but what’s important is their application (no pun intended).
There are times when you have an instance of one type and you need to use it in a context where a different, but perhaps a similar type is required. For the “one-off” case, you might create an instance of the required type using the state of the instance you already have. However, for the general case, if there are many such occurrences in the code, you would rather have an automated conversion mechanism.
A similar problem occurs when you call one or more functions repeatedly and have to pass the same value to all the invocations. You might like a way of specifying a default value for that parameter, so it is not necessary to specify it explicitly all the time.
The Scala keyword
implicit
can be used to support both needs.
Consider the following code fragment:
val
name:String
="scala"
println(name.capitalize.reverse)
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]:
No conversion will be attempted if the object and method combination type check successfully.
Only methods with the implicit
keyword are
considered.
Only implicit methods in the current scope are considered, as well as implicit methods defined in the companion object of the target type.
Implicit methods aren’t chained to get from the available
type, through intermediate types, to the target
type. Only a method that takes a single available type instance and
returns a target type instance will be considered.
No conversion is attempted if more than one possible conversion method could be applied. There must be one and only one possibility.
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.RichStringclass
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]).
We saw in Chapter 2 that Scala version 2.8 adds support for
default argument values, like you find in other languages like Ruby and
C++. There are two other ways to achieve the same effect in all versions
of Scala. The first is to use function currying, as we have seen. The
second way is to define implicit values, using the
implicit
keyword.
Let’s examine how implicit values work:
// code-examples/FP/implicits/implicit-parameter-script.scala
import
scala.runtime.RichStringdef
multiplier
(i:Int
)(implicit
factor:Int
) { println(i * factor) }implicit
val
factor =2
multiplier(2
) multiplier(2
)(3
)
Our multiplier takes two
lists of parameters. The latter includes an integer value, factor
, marked implicit
.
This keyword informs the compiler to seek the value for factor
from the surrounding scope, if
available, or to use whatever parameter has been explicitly supplied to
the function.
We’ve defined our own
factor
value in scope, and that value is used in the
first call to multiplier
. In the second call, we’re
explicitly passing in a value for factor
and it
overrides the value in the surrounding scope.
Essentially, implicit
function parameters behave as parameters with a default value, with the
key difference being that the value comes from the surrounding scope. Had
our factor
value resided in a class or object, we would
have had to import it into the local scope. If the compiler can’t
determine the value to use for an implicit parameter, an error of “no
implicit argument matching parameter” will occur.
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.
Typically, parameters to functions are by-value parameters; that is, the value of the parameter is determined before it is passed to the function. In most circumstances, this is the behavior we want and expect.
But what if we need to write a function that accepts as a parameter an expression that we don’t want evaluated until it’s called within our function? For this circumstance, Scala offers by-name parameters.
A by-name parameter is specified by omitting the parentheses that normally accompany a function parameter, as follows:
def
myCallByNameFunction
(callByNameParameter:=> ReturnType
)
Without this syntactic shortcut, this method definition would look like the following:
def
myCallByNameFunction
(callByNameParameter: ()=>
ReturnType
)
And what’s more, we would have to include those unsightly, empty parentheses in every call to that method. Use of by-name parameters removes that requirement.
We can use by-name
parameters to implement powerful looping constructs, among other things.
Let’s go crazy and implement our own while
loop,
throwing currying into the mix:
// code-examples/FP/overrides/call-by-name-script.scala
def
whileAwesome
(conditional:=> Boolean
)(f:=> Unit
) {if
(conditional) { f whileAwesome(conditional)(f) } }var
count =0
whileAwesome(count <5
) { println("still awesome"
) count +=1
}
What would happen if we
removed the arrow between conditional:
and
Boolean
? The expression count < 5
would be evaluated to true
before being passed into our
custom while
loop, and the message “still awesome”
would be printed to the console indefinitely. By delaying evaluation until
conditional
is called inside our function with a
by-name parameter, we get the behavior we expect.
In Overriding Abstract and Concrete Fields in Traits, we showed several scenarios where
the order of initialization for fields in override scenarios can be
problematic. We discussed one solution, pre-initialized
fields. Now we discuss the other solution we mentioned
previously, lazy val
s.
Here is that example
rewritten with a lazy val
:
// code-examples/FP/overrides/trait-lazy-init-val-script.scala
trait
AbstractT2
{ println("In AbstractT2:"
)val
value:Int
lazy
val
inverse = { println("initializing inverse:"
);1.0
/value }//println("AbstractT2: value = "+value+", inverse = "+inverse)
}val
c2d =new
AbstractT2
{ println("In c2d:"
)val
value =10
} println("Using c2d:"
) println("c2d.value = "
+c2d.value+", inverse = "
+c2d.inverse)
The is the output of the script:
In AbstractT2: In c2d: Using c2d: initializing inverse: c2d.value = 10, inverse = 0.1
As before, we are using an
anonymous inner class that implicitly extends the trait. The body of the
class, which initializes value
, is evaluated
after the trait’s body. However, note that
inverse
is declared lazy
, which
means that the righthand side will be evaluated only when
inverse
is actually used. In this
case, that happens in the last println
statement. Only
then is inverse
initialized, using
value
, which is properly initialized at this
point.
Try uncommenting the
println
statement at the end of the
AbstractT2
body. What happens now?
In AbstractT2: initializing inverse: AbstractT2: value = 0, inverse = Infinity In c2d: Using c2d: c2d.value = 10, inverse = Infinity
This
println
forces inverse
to be
evaluated inside the body of AbstractT2
, before
value
is initialized by the class body, thereby
reproducing the problem we had before.
This example raises an
important point; if other val
s use the lazy
val
in the same class or trait body, they should be declared
lazy
, too. Also, watch out for function calls in the
body that use the lazy val
.
So, how is a lazy
val
different from a method call? In a method call, the body is
executed every time the method is invoked. For a
lazy val
, the initialization “body” is evaluated only
once, when the variable is used for the first time. This one-time
evaluation makes little sense for a mutable field. Therefore, the
lazy
keyword is not allowed on var
s.
(They can’t really make use of it anyway.)
You can also use
lazy val
s to avoid costly initializations that you may
not actually need and to defer initializations that slow down application
startup. They work well in constructors, where it’s clear to other
programmers that all the one-time heavy lifting for initializing an
instance is done in one place.
Another use for laziness is to manage potentially infinite data structures where only a manageable subset of the data will actually be used. In fact, mathematic notation is inherently lazy. When we write the Fibonacci sequence, for example, we might write it as an infinite sequence, something like this:
Fib = 1, 1, 2, 3, 5, 8, ...
Some pure functional languages are lazy by default, so they mimic this behavior as closely as possible. This can work without exhausting resources if the user never tries to use more than a finite subset of these values. Scala is not lazy by default, but it does offer support for working with infinite data structures. We’ll address this topic in Infinite Data Structures and Laziness.
When object-oriented programming went mainstream in the late ’80s and early ’90s, there was great hope that it would usher in an era of reusable software components. It didn’t really work out that way, except in some rare cases, like the windowing APIs of various platforms.
Why did this not happen? There are certainly many reasons, but a likely source is the fact that simple source or binary interoperability protocols never materialized that would glue these components together. The richness of object APIs was the very factor that undermined componentization.
Component models that have succeeded are all based on very simple foundations. Integrated circuits (ICs) in electronics plug into buses with 2n signaling wires that are boolean, either on or off. From that very simple protocol, the most explosive growth of any industry in human history was born.
HTTP is another good example. With a handful of message types and a very simple standard for message content, it set the stage for the Internet revolution. RESTful web services built on top of HTTP are also proving successful as components, but they are just complex enough that care is required to ensure that they work successfully.
So, is there hope for a binary or source-level component model? It probably won’t be object-oriented, as we’ve seen. Rather, it could be more functional.
Components should interoperate by exchanging a few immutable data structures, e.g., lists and maps, that carry both data and “commands.” Such a component model would have the simplicity necessary for success and the richness required to perform real work. Notice how that sounds a lot like HTTP and REST.
In fact, the Actor model has many of these qualities, as we’ll explore in the next chapter.