• Preliminaries
• Creational Patterns
• Structural Patterns
• Behavioral Patterns

Preliminaries

This book like any other text on programming includes code samples. Complete code for all of the samples is also available as a download. All of the sample is written in Scala, a modern functional programming (FP) language. We started off by talking about the first FP language, Lisp, so you might be wondering why we are not using that. While Lisp is indeed the first functional programming language, FP has itself evolved since the 1950's. In fact most would say that Lisp lacks several of the key characteristics of functional programming, though some of its dialects such as Scheme and Clojure address these shortcomings.

Functional programming is not immune from the dynamic vs. static typing debate that most programmers have participated in at some point. Lisp is a dynamic language, but the concept of types fits in nicely with many of the other tenets of functional programming. Indeed significant FP languages like ML and Haskell use a static type system. Many of the object-oriented (OO) design patterns that we will discuss are often best described using types, so it will be easiest to express these FP translations if our language has types.

That still leaves the question of why not use a language like Haskell? Scala has one more feature that makes it well suited to our task. It is a hybrid language with support for all of the concepts of object-oriented programming as well as functional programming. In fact, you can write Scala in a completely object-oriented manner and ignore its functional programming characteristics completely. That is a negative in the eyes of many FP advocates, but it is definite positive in the context of this book. It will allow us to express the OO design patterns in a standard OO way, but also translate this code to an FP-style without switching languages that we use. It should be noted that Scala is not unique in this capability, and that F# is another very modern language that combines OO and FP. We could have certainly used F# instead. With the always controversial choice of programming languages out of the way, we should also mention a few caveats. While this book will use Scala, it is not assumed that the reader already knows Scala. After all, this book is meant for folks who are new to FP, and that does not subscribe someone who already knows Scala. However even though we do not assume you already know Scala, this book is not meant to teach you Scala. There are many excellent books available with that purpose. If at the end of this book you find Scala interesting, you will hopefully read a book specifically about Scala.

So we don't assume you already know Scala, but this is not a full-blown introduction to Scala like you would find in a text dedicated to the topic. We will assume that you are quite used to programming and object-oriented programming in particular. With that in mind, let's look at a short Scala program that does something you are probably very familiar with: the quick sort. This will serve as a quick way to introduce some basics so that the Scala versions of the OO design patterns will be a little easier to quickly understand.

Introduction and motivation

The mathematician Alonzo Church first wrote about the lambda calculus in the 1930s. Some twenty years later, John McCarthy invented the Lisp programming language based on Church's lambda calculus. Lisp is not only one of the oldest programming languages, but it is also the oldest functional programming language. The lambda calculus provided an elegant mathematical model for expressing computation, and functional programming languages allow these mathematical expressions to become code that can be executed by a computer. Yet here we are more than sixty years later and the code used to create the most widely used software-from the Linux kernel, to the Google search engine, to the Angry Birds video game-bares little resemblance to the lambda calculus.

Code written in a functional programming language tend to be easily ran concurrently across many cores with no modification.

The renewed interest in functional programming can be largely attributed to the demand for concurrent programs. We are many years since Gordon Moore proclaimed that his eponymous law was dead, and that computations can only be done faster if they can be done in a concurrent manner. This is sobering proclamation forced many software developers to examine the tools of their trade and decide they were insufficient. Concurrent programming is too difficult to understand using the imperative, object-oriented used by most programmers. An object with methods that may or may not mutate its internal state, as well as the state of other related objects, cannot be safely shared by code whose execution is spread out over the many cores of a modern computer. Code like this usually has to undergo heavy modification to be made safe for concurrency, and often this modification is very difficult to get correct. However code written in a functional programming language tend to be easily ran concurrently across many cores with no modification.

