Chapter 5. Functional programming
- Why functional programming matters
- Mixing functional programming with OOP
- Functions in various forms
- Monads and their practical examples
You’re already doing functional programming using Scala if you’ve been following the examples in the book. In some cases it’s explicitly mentioned or visible and in other cases it’s mixed with object-oriented constructs of the Scala language. This chapter focuses on functional programming concepts and how they can be implemented in Scala. The goal of the chapter is to make you comfortable with functional programming and help you to write code in functional programming style.
Functional programming is a programming paradigm that models computation as the evaluation of expressions. And expressions are built using functions that don’t have mutable state and side effects. Exploring the roots of functional programming is valuable.[1] Believe it or not, functional programming started around 1930 when Alonzo Church introduced lambda calculus.[2] A lambda calculus (λ calculus) is a formal mathematical system to investigate functions, function application, and function recursion. In lambda calculus functions are first-class values; functions can take other functions as a parameter and return functions as an output (higher-order functions). A function that adds two input parameters could be written like the following in lambda calculus:
1 Slava Akhmechet, “Functional Programming for the Rest of Us,” June 19, 2006, www.defmacro.org/ramblings/fp.html.
2 Lloyd Anderson, “Lambda Calculus,” http://mng.bz/tWaV.
λx. λy. x + y
Here λx. λy. x + y represents an anonymous function that takes x as a parameter and returns the new anonymous function λy. x + y that takes y as a parameter and returns the result of x + y. In lambda calculus all the functions are anonymous and represented by the symbol λ (hence the name lambda).
Lambda calculus is the main inspiration behind functional programming. Functional programming languages implement lambda calculus with some constraints and types. Not all programming languages have features like first-class functions, pattern matching, and so on, but it’s possible to do functional programming in almost all programming languages. The next section explains functional programming in detail.
5.1. What is functional programming?
Functional programming is programming with functions. There’s nothing much to it except understanding what’s meant by function in this context. A function relates every value of type X to exactly one value of Y (see figure 5.1). A type is associated with a set of values. Here type X represents the set of values (1, 2, 3) and Y represents the set of values (a, b, c).
Figure 5.1. A pure function where each value of X is mapped to exactly one value of Y
In Scala you could write the signature of such a function as follows:
def f: X => Y
A function provides the predictability that for a given input you will always get the same output. The following function is an example of that:
scala> def add(a: Int, b: Int): Int = a + b add: (a: Int,b: Int)Int scala> add(10, 10) res0: Int = 20
Here the function add: (Int, Int) => Int fits the definition of the function because for a given input, it’s always going to return the same result.
But what about the functions that depend on some external state and don’t return the same result all the time? They’re functions but they’re not pure functions. A pure function doesn’t have side effects. Any observable behavior change after the function finishes is considered a side effect. Updating global or static variables, writing data to the filesystem, displays on screen, calling other “side-effecting” functions, and throwing exceptions are all examples of side effects. The behavior of a pure function doesn’t depend on any external behavior or state. You’re also not allowed to mutate the arguments to the function or invoke a function that has side effects. The add function is a perfect example of a pure function, but the following weather function isn’t a pure function because the weather will change based on when you invoke the function:
def weather(zipCode: String) = {
val url =
"http://api.wunderground.com/auto/wui/geo/GeoLookupXML/index.xml?query="
Source.fromURL(url + zipCode)
}
Here I use the Weather Underground API[3] to get the weather information for a given ZIP code. Why care about pure functions? What’s the value of programming with pure functions?
3 Weather Underground, “A Weather API Designed for Developers,” http://mng.bz/VtC8.
The value is referential transparency. Referential transparency is a property whereby an expression could be replaced by its value without affecting the program. Let’s see an example of how referential transparency works. Assume the following is a part of a functional program:
... val v = add(10, 10) + add(5, 5) ...
Because add is a pure function, I can replace the function call add(10, 10) with its result, which is 20, without changing the behavior of the program. And similarly I could replace add(5, 5) with 10 without affecting the behavior of the program. Why should you care about referential transparency? What advantage does it give you?
5.1.1. The benefits of referential transparency
Referential transparency provides the ability to reason about your code. You can provide proof that your program works correctly by replacing pure functions with their values and reducing a complex expression to a simpler expression. Sometimes you can even compute the result of a program in your head. This ability to reason about code helps programmers to debug and solve complex problems easily. And therein lies the essence of functional programming. With varying difficulty you can do functional programming in any programming language. The essence of functional programming is referential transparency, and its benefit is referential transparency—the safety net that allows you to easily find and fix problems. When you add that to the fact that Scala is a type-safe language, you can catch lots of problem ahead of time during compilation.
In Scala, functional programming is baked in with Scala’s object-oriented features, so sometimes it’s difficult to distinguish it when you have a language that allows you to define both methods and functions. You will explore this in detail, but for now remember that methods in Scala don’t have any type; type is only associated with the enclosing class, whereas functions are represented by a type and object.
Unfortunately, coming up with a definition of a functional programming language[4] is still hard. Everyone has his or her own definition, and I’m sure you’ll also come up with your own one day. But even if functional programming is possible in all languages, it doesn’t necessarily mean you should use it. It can be like trying to do OOP in a procedural language—it’s possible, but probably hard and painful. There is good news: writing functional programs in Scala is easy. The next section builds one from scratch.
4 David R. Maclver, “A Problem of Language,” May 15, 2009, http://mng.bz/nsi2.
5.1.2. A pure functional program
A pure functional program is a single referentially transparent expression. An expression is constructed with a combination of subexpressions created using the language. An expression always evaluates to a result. The following is an example of a pure functional program:
object PureFunctionalProgram {
def main(args: Array[String]):Unit = singleExpression(args.toList)
def singleExpression: List[String] => (List[Int], List[Int]) = { a =>
a map (_.toInt) partition (_ < 30)
}
}
Here the main method is the entry point to our purely functional program, and the rest of the program is defined by a single expression that takes a collection of strings and returns a Tuple of two collections based on some partition criteria. The single expression is in turn built on two subexpressions: a map (_.toInt) and <result of first sub expression> partition (_ < 30). If you can start thinking about your program as a collection of subexpressions combined into one single referentially transparent expression, you have achieved a purely functional program. Yes, you still may have to read inputs from the console or from the filesystem, but think of those as implementation details. It doesn’t matter how the inputs are read—the behavior of your purely functional program should not change.
5.2. Moving from OOP to functional programming
Programmers in Java and C# as well as C++ are already familiar with the concepts of classes and objects and are probably comfortable with OOP. But how can one transition to a more functional programming style from a more OOP experience? Scala is a great language for this because it allows you to combine the styles in an elegant and well-engineered fashion. It’s perfectly okay to start with Scala and focus on only its object-oriented features, but as you become more comfortable with the language and its library, you may slowly transition to a more functional programming style as discussed in the previous section. In this section I highlight a few techniques that you can use to move to a more functional programming style and yet retain OO techniques and style as appropriate.
5.2.1. Pure vs. impure programming
At first glance it may seem odd to compare object-oriented and functional programming at a pure versus impure level. Although it’s true that you can write object-oriented code without side effects, in practice OOP easily becomes riddled with undesirable side effects. Typically, OO-style applications are built around the idea of mutable state (produces side effects) managed by various objects inside the application.
Object-oriented solutions are modeled around classes and objects where data tends to carry collections of methods, and these methods share and at times mutate the data. A functional programming style only deals with values where problems are solved by the application of functions to data. Because data is only represented by value, each application of a function results in a new value without any side effects.
Another way to differentiate them is that functional programming raises the abstraction level over OOP. Object-oriented programming sometimes feels machine-dependent—concepts like pass by value, pass by reference, equality, and identity are defined based on how the program is interpreted or executed at runtime. If you only work with values, then how your functional program is interpreted and executed becomes irrelevant. Remember, you can compute the result of a purely functional program using paper and pen; running it using a machine is an implementation detail.
In languages where you have only functions, such as Haskell and Clojure, you don’t have to worry about impurity. But Scala bakes both object-oriented and functional programming into one language, so you have to be extra careful about side effects. In Scala you still have to define classes (or traits) and objects to group your methods and function values. And it’s your responsibility as a developer to make sure you don’t rely on mutable data defined inside the class.
Take the following example, where you have a class that represents a square with one method that computes the area:
class Square(var side: Int) {
def area = side * side
}
The problem with this class is that the side property is mutable, and the area method depends on the value of the side to compute the area of the square. It’s clearly not a pure solution because the result of the area method depends on some external state—in this case, the value of the side property. It’s also hard to reason about the area method because now you have to keep track of the value of the side property at a given point in time. To implement Square in a pure functional way, you’ll use a Successor Value pattern[5] (sometimes called a functional object), where each change of state returns a copy of itself with the new state:
5 Michael Feathers, “The Successor Value Pattern, March 22, 2009, http://mng.bz/b27e.
class PureSquare(val side: Int) {
def newSide(s: Int): PureSquare = new PureSquare(s)
def area = side * side
}
In this new solution, every time the side property is modified, a new copy of PureSquare is returned, so you don’t have to worry about a mutable state and the result of the area method because now it’s associated with a new object, PureSquare. This common pattern is used when you have to model a state that could change over time. The Java String class we’ve been using throughout the book is an example of a Functional Object pattern. Now your challenge is to design all your objects in a similar fashion because it’s easy to introduce side effects unintentionally. Watch out for all the vars and setters that your methods depend on and make them as pure as possible. Remember going forward: referential transparency is a criterion of a good design.
5.2.2. Object-oriented patterns in functional programming
Design patterns are just as useful in functional programming as they are in OOP as tools for communication. Some design patterns like Singleton, Factory, and Visitor are already implemented as part of the language. You can easily implement Singleton and Factory patterns using Scala objects. You could implement the Visitor pattern using the pattern-matching feature of Scala. Take a look at the Strategy pattern.[6] This pattern allows you to select algorithms at runtime and can easily be implemented using a higher-order function:
6 “Strategy pattern,” February 2011, http://en.wikipedia.org/wiki/Strategy_pattern.
def calculatePrice(product: String, taxingStrategy: String => Double) = {
...
...
val tax = taxingStrategy(product)
...
}
Because taxingStrategy is defined as a function, you can pass different implementations of the strategy. Similarly you can also implement the template method pattern using the higher-order functions.
Higher-order functions are also useful when dealing with dependency injection (DI). You can use function currying to inject dependencies. For example, you can define a type for tax strategy and have a function that calculates a tax based on strategy and the product code:
trait TaxStrategy {def taxIt(product: String): Double }
class ATaxStrategy extends TaxStrategy {
def taxIt(product: String): Double = ...
}
class BTaxStrategy extends TaxStrategy {
def taxIt(product: String): Double = ...
}
def taxIt: TaxStrategy => String => Double = s => p => s.taxIt(p)
Here I have two implementations of the TaxStrategy trait, ATaxStrategy and BTaxStrategy. The interesting code here is the taxIt function. This function takes an instance of TaxStrategy and returns a function of type String => Double, which encapsulates the taxing strategy. With this setup you can easily create new functions by injecting different types of tax strategy:
def taxIt_a: String => Double = taxIt(new ATaxStrategy) def taxIt_b: String => Double = taxIt(new BTaxStrategy)
Your knowledge of OO design patterns is still valuable in Scala, but its style of implementation has changed. Functional programming brings new sets of patterns that you haven’t encountered before, and those are mainly related to recursive programming.
5.2.3. Modeling purely functional programs
So far, I’ve been focusing on implementing pure functional solutions, but what if you have to deal with side effects like writing to a socket or to a database? You can’t avoid that, and in fact any useful program you write for an enterprise probably has a side effect. Are you doomed? No! The trick is to push the side effects as far down as possible. You can create an impure layer, as shown in figure 5.2, and keep the rest of your application as pure and functional as possible. In section 5.5 you’ll learn how to build abstractions around code that by necessity include side effects.
Figure 5.2. Separating pure and side-effecting (impure) code. The side-effecting code should form a thin layer around the application.
To demonstrate how this works, you’re going to build a simple HTTP server that only serves files from a directory in which the server is started. You’re going to implement the HTTP GET command. Like any server, this HTTP server is full of side effects, like writing to a socket, reading files from the filesystem, and so on. Here are your design goals for the server you’re building:
- Separate the code into different layers, pure code from the side-effecting code.
- Respond with the contents of a file for a given HTTP GET request.
- Respond with a 404 message when the file requested is missing.
The essence of the problem is to parse the request to figure out the name of the requested file, locate the resource, and return the response. Let’s represent them with appropriate types and functions. The HTTP request is nothing but a stream of characters received from the client, and when building the pure model you don’t have to worry about how we receive them—all you care about is that it’s a collection of characters:
type Request = Iterator[Char]
Similarly the response could also be represented as a collection of characters. For simplicity, represent that using List[String]:
type Response = List[String]
The resource locator type should be able to check whether the file exists, retrieve the file contents, and check the content length. The first one would be used to determine whether to return the 200 response code or 404 error code. Here’s how the ResourceLocator type looks:
type ResourceLocator = String => Resource
trait Resource {
def exists: Boolean
def contents: List[String]
def contentLength: Int
}
The ResourceLocator is a function type that takes the name of a resource and returns the resource. The resource is represented by a trait Resource and provides all the methods you need to create the appropriate HTTP response. The important point here is that you’re building an abstract layer that will allow you to design your application using values and pure functions. The following listing gives the complete implementation of the pure side of things, where the GET method returns success (HTTP 200) or failure (HTTP 404) response.
Listing 5.1. A pure implementation of an HTTP server
The GET method first retrieves the requested filename, then locates the file based on the given locator. The _200 and _404 are partial functions and are defined for success and failure cases respectively. The _200 function is invoked if the file exists; otherwise, the _404 function is invoked.
Now that the core of the server is implemented, you need to hook it to the real world so it can be useful and practical. First you have to open a server socket at an appropriate port and listen for requests. You also have to handle each request in a separate thread so that you can listen for a new request while you’re processing the old one. You can find the complete working copy in the code base for the chapter as NanoHttpServer.scala. Here let’s focus on the implementation of Resource and ResourceLocator:
import Pure._
case class IOResource(name: String) extends Resource {
def exists = new File(name).exists
def contents = Source.fromFile(name).getLines.toList
def contentLength = Source.fromFile(name).count(x => true)
}
implicit val ioResourceLocator: ResourceLocator =
name => IOResource(name)
The IOResource reads files from the local filesystem using the scala.io.Source, and the ResourceLocator is a function that takes the name of the file and creates an instance of IOResource. The only thing left now is reading and writing to the socket. You’ve successfully separated the side effects from pure functional code. This is an important technique to remember when designing your application: push the side effects to the edge of the world. You can refer to the nano-http-server project in the code base of this chapter for the complete implementation. To run the example, you need to install the simple build tool covered in the next chapter. In the next section you’ll explore various types of functions and their applications.
5.3. Functions in all shapes and forms
Functional programming is all about functions, and Scala lets you create functions in various forms. Functions in Scala are first-class values. That means you can treat functions like Int or String as type values in Scala. You can create them as a value, pass them to functions as parameters, and compose them to create new functions.
5.3.1. Methods vs. functions
The common form of a function in Scala is defined as a member of a class. It’s called a method:
class UseResource {
def use(r: Resource): Boolean = {...}
}
Here use is a method defined in the class UseResource. One downside of using methods is that it’s easy to depend on the state defined by the enclosing class without explicitly passing the dependencies as parameters—be careful about that because that will take you away from having pure methods. Unlike functions, methods don’t have any type associated with them. Scala infuses functional programming with OOP by transforming functions into objects. For example, you can assign a function literal (anonymous function) to a value like the following:
val succ = (x: Int) => x + 1
Here succ is associated with a function Int => Int and it’s nothing but a shorthand definition of the following:
val succFunction = new Function1[Int, Int] {
def apply(x:Int) : Int = x + 1
}
Both of those definitions are equivalent. Functions in Scala are represented by a type and object, but methods aren’t. Methods are only associated with the enclosing class. The good news is that Scala lets you convert methods to functions using a transform process called Eta expansion. You can take any existing method and append _ (underscore) to create the function. The following code creates a function version of the use method from the previous example:
val use_func: Resource => Boolean = (new UseResource).use _
It’s common in Scala to convert methods into functions and pass them around to other functions. In the next section you’ll look into examples of higher-order functions and how they help you in solving problems.
5.3.2. Higher-order functions
Higher-order functions are those that take functions as parameters or return functions as a return value. You’ve already seen plenty of examples of higher-order functions throughout the book. In the Scala collections you’ll notice the use of higher-order functions everywhere. For example, to filter out all the even numbers from a List, you write something like the following:
scala> val l = List(1, 2, 3, 5, 7, 10, 15) l: List[Int] = List(1, 2, 3, 5, 7, 10, 15) scala> l.filter(_ % 2 == 0) res0: List[Int] = List(2, 10)
Here % 2 == 0 is a function literal (I’m sure you already knew that). Now let’s see how you can use higher-order functions to solve a day-to-day problem. One of the most common programming problems is managing resources. For example, to send data over a TCP connection, you have to open a socket, send data, and, hopefully, remember to close the socket. Similarly, to read data from a file in a filesystem, you have to open the file, read data, and then close the file handle. The typical way to manage these resources is to wrap them in a try-finally block like the following:
val r: Resource = getResource()
try {
useResourceToDoUsefulStuff(r)
} finally {
r.dispose()
}
You get a handle to the resource (socket or file) and use the resource in the try-finally (sometimes catch) block to dispose of the resource once you’re done using it. Now let’s see how you can easily separate the resource-management part (try-finally) from the use:
def use[A, B <: Resource ](r: Resource)(f: Resource => A): A = {
try {
f(r)
} finally {
r.dispose()
}
}
Here the use function is taking care of the resource management, and the function parameter f allows you to use the resource without worrying about releasing or disposing of it. Now the code for sending data through a socket will be like the following:
use(socketResource) { r=>
sendData(r)
}
This abstraction for managing resources will remove duplication from your code and centralize the way you manage and dispose of resources after use, without cluttering the code base with try-finally blocks. To make this work you have to define a common type like Resource so you can create abstraction around the implementation. This is a common pattern in Scala known as the Loan pattern[7] (the object-oriented counterpart is called the Template Method pattern).
7 Kevin Wright (added), “Loan pattern,” last edited May 25, 2011, https://wiki.scala-lang.org/display/SYGN/Loan.
Another example will demonstrate the power of higher-order functions in terms of the design flexibility it provides to programmers. One of the common pieces of logic that you’ll see across code bases goes something like the following:
2. Perform some side-effect-inducing operation for the instance.
3. Use the instance in the other parts of the code.
You have to perform steps 1 and 2 before you can start using the instance. The problem is, there’s structure to isolate the side-effect-inducing code, and it gets mixed with steps 1 and 3. Let’s take a look at the following pseudo Scala code:
val x = Person(firstName, lastName)
x.setInfo(someInfo)
println("log: new person is created")
mailer.mail("new person joined " + x)
x.firstName
Because steps 1 and 2 need to be done together before you can start using the instance, it would be nice if you could do it all as part of step 1 when you create an instance (like inside the constructor). But the problem with that approach is that you might not have everything that’s accessible to the context of the caller namespace. For example, the reference to mailer in the previous code snippet is only available to the context of the caller and not available inside the Person instance. One way you can address this problem is to use higher-order functions. I will define a function called tap that will take an instance and a side-effect-inducing function. This function will apply the side-effecting function to the instance and return the instance. Here’s how you could write it:
def tap[A](a: A)(sideEffect: A => Unit): A = {
sideEffect(a)
a
}
With this new tap function, your code will get some structure:
val x = Person(firstName, lastName)
tap(x) { p =>
import p._
setInfo(someInfo)
println("log: new person is created")
mailer.mail("new person joined " + x)
}.firstName
This is better than what you had, but you can still improve on it using Scala’s implicit conversion. Because this is so common, you’ll make this function available to all the types. The following listing gives the complete working example.
Listing 5.2. Kestrel combinator
Compare the code inside the main method 
with the pseudo code you started with, and you should see the difference. Now the code is more concise and well-structured,
and the side effects are not leaking through. The best part of this pattern is that it lets you compose without relying on
sequences of instructions. This is also a common combinator (higher-order function) in functional programming called Kestrel.[8] Kestrel is one of the many combinators defined in Raymond Smullyan’s book To Mock a Mockingbird (Knopf, 1985). The combinatory logic is beyond the scope of this book, but I highly recommend To Mock a Mockingbird. I’d like to highlight that once you start thinking in higher-order functions, you’ll see opportunities for extracting reusable
code that you never thought possible. Think, for example, about foldRight and foldLeft defined in the Scala collection library, which let you apply any binary function. The application of higher-order functions
lets you write don’t-repeat-yourself (DRY) code and you should use it as much as possible. The next section discusses partial
functions and how they help in the composition of functions.
8 Reg Braithwaite, “Kestrels,” http://mng.bz/WKns.
5.3.3. Function currying
Function currying is a technique for transforming a function that takes multiple parameters into a function that takes a single parameter. Look at the following function definition that takes two parameters:
scala> trait TaxStrategy { def taxIt(product: String): Double }
defined trait TaxStrategy
scala> val taxIt: (TaxStrategy, String) => Double = (s, p) => s.taxIt(p)
taxIt: (TaxStrategy, String) => Double = <function2>
The taxIt function takes TaxStrategy and String parameters and returns Double value. To turn this function into a curried function, you can invoke the built-in curried method defined for function types:
scala> taxIt.curried res2: TaxStrategy => String => Double = <function1>
It turned the taxIt function into a function that takes one parameter and returns another function that takes the second parameter:
scala> class TaxFree extends TaxStrategy { override def taxIt(product:
String) = 0.0 }
defined class TaxFree
scala> val taxFree = taxIt.curried(new TaxFree)
taxFree: String => Double = <function1>
scala> taxFree("someProduct")
res3: Double = 0.0
What’s the benefit of using function currying? It allows you to turn generalized functions into specialized ones. For example, turning the taxIt function to function currying allows you to create a more specialized function like taxFree. This is similar to how DI works in OOP. Here I injected the taxStrategy as a dependency to the curried function to create a new function that uses the dependency. You can also turn existing methods to curried functions using an underscore (_). The following code example redefines the taxIt function as a method and then converts it to a curried function:
scala> def taxIt(s: TaxStrategy, product: String) = { s.taxIt(product) }
taxIt: (s: TaxStrategy, product: String)Double
scala> val taxItF = taxIt _
taxItF: (TaxStrategy, String) => Double = <function2>
scala> taxItF.curried
res4: TaxStrategy => String => Double = <function1>
You can also define methods in currying style using multiple parameters set:
scala> def taxIt(s: TaxStrategy)(product: String) = { s.taxIt(product) }
taxIt: (s: TaxStrategy)(product: String)Double
scala> val taxFree = taxIt(new TaxFree) _
taxFree: String => Double = <function1>
You’ve used multiple parameters set for higher-order functions to pass anonymous function like closures, but now you’ve learned another benefit of function currying: dependency injection.
5.3.4. Function composition and partial functions
A partial function is a function that’s only defined for a subset of input values. This is different from the definition of a pure function (see section 5.1), which is defined for all input parameters. Figure 5.3 shows a partial function f: X -> Y which is only defined for X=1 and X=3, not X=2.
Figure 5.3. A partial function that’s only defined for a subset of parameter values, in this case only for 1 and 3. Compare this figure with figure 5.1.
In Scala partial functions are defined by trait PartialFunction[-A, +B] and extend scala.Function1 trait. Like all function types, PartialFunction declares the apply method and an additional method called def isDefinedAt(a: A):Boolean. This isDefinedAt method determines whether the given partial function is defined for a given parameter.
The easiest way to create a partial function is by defining an anonymous function with pattern matching. The following code example defines the partial function shown in figure 5.3:
def intToChar: PartialFunction[Int, Char] = {
case 1 => 'a'
case 3 => 'c'
}
In this case the Scala compiler will translate the preceding code snippet to something like the following:
new PartialFunction[Int, Char] {
def apply(i: Int) = i match {
case 1 => 'a'
case 3 => 'c'
}
def isDefinedAt(i: Int): Boolean = i match {
case 1 => true
case 3 => true
case _ => false
}
}
The PartialFunction trait provides two interesting combinatory methods called orElse and andThen. The orElse method lets you combine this partial function with another partial function. It’s much like if-else, where if the current partial function isn’t defined for a given case, then the other is invoked. You can chain multiples of them to create if-else if patterns. On the other hand, andThen lets you compose transformation functions with a partial function that works on the result produced by the partial function. An example will demonstrate the power of functional composition.
Note
It’s important to understand the usefulness of partial functions. They let you write smaller functions, keeping in mind the single responsibility principle, and then compose them together to create a complete function that provides the solution. Be aware of the performance penalty. When composing partial functions, always remember that the isDefinedAt method of each composing partial function might get invoked multiple times.[9]
9 Vassil Dichev, “Speaking My (Programming) Language?,” July 31, 2011, http://mng.bz/9yOx.
Assume you’re building a pricing system for all the patient claims for which you need to invoice your providers. Typically these systems are complicated, so I’ll simplify things a little. The pricing depends on the type of the claim and location. Furthermore, the location is divided by state codes or ZIP codes. Each of these factors could influence the final price you’ll charge your providers. Also, not all claims have specific pricing logic associated with them, so you have to have a catch-all default so that you can always calculate the price. I’m sure this sounds similar to some of the business rules you implement for your enterprise. Let’s implement this small problem using partial functions. First define the claim types you’re going to work with:
sealed trait Claim { val claimId: Int }
case class Full(val claimId: Int) extends Claim
case class Partial(val claimId: Int, percentage: Double) extends Claim
case class Generic(val claimId: Int) extends Claim
Each claim takes a claimId that uniquely identifies it in the system and optionally some additional properties associated with the claim. Understanding how each claim is different isn’t important for this exercise, but remember that they’re different.
To request a price, the requestor has to provide the claim information, the location, and the product identifier. In this application you can easily represent that using case classes:
case class Location(stateCode: Option[String], zipCode: Option[String]) case class Req(productId: String, location: Location, claim: Claim)
Except for Generic claim, the pricing for each claim is determined by specific business logic, and all the calculations start with some base prices associated with the product. To determine the final price of a product and the claim, you have to provide the request information and the base price. You can capture that with a type variable called PC (Pricing Criteria):
type PC = Tuple2[Req, Option[Double]]
Here the Option[Double] represents the base price of the product. The following code example implements the business logic associated with each Full and Partial claim:
def handleFullClaim: PartialFunction[PC, PC] = {
case (c@Req(id, l, Full(claimId)), basePrice) =>
...
}
def handlePartialClaim: PartialFunction[PC, PC] = {
case (c@Req(id, l, Partial(claimId, percentage)), basePrice) =>
...
}
Similarly, the final price to the provider is also influenced by the location of the claim. Both state code and ZIP code could change the price. The separate location-based logic could also be implemented as separate partial functions, as in the following:
def handleZipCode: PartialFunction[PC, PC] = {
case (c@Req(id, Location(_, Some(zipCode)), _), price) =>
...
}
def handleStateCode: PartialFunction[PC, PC] = {
case (c@Req(id, Location(Some(stateCode), _), _), price) =>
...
}
To create the final solution to calculate the price for a provider, you can combine these smaller partial functions and be done with it. According to the business rules, you should first determine the price based on the claim and further refine the calculated price based on location. You can easily combine these functions with the orElse and andThen combinators you learned at the beginning of this section:
def claimHandlers = handleFullClaim orElse handlePartialClaim
def locationHandlers = handleZipCode orElse handleStateCode
def priceCalculator: PartialFunction[PC, PC] =
claimHandlers andThen locationHandlers
The preceding code implements the business rules the way they’ve been described. Calculate the price using the claim, then refine it based on location. As the business rules or new claim types get added to the system, you can easily modify the combinations and add new partial functions. For example, you aren’t handling the Generic claim type yet. You can easily add it to the final solution by adding another orElse block to the claimHandlers.
The partial functions are applicable to more situations than you might think. For example, throwing exceptions from a function or a method could be considered a partial function. The function that’s throwing an exception isn’t defined for the case that raises the exception. Instead of throwing an exception, you could consider making the function partial and combining it with some other function that knows how to handle the exception case. In Scala, partial functions are powerful when it comes to function composition. Keep that in mind when you write your code.
5.3.5. Recursion
Recursion is where a function calls itself. Recursion is a useful tool in your functional programming toolbox. It lets you break problems into subproblems and subproblems further down into sub-subproblems.[10] This allows for solving these smaller subproblems and then combining them together to produce the final solution. Think of recursion as the assembly language of functional programming.
10 James O. Coplien, “To Iterate is Human, to Recurse, Divine,” C++ Report 10(7), July/August 1988, pp 43-51, http://mng.bz/wXr4.
One of the main benefits of recursion is that it lets you create solutions without mutation. In the next small exercise, you have to calculate the sum of all the elements of a List without using any mutation. You can solve the problem in many ways using library functions, but let’s try to build it from scratch. The imperative solution to this problem looks something like the following:
scala> var sum = 0
scala> for(e <- List(1,2,3)) { sum += e }
You declare a mutating variable and accumulate the result by iterating through all the elements of the collection. And the recursion-based solution would look something like the following:
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case x :: ys => x + sum(ys)
}
The difference is that a recursion-based solution doesn’t use any mutable temporary variables and it lets you break the problem into smaller pieces. A typical way to implement recursive functions in Scala is to use pattern matching. Pattern matching helps you break the problem into subproblems where each case potentially represents a subproblem. Recursion always looks easy when someone else is doing it, but it can be hard when you have to do it. The next section explains how you can start thinking recursively by following simple steps.
5.4. Thinking recursively
Suppose you’re given a list of elements, and your job is to remove the duplicates. For example, if you’re given List(0,1,2,3,2,1,0), the output should be List(0, 1, 2, 3). I’m going to show you a step-by-step process to come up with a recursion-based solution.[11]
11 Graham Hutton, Programming in Haskell (Cambridge University Press, 2007), www.cs.nott.ac.uk/~gmh/book.html.
The first step is to identify the type. Thinking in terms of type will help you think about the input parameter and the return value of the function. Don’t generalize yet, but think about what you have and what you want to achieve. Sometimes using a concrete example helps. The type of the removeDups function will look like the following:
removeDups: List[Int] => List[Int]
The next step is to declare all the cases that you need to handle. In the case of removeDups, you have to handle the following cases:
case Nil => case x :: ys if(ys.contains(x)) => case x :: ys =>
The first case checks for an empty list, the second case is for a duplicate element in the list, and the third case is for a nonduplicate element. Depending on the type of the problem you’re trying to solve, you might end up with many cases. Don’t worry—you’ll refactor the solution later into a more elegant solution after it’s working.
The next step is to implement the simple cases. Here you have only one simple case, and that’s case Nil. Because empty lists can’t have any duplicates, you can safely return an empty list back:
case Nil => Nil case x :: ys if(ys.contains(x)) => case x :: ys =>
The next step is to implement the other case(s) when you have a nonempty list. For this step, it’s useful to consider which constructs and functions you have that you could use to implement these cases. For the second case, you want to throw out the x because it’s a duplicate and continue with the processing for the rest of the elements in the list. The easiest way to do that is to invoke removeDups again by passing the ys as a parameter.
case Nil => Nil case x :: ys if(ys.contains(x)) => removeDups(ys) case x :: ys =>
For the last case you want to continue with the rest of the list and append the nonduplicate element to the list:
case Nil => Nil case x :: ys if(ys.contains(x)) => removeDups(ys) case x :: ys => removeDups(ys) :+ x
The final step is to generalize and simplify the solution. Start with your type signature and see whether you can generalize the solution. In this case, you started with List[Int] => List[Int], but do you need to specify Int here? Are you using anything that’s specific to the Int?
In the removeDups solution, you don’t care about the type of List as long as there is a way to compare two elements. You can generalize the type signature of removeDups as in the following:
def removeDups[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case x :: ys if(ys.contains(x)) => removeDups(ys)
case x :: ys => removeDups(ys) :+ x
}
Next comes the refactoring. Let’s see whether you can simplify the implementation. In this case, it looks simple so you don’t need to go any farther. But sometimes foldl or foldr could simplify the solution.
The best way to get better at recursion is practice. Once you become comfortable, these steps will come naturally to you, but until then let them guide you in how to implement recursive solutions.
5.4.1. Tail recursion
Before I talk about tail recursion, let me explain how head recursion works. Head recursion is the more traditional way of doing recursion, where you perform the recursive call first and then take the return value from the recursive function and calculate the result.
In tail recursion you perform your calculation first and then execute the recursive call by passing the result of the current step to the next step. I’ll provide an example shortly to demonstrate how you can write recursive functions, keeping tail recursion in mind. But first it’s useful to consider why recursion is avoided in Java and other similar languages.
Generally when you call a function an entry is added to the call stack of the currently running thread. The downside is that the call stack has a defined size, and once you violate that boundary you get a StackOverflowError exception. This is why Java developers prefer to iterate rather than recurse. Because Scala runs on the JVM, Scala programs also suffer from this problem. But the good news is that starting with Scala 2.8.1, Scala overcomes this limitation by doing tail call optimization. Here’s a tail call optimization example. In the following code snippet you’re calculating the length of a given List:
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case x :: ys => 1 + length(ys)
}
This is a classic example of head recursion where you call length recursively and then add all the ones at the end. If you try to execute this function with a large List (100,000 elements, for example), you will get a StackOverflowError. Now rewrite the preceding function in tail recursion:
def length2[A](xs: List[A]): Int = {
def _length(xs: List[A], currentLength: Int): Int = xs match {
case Nil => currentLength
case x :: ys => _length(ys, currentLength + 1)
}
_length(xs, 0)
}
In this version you aren’t doing any calculation after the recursive call. You do the calculation at each step and pass the result to the next step of the recursion. The question is, which one should you prefer? For Scala, you should always prefer the version that uses tail recursion because Scala tries to optimize tail recursive functions. Scala does tail call optimization at compile time, and the compiler transforms a tail recursive function into a loop. This way tail recursive functions don’t add additional entries to the call stack and don’t blow up. Scala can’t optimize every tail recursion—it can optimize functions but not nonfinal methods. The best way to know whether the Scala compiler can optimize your tail recursion is to use the @tailrec annotation because that way you’ll get a compiler warning if the Scala compiler fails to optimize your tail recursive functions or methods. The following listing has the complete length function with the @tailrec annotation.
Listing 5.3. Tail recursive function with @tailrec annotation
The common pattern for implementing a tail recursive function is to use a local function like _length. This local function approach allows you to have an additional parameter by which you can pass the result of the current step to the next step. Always remember when going for tailrec optimization that your recursion should be the last step in your function or final method.
5.5. Algebraic data types
Algebraic data type (ADT) is a classification. A data type in general is a set of values (think of Int as a type that identifies all the integer values). You can define an algebraic type by enumerating all the values of the set, except each value could have its own constructor. It also allows you to decompose the type using pattern matching. If that sounds like an abstract concept, let’s look at an example. So far you’ve learned that ADT is a kind of type that represents a set of values. ADTs could represent a finite or an infinite set of values. First, look at an example of a closed ADT (finite set of values) that explores why they’re valuable.
The easiest way to define an algebraic type in Scala is to use case classes. The following example code defines an Account type and its possible values:
object ADT {
sealed trait Account
case class CheckingAccount(accountId: String) extends Account
case class SavingAccount(accountId: String, limit: Double)
extends Account
case class PremiumAccount(corporateId: String, accountHolder: String)
extends Account
}
Here you’ve defined three account types, each with its own constructor taking various numbers of parameters. It also declares Account trait as sealed, and that means no one else can extend the trait and create a new type of Account unless it’s defined in the same source file. You’ve managed to create a finite ADT, but why case classes are a good implementation choice for ADTs is still not clear. The reason is pattern matching. Once you’ve created ADTs, you use them in functions. ADTs become much easier to deal with if they’re implemented as case classes because pattern matching works out of the box. In the following snippet printAccountDetails prints the details of each account:
object ADT {
...
def printAccountDetails(account: Account): Unit = account match {
case CheckingAccount(accountId) =>
println("Account id " + accountId)
case SavingAccount(accountId, limit) =>
println("Account id " + accountId + " , " + limit)
}
}
Along with the values and constructors, ADTs also come with a way to decompose the type through pattern matching so that you can easily use them in your functions. A powerful concept: once you create an algebraic data type, you get pattern matching support to readily use them in functions.
In the printAccountDetails function I intentionally left out the case for PremiumAccount in order to show you what happens when you compile the previous code. You’ll see the following warning for the missing case:
[warn] missing combination PremiumAccount
[warn] def printAccountDetails(account: Account): Unit = account match {
Another advantage of using the finite algebraic data type is that it provides hints to the Scala compiler to check whether the functions are handling all possible values of algebraic data types. There are two ways you can get rid of the warning: provide the case for the PremiumAccount or make the Account type nonsealed. The downside of removing the sealed keyword is that anybody can extend Account trait and create a new account type. In that case, how can you write functions that handle all possible account types like printAccountDetails? I’m fond of finite (closed) algebraic types and always prefer to use them because I can get a lot of mileage from Scala at compilation time.
One of the biggest benefits is writing total functions. A total function is one that knows how to handle all the values of an algebraic data type and always produces a result. That means you know at compile time that the function will work for all inputs. You’ve been using ADT types in this book for a while now without knowing it. A couple of well-known examples of ADT in Scala are scala.Either and scala.Option.
5.6. Why does functional programming matter?
You’ve explored quite a bit of theory and seen many examples of functional programming in this chapter. Functional programming, as I’ve mentioned, is different from imperative programming. It’s another way of thinking about programming. Why bother to learn this new technique? What will this buy you?
First, it’s good to learn a new programming paradigm because it makes you a better programmer (see section 1.1.4). But this reason alone isn’t good enough—what other benefits does functional programming provide? The popular answer is concurrency and multicore programming. Functional programming helps you write concurrent applications more effectively and easily. Enterprise software developers have to deal with complex business problems and large-scale software development, and although concurrency is an important part of it, it’s not enough to convince all developers. In the rest of the section I make a case for why functional programming matters and how it can help you better handle complexity.
John Hughes, a renowned computer scientist, in his excellent paper on why functional programming matters[12] describes how functional programming helps in handling complexity. In fact, the content and the title of this section were influenced by this paper.
12 John Hughes, “Why Functional Programming Matters,” 1990, http://mng.bz/8KxU.
Take the example of Unix pipes. Unix pipes are analogous to a pipeline where processes are chained together (by their input/output streams) to form a pipeline. For example, the following command retrieves the size of the file identified by the URL www.manning.com/raychaudhuri/:
curl -s "http://www.manning.com/raychaudhuri/" | wc –c
Here I combine the curl process to get data from the server and the wc process to count the bytes I get back from the server. The | is the Unix pipe command, which indicates the output from one process is to be “piped” as input to the next one. I’m pretty sure the authors of curl and wc would have never thought that someone would combine these processes to perform an action. In fact, you can almost take any number of Unix processes and combine them to create new commands. This is one of the most useful and powerful ideas of the Unix-like OSs. What’s the design philosophy behind all these Unix processes?[13] All Unix processes follow two simple rules:
13 Eric S. Raymond, The Art of Unix Programming, Addison-Wesley, 2008, www.catb.org/esr/writings/taoup/.
- Write programs that do one thing and do it well.
- Write programs to work together.
So what do you gain by following these simple rules? The answer is composability. Unix processes show us the power of composability. Unix processes are like LEGO blocks. You can pick them in any order, combine them to create new processes, name these processes, build new processes on top of them, and so on. How does all of this map to functional programming? A Unix pipe is like a functional programming language. If you think of each process as a function, a Unix pipe lets you compose these functions using | notation; in Scala it’s functional composition. Similarly, let’s say the following set of functions is available to you in Scala:
def even: Int => Boolean = _ % 2 == 0
def not: Boolean => Boolean = !_
def filter[A](criteria: A => Boolean)(col: Traversable[A])=
col.filter(criteria)
def map[A, B](f: A => B)(col: Traversable[A]) = col.map(f)
These functions are like Unix processes in that each one does exactly one thing. The even function returns true if the given element is an even integer value. The not function toggles the input Boolean parameter. The filter function, on the other hand, takes a Traversable type collection (super trait for all traversable collection types in Scala) and additional criteria function to return a collection with all the elements that match the criteria. The map function traverses the collection and applies the given function f. Now, suppose you have a problem where you have to find all the even numbers in a given collection and double them. With the functions at your disposal, you can easily build the solution by composing them into a multistep process. First build a filter that knows how to find even elements and a function that can double a value:
def evenFilter = filter(even) _ def double: Int => Int = _ * 2
In the case of evenFilter I’m using function currying to create a specific version of the filter that knows how to filter even numbers. To compose the two functions together, Scala provides a method called andThen, available to all function types except those with zero arguments. This andThen method behaves similarly to Unix pipes—it combines two functions in sequence and creates one function. Because all Scala functions get compiled to a scala.Function trait, you’ll use this compose method to join two functions. To filter out odd elements and double them, create the following function:
def doubleAllEven = evenFilter andThen map(double)
Here evenFilter creates a collection of even elements, and the map function invokes the double function for each element in the collection. Job done. But what if you have to double all the odd numbers? You have all the ingredients you need, just compose them slightly differently:
def odd: Int => Boolean = not compose even def oddFilter = filter(odd) _ def doubleAllOdd = oddFilter andThen map(double)
Here for the odd function I use another combinatory method defined for function types, called compose. The only difference between andThen and compose is that the order of evaluation for compose is right to left. odd will find all the even elements and negate them.
The example in hand is naïve and simple, but one point is clear: composability allows you to build solutions from smaller building blocks, which is important because that’s how you solve complex problems. When you design a solution for a large, complex problem, you break the problem into smaller problems and further break them down into even smaller problems until you get to a point where comprehension is easy. Solving these individual pieces and then gluing them together to build the final piece is a centuries-old technique.
This breaking down of problems into smaller digestible pieces happens across all the layers of software development. Functional composability lets you build these mathematical microworlds in your application. In these microworlds you can be certain about things because they’re all made of pure functions, and you can easily build them using function composition. The good news is that you can implement most of the application complexity in these microworlds, and functional composability gives you a clear, well-defined path to break the problem into smaller functions and compose them later.
In today’s enterprises, delivering software is not enough. You have to deliver as fast as possible. And therein lies the benefits of abstraction and composability. You as a developer can save time by composing smaller functions without reinventing and duplicating implementations.
Another benefit of this pure functional world is debugging. You no longer have to worry about the sequence of events that happened before the problem occurred because there’s no side effect. You also don’t have to worry about the sequence in which the functions are executed because the behavior of the function is only driven by the set of input parameters. It’s much easier to find defects in the functional programming world than in the imperative programming world. To make all this possible, follow the Unix design philosophy:
- Write pure functions that do one thing and do it well.
- Write functions that can compose with other functions.
The first rule is the Single Responsibility Principle. The second rule is a by-product of following the first rule. Keeping functions small and pure automatically helps you compose them together with other functions, as you saw in the previous example. One way to keep functions small is to have them only take one parameter (although the reality is you’re going to have functions that take multiple parameters and do a combination of things).
The second rule is to write functions while keeping function currying in mind, or use partial functions. When declaring functions, make sure you order your parameters from most specific to most generic. It will help others to use functions in more places and to replace the generic parameters—or even better, have functions that take only a single parameter.
As an object functional language, Scala offers the benefits of both object-oriented and functional programming. Functional programming gives you the additional benefit of composition that makes the core and more complex parts of your application easier to write and maintain.
So what about those functions with side effects? Are they hopeless in terms of composition? No. In the next section I show how you can build abstractions around them so that they can participate in composition.
5.7. Building higher abstractions with monads
If you come from an OOP background you’ve probably encountered design patterns. In this section I describe a functional programming design pattern called monads. The problem with monads is the mysticism that comes along with them. The general misconceptions about monads are that they’re hard to understand and that you need a good mathematical background to fully appreciate them. It’s true that monads originated from tenets of category theory,[14] a branch of mathematics that formalizes abstract mathematical concepts into collections and arrows. But they provide a nice abstraction layer (like design patterns) to help structure your code.
14 “Category Theory,” http://en.wikipedia.org/wiki/Category_theory.
Many implementations of monads exist, and each solves a specific kind of problem. You’ve already used monads, in fact—the two common ones so far are List and Option. The List monad abstracts out the computation that might return 0, 1, or more possible results. The Option monad abstracts out the computation that may not return anything (Some or None). Monads are usually considered an advanced functional programming concept, but I feel strongly enough about them to put them in this book because they have enough practical benefits that you as an application developer should know them. The two most important benefits are
1. Monads let you compose functions that don’t compose well, such as functions that have side effects.
2. Monads let you order computation within functional programming so that you can model sequences of actions.
Both of these are critical and powerful properties to be aware of when designing applications using functional programming techniques. First I’ll explore the second benefit because it’s commonly used even if you’re building smaller mathematical microworlds without side effects. In the later part of this section I show you how to compose side-effecting functions in functional programming style.
5.7.1. Managing state using monads
When I introduced functional programming I mentioned that it doesn’t care about the sequencing of functions or operations, because functions are pure. Let’s challenge that with another retail pricing example. This application needs to calculate a price for a product by following a sequence of steps:
1. Find the base price of the product.
2. Apply a state code-specific discount to the base price.
3. Apply a product-specific discount to the result of the previous step.
4. Apply tax to the result of the previous step to get the final price.
This pattern should be common in enterprise software. It’s clear that you have to maintain the price generated by each action and pass it to the next action in the sequence. How will you do that? The imperative answer is to use a mutable variable shared by each action—bad idea, for all the reasons I’ve mentioned throughout the book. What about implementing all these actions in one function? Yikes! That could result in a large function, because each step could potentially be 10–20 lines of code. A better answer would be to implement each step as a function and pipe the result of the current action to the next action. The following listing shows how the implementation would look.
Listing 5.4. Sequencing methods by passing back the state
I stubbed out the uninteresting parts of the code into a file called Stubs so that it doesn’t clutter the code example. Here’s the implementation with some hardcoded values:
object Stubs {
def findTheBasePrice(productId: String) = 10.0
def findStateSpecificDiscount(productId: String, stateCode: String) = 0.5
def findProductSpecificDiscount(productId: String) = 0.5
def calculateTax(productId: String, price: Double) = 5.0
}
The most interesting feature in listing 5.4 is the calculate price method . It invokes each individual function and wires them together in a sequence by passing the result of one function to the next.
Naming variables with a, b, and c is not a good idea, but it nicely shows how the instance of PriceState is passed around. This solution works and is implemented using a functional programming style, but the API of each individual
function looks ugly. Instead of returning only the price, the applyStateSpecificDiscount, applyProductSpecificDiscount, and applyTax methods now have to return an instance of PriceState. The last line of each apply method in listing 5.4 shows the problem.
The next problem is in the calculatePrice method. It’s easy to get something wrong while managing PriceState on your own, while wiring each individual method. In more complicated problems, this kind of approach becomes messy. Surely a higher abstraction that takes care of this state management would be helpful. Here comes the State monad. It is called a State monad because it threads the changing state across multiple operations transparently. In this case, you’ll implement a State monad so that you don’t have to manage the PriceState across multiple method calls. But you’ll have enough of a generic implementation so that you can use it in other places where you have similar problems.
The Scalaz[15] library provides implementations of lots of monads—consider using them without reinventing the wheel. Here you’ll implement the State monad.
15 “Type Classes and Pure Functional Data Structures for Scala,” http://github.com/scalaz/scalaz.
Before I show you how to implement your State monad, let us change the signature of the findBasePrice, applyStateSpecificDiscount, applyProductSpecific-Discount, and applyTax methods so that the API looks cleaner:
def findBasePrice(ps: PriceState): Double def applyStateSpecificDiscount(ps: PriceState): Double def applyProductSpecificDiscount(ps: PriceState): Double def applyTax(ps: PriceState): Double
All these methods now take an instance of PriceState and return the calculated price. Your job is to implement a State monad so you can sequence these methods or actions to calculate the final price.
The State monad encapsulates a transition function from an initial state to a (newState, value) pair. It could be easily represented as a trait in Scala, as in the following:
trait State[S, +A] {
def apply(s: S): (S, A)
}
The apply method represents that transition function. To implement this trait all you have to do is provide a function that takes S and returns (S,A). You could easily implement that as the following:
object State {
def state[S, A](f: S => (S, A)) = new State[S, A] {
def apply(s: S) = f(s)
}
}
You’ll use this object as a place to keep all the handy methods you need to work with your State monad. While you’re there, add a couple of methods to the State object to make life easier:
object State {
def state[S, A](f: S => (S, A)) = new State[S, A] {
def apply(s: S) = f(s)
}
def init[S]: State[S, S] = state[S, S](s => (s, s))
def modify[S](f: S => S) =
init[S] flatMap (s => state(_ => (f(s), ())))
}
The init method lets you create State monads with a skeleton implementation of a transition function (s => (s, s)). Think of it as a default constructor of the State monad. The modify method is a bit more interesting. It lets you modify the current state inside the monad with a new state and return the given function and value part of the (S, A) pair with Unit. You’ll use this method to implement your solution.
To treat the State trait as a first-class monad you also have to implement map and flatMap methods. Why will be clear once you’re done with it, but for now remember that map and flatMap are critical parts of the monad interface—without them, no function can become a monad in Scala.
Implementing map and flatMap is easy because you know how to create an instance of the State monad. The following listing shows the trait that represents the State monad.
Listing 5.5. StateMonad in Scala
The map method of the State monad helps transform the value inside the State monad. On the other hand, flatMap helps transition from one state to another. If all this feels a little abstract, don’t worry—it will make sense when you use these constructs to implement the solution. Let’s do that right now.
So far you’ve learned that State monads take care of threading the changing state across method calls without your being worried about it. But you still have to invoke individual pricing methods in sequence as specified by the business rules. The best place to sequence a series of method calls is in a for-comprehension. This guarantees that the steps you specify inside them will execute in sequence; it’s also a great way to isolate things that need to be run in a sequence. In this case it will be something like the following:
import StateMonad.State._
def modifyPriceState(f: PriceState => Double) =
modify[PriceState](s => s.copy(price = f(s)))
val stateMonad = for {
_ <- modifyPriceState(findBasePrice)
_ <- modifyPriceState(applyStateSpecificDiscount)
_ <- modifyPriceState(applyProductSpecificDiscount)
_ <- modifyPriceState(applyTax)
} yield ()
Lots of things are going on in this small code example, so let me take it from the top. The modifyPriceState method is a handy method that takes one of the pricing methods and lifts it to a function so that you can invoke the modify method inside the State object.
Each modifyPriceState method creates an instance of a State monad. When you invoke them inside the for-comprehension, you get a State monad back that encapsulates this sequence of method calls and knows how to create a price state with a final price. Note that now stateMonad holds a transition function that’s a composition of all the pricing methods defined inside the for-comprehension. And the benefit of this approach is that the threading of state is almost invisible from the application code and is hidden inside the monad. You can pass around this instance of a State monad, and when the time comes you can calculate the final price by passing the initial state:
val initialPriceState = PriceState(productId, stateCode, 0.0) val finalPriceState = stateMonad.apply(initialPriceState)._1 val finalPrice = finalPriceState.price
How does this work? The magic is in map and flatMap. The for-comprehension is nothing but syntactic sugar for map/flatMap. You’ve used for-comprehensions for List and Option—because they both implement map and flatMap. Chapter 4 looked into this in great detail, and in this section I’ll dissect the previous for-comprehension and show you how it gets translated to the map/flatMap combination.
Note in the previous code example those underscores on the left side of the for-comprehension. They represent the value part of the pair, and you don’t need to worry about them for this example. I’ll show you another example where this value would be used effectively—the following listing shows the complete reimplementation of the retail pricing using StateMonad.
Listing 5.6. Sequencing methods using StateMonad
State monad is a general abstraction layer that allows you to build computations for sequences of actions that require a shared state.
You’ve yet to see the relevance of having the pair of state and value in your State monad implementation. Although it’s true that you don’t always need them, if you have a computation that relies on the current state of the monad, you can use the state and value pair to do your computation. Suppose you need to implement logging for the retail-pricing example and log the result of each step.
To implement logging, you need to expose one more method to the State object, called gets. This method lets you access the current state so you can create the log message and save it as a value inside the monad. Here’s how it’s implemented:
def gets[S,A](f: S => A): State[S, A] = init[S] flatMap (s => state(_ => (s, f(s))))
It’s similar to the modify method but allows you to provide a function that takes S and returns A. The gets method also creates a new instance of State monad with the value returned from the given function f. Now you can sequence the log steps after each pricing action inside the for-comprehension, as shown in the following listing, to log all the steps.
Listing 5.7. Calculating price and logging each step
First you create a logStep method to wrap the gets method to provide a little more readability. Secondly you’ve sequenced the logStep after each state modification so you can track the state changes. Finally you’re combining the log of each step as part of the yield to create a list of log messages. See how easy it is to add behavior that relies on changing state using State monad?
5.7.2. Building blocks for monads
The building blocks for monads in Scala are the flatMap and map combination. If you think of a monad as a container, then flatMap and map are the only two possible ways to get into the value currently stored inside the container. Both flatMap and map take a function as a parameter and create a new instance of a monad by applying the function to allow composability. But in both cases you end up with another instance of a monad. To retrieve the value from the monad, you have to use a different technique. For our example I used the apply method defined inside the StateMonad. For some types of monads, you use pattern matching. For example, scala.Option is a monad, and you use pattern matching to retrieve the value from the Some instance.
The important part is to understand why you need both flatMap and map methods. They seem to have a similar kind of behavior. To clearly understand why both are important, reimplement the calculatePrice method from listing 5.6 without the for-comprehension:
def calculatePrice2(productId: String, stateCode: String): Double = {
def modifyPriceState(f: PriceState => Double) =
modify[PriceState](s => s.copy(price = f(s)))
val stateMonad = modifyPriceState(findBasePrice) flatMap {a =>
modifyPriceState(applyStateSpecificDiscount) flatMap {b =>
modifyPriceState (applyProductSpecificDiscount) flatMap {c =>
modifyPriceState (applyTax) map {d =>() }
}
}
}
val initialPriceState = PriceState(productId, stateCode, 0.0)
val finalPriceState = stateMonad.apply(initialPriceState)._1
val finalPrice = finalPriceState.price
finalPrice
}
Here price state is chained together using flatMap without the syntactic sugar of for-comprehension. As you can see, I used both flatMap and map together. This is exactly how Scala will also translate the for-comprehension from listing 5.6. Now compare the previous code using the following signature of map and flatMap:
def map[B](f: A => B): State[S, B] def flatMap[B](f: A => State[S, B]): State[S, B]
The map method lets you create an instance of State monad, and flatMap lets you flatten the nested state. Without flatMap you end up with a nested instance of State monad because each invocation of modifyPriceState returns back an instance of State monad. Try to change the previous code to use map instead of flatMap to see the difference.
Here’s the recipe for building a monad on your own:
1. Define both flatMap and map for the interface.
2. Decide on a way to get the value of the monad (pattern matching or apply).
3. Conform to the monadic laws.[16]
16 Tony Morris, “Monad Laws using Reductio (Scala)”, June 26, 2008, http://mng.bz/59P5.
Monads are almost everywhere—you’ve been using them without knowing it. One common monad you haven’t seen here is the I/O monad. This one lets you compose functions with side effects. Explore the Scalaz library for its implementation. Now you know how to create monads on your own and identify them if you see them in the wild. Monads are a great way to raise the abstraction level that is composable. You could have invented monads[17] (and maybe you already have).
17 Dan Piponi (sigfpe), “You Could Have Invented Monads! (And Maybe You Already Have.),” August 7, 2006, http://mng.bz/96E6.
5.8. Summary
This chapter explored the functional programming side of Scala. Even though you’ve been using functional programming constructs provided by Scala, for the first time I explained functional programming in detail in this chapter. You looked into the roots of functional programming and into the example of a purely functional program.
Enterprise developers find it hard to not worry about side effects because any interesting program out there somehow has to talk to the outside world. You learned how you could still build pure functional modules and push the side effects as far as possible from the core code, which will help build the confidence in and correctness of your applications. Now no more hours of debugging will be required to isolate the mutable state that’s causing your application to misbehave.
The critical benefit of functional programming is composition, the fundamental property that you apply when you construct large programs. And with the power of type abstractions available in Scala, you can finally build reusable functions and components.
You also learned about a functional programming design pattern called Monad. Monads let you compose in the face of side effects. At first they appear to be complex, but once you start using them you’ll see this pattern in many places, including the standard Scala library. Using Monads you’ve merely scratched the surface of functional programming design patterns and concepts. I highly recommend exploring advanced functional programming concepts. A great place to start is Scala in Depth (www.manning.com/suereth/) by Joshua D. Suereth (Manning, 2012).
Functional programming isn’t restricted to Scala. You can use the concepts you’ve learned here in any programming language. Always remember the key is to create a referentially transparent expression, and if that’s possible in your language then go for it. Functional programming languages should also enable functional composition. In short, one language is more functional than another if it makes composing functions easier.
Chapter 6 explores how you can start taking advantage of the benefits of your Java code bases by integrating them with Scala.