Concurrency has certainly been the big draw for functional programming languages, but it is not the only one. Functional principles like the immutability of data make functional programs safe in concurrent environments, but they also make it much easier for engineers to understand the program. Functional programming languages have an expressiveness that can be directly traced back to the lambda calculus. Expressions that state what a program should do as opposed to how it should be done are much easier to understand and are natural in functional languages. Programs written in this manner tend to be more concise but more descriptive, and thus easier to write correctly. Many functional programming evangelists advocate writing programs that can be easily understood and proved correct over programs that can be easily and are thoroughly tested. Naturally programs that are easier to understand are also easier to debug.

It can be said that developers come to functional programming languages for the concurrency and stay for the correctness.

Functional programming may sound great in theory, but it can be very difficult in practice. Some developers may have already learned some functional programming, perhaps they even used it some while in school. Other developers may have an extensive background in mathematics and logic, and thus the lambda calculus inspired characteristics of functional programming languages might even seem intuitive. If you are not in one of these two camps, then chance are that functional programming languages may seem completely foreign. It may seem so different from the languages that you are familiar that you have a hard time even getting started. If that sounds even a little like you, then you are who this book was written for.

Learning your first functional programming language can seem every bit as daunting as learning a foreign language. The symbology and syntax can seem like an ancient alphabet. The programs are often very dense, and understanding one can be like listening to a foreign language spoken at high speed by native speakers. One approach that some people take to learning a foreign language is to learn to speak it conversationally instead of trying to first the formal alphabet, lexicon, and grammar. This is the approach that we will take with this book. We will take some everyday conversations that are familiar and comfortable to most programmers who use an object-oriented language, and we will translate them to our foreign language that we are trying to learn, i.e., to a functional programming language. Along the way we will explain some of the lexicon and grammar, i.e. common constructs and how they can be combined. At the end we will not only have these conversational elements ready to apply, but we will have gained some basic insights into the language. This will make it much easier to tackle a functional programming language heads on. Before we start translating these design patterns, let's lay some ground rules on how we will do this so that you know what to expect from each translation.

One approach that some people take to learning a foreign language is to learn to speak it conversationally instead of trying to first the formal alphabet, lexicon, and grammar. This is the approach that we will take with this book.

Quicksort in Scala

The quicksort is one of the most celebrated algorithms in computer science as it is elegant while still being very efficient and fast. To jog your memory, quicksort is a way of sorting a list of items. It is usually described in terms of sorting an array of integers, as it is straightforward to generalize from there. That is the same approach we will take. We will start with an array of integers. We will pick a pivot element and then partition the array so that all elements smaller than the pivot will be to the left of the pivot, while all elements greater will be to its right. This will leave the pivot in the correct position. We will then apply the quicksort to the two partitions and so on, until we are left with a sorted array. Here's how it looks in Scala.

def quicksort(nums:Array[Int]){ quicksort(nums, 0, 
nums.length - 1) }

A function (or method or subroutine) in Scala is denoted using the keyword def. Our first function is called quicksort and it takes a single parameter called nums that is of type Array. In Scala, Array is generic (parameterized) class, and thus nums is an Array of Int, Scala's integer type. Our quicksort method has one line of code, a call to a more flexible version of quicksort which works on a sub-array specified by its start and end index in the original array. So to quicksort the whole array, we specify the start (0) and beginning (nums.length - 1). Notice that the name of this function is the same, but it has different parameters. We can do this because Scala supports function overloading. Here is the fancier quicksort function.

def quicksort(nums:Array[Int], start:Int, end:Int){
     if (end - start < 1){
         // no-op 
     } else if (end - start == 1){
        if (nums(end) < nums(start)){
             swap(nums, start, end)
     } else { 
        var pivotIndex = choosePivot(nums, start, end); 
        swap(nums, start, pivotIndex) 
        pivotIndex = partition(nums, start, end) 
        if (pivotIndex > 0){ 
            quicksort(nums, start, pivotIndex - 1) 
     } 
     if (pivotIndex < end - 1){ 
         quicksort(nums, pivotIndex + 1, end) 
     } 
  } 
}

OK, now we're seeing more of the familiar quicksort logic.

• This function first handles the two trivial cases, of arrays of length 1 or 2.
• For the non-trivial cases, it uses a function called choosePivot to pick an element in the array to use a pivot. If you are very familiar with the quicksort then you know how crucial this choice of pivot can be, though for our example we will simply pick the first element of the array for the pivot.
• Our quicksort then swaps the pivot element with the first element by using another function that is appropriately called swap.
• Then our function partitions the array, so that all of the elements to the left of the pivot are smaller than the pivot and all of the elements to the right of the pivot are larger than the pivot. This is done using another function called partition.
• Finally if there are enough elements to the left and/or right of the pivot, we call quicksort on those subarrays. We won't bother with the choosePivot and swap functions, since they are fairly trivial.

This function first handles the two trivial cases, of arrays of length 1 or 2. For the non-trivial cases, it uses a function called choosePivot to pick an element in the array to use a pivot. If you are very familiar with the quicksort then you know how crucial this choice of pivot can be, though for our example we will simply pick the first element of the array for the pivot. Our quicksort then swaps the pivot element with the first element by using another function that is appropriately called swap. Then our function partitions the array, so that all of the elements to the left of the pivot are smaller than the pivot and all of the elements to the right of the pivot are larger than the pivot. This is done using another function called partition. Finally if there are enough elements to the left and/or right of the pivot, we call quicksort on those subarrays. We won't bother with the choosePivot and swap functions, since they are fairly trivial.

However let's take a look at the partition function.

def partition(nums:Array[Int], start:Int, end:Int) = {
    var pivotBoundary, partitionBoundary = start + 1
    var pivot = nums(start)
    while (partitionBoundary

This function starts off declaring two variables, pivotBoundary and partitionBoundary. The first is the boundary of where our pivot is in the array. So all of the elements whose index is greater than or equal to pivotBoundary will have a value greater than the value of the pivot (stored in the variable called pivot, declared on the next line.) The partitionBoundary variable denotes the boundary of the part of the array that we have partitioned and the part that is not partitioned. More precisely, partitionBoundary is the smallest index that has not been partitioned. Notice that we have initialized both of these variables to start + 1. Next we perform the classic in-place quicksort partitioning. We start a loop that ends when partitionBoundary is equal to the end value, i.e. all of our array is partitioned. If the value at partitionBoundary is less than the pivot value, then we swap the values at the pivotBoundary and partitionBoundary and we increment the pivotBoundary. Finally once the loop finishes we swap the values at the beginning of the array and at one less than the pivotBoundary. This puts the pivot value at an index of pivotBoundary - 1 and we return this value to the caller so it knows where the pivot in the partition can be found.

Finally an experienced programmer might notice a couple of things. First, it would be better to only expose the first, one-parameter quicksort function and keep the other functions hidden, since they are just there to help out. In Scala this can be done by making those functions private. Second, while we have implemented a quicksort on an array of integers, our code has done very little that is specific to integers. The only thing that has relied on integers is the less-than comparison used in both the second quicksort function and the partition function. So you might be itching to make this algorithm generic, and indeed Scala's rich type system supports this. In fact, all we have to do is convert the function signatures:

private def quicksort[T

This declares that we can perform the quicksort on an Array of type T where T is a subtype of Ordered[T].

scala> val nums = Array(4,5,3,6,1) 
nums: Array[Int] = Array(4, 5, 3, 6, 1) 

scala> quicksort(nums) 
scala> nums res1: Array[Int] = Array(1, 3, 4, 5, 6) 
scala> val words = Array("I", "Will", "Possess", "Your", "Heart") 
words: Array[java.lang.String] = Array(I, Will, Possess, 
Your, Heart) 

scala> quicksort(words) scala> words res3: Array[java.lang.String] 
= Array(Heart, I, Possess, Will, Your)