# 4. The Functional Programming Paradigm¶

In this chapter, we study the functional programming paradigm, with examples and projects mostly in Scala.

## 4.1. Solving problems using built-in types and behaviors¶

As do other languages, Scala provides an extensive library of predefined types and (generic) type constructors along with a rich set of behaviors.
Many of these, especially collection types and certain utility types, are *algebraic data types*, discussed below in more detail:

`Seq`

/`List`

http://scala-lang.org/api/current/index.html#scala.collection.immutable.List

https://github.com/lucproglangcourse/misc-explorations-scala/blob/master/lists.sc

note the difference between those and tuples

`Map`

`Option`

/`Either`

`Try`

By using Scala like a scripting language (such as Python or Ruby), one can solve many problems without even defining custom algebraic data types, except perhaps the occasional tuple. The main building blocks in scripting-style Scala are the collection and utility types we just mentioned, along with

important methods

`map`

,`take`

/`drop`

,`filter`

/`withFilter`

,`find`

,`flatMap`

,`sum`

,`foldLeft`

/`foldRight`

,`scanLeft`

,`zip`

,`groupBy`

,`collect`

`for`

comprehensions

Todo

elaborate more on `for`

comprehensions and `flatMap`

### 4.1.1. Examples¶

Loop over all items in a finite collection or iterator using mutable state:

```
final Iterator<String> incoming = ...;
int sum = 0;
int count = 0;
for (final String s: incoming) {
sum += s.length();
count += 1;
}
final float result = (float) sum / count;
```

Immutable equivalent using `foldLeft`

:

```
val (sum, count) = incoming.foldLeft {
(0, 0)
} { case ((sum, count), next) =>
(sum + next.length, count + 1)
}
val result = sum.toFloat / count
```

Unbounded loop until a condition is met:

```
final Scanner input = new Scanner(System.in);
System.out.print("enter next expression: ");
while (input.hasNextLine()) {
final String line = input.nextLine();
processExpr(line)
System.out.print("enter next expression: ");
}
```

Immutable equivalent using `continually`

:

```
Iterator continually {
print("enter next expression: ")
StdIn.readLine()
} takeWhile { line =>
line != null
} foreach { line =>
processExpr(line)
}
```

### 4.1.2. Other important operations on collections¶

When the body of the iteration produces a

*side effect*such as output, we can use`foreach`

instead of`continually`

.If we want to compute a

*result value*, we can use`foldLeft`

instead of`foreach`

.If we want to compute a

*sequence of result values*, one for each original item, we can use`scanLeft`

(examples are available here).If we want to transform a

*collection of result values*by independently applying the same function to each item while preserving the collection’s skeletal structure, we can use`map`

.If we want to do the same as

`map`

but without introducing an additional level of structural nesting even though the function does so, we can use`flatMap`

, which flattens the inner structure into the outer; an example is the splitting of lines to words seen in the subsection on console applications.`flatMap`

is equivalent to`map`

followed by`flatten`

.

The following example illustrates the difference between `map`

and `flatMap`

from an imperative perspective:

```
// map - the result is a nested collection
scala> Seq("hello world what up", "hola mundo", "hallo welt")
res0: Seq[String] = List(hello world what up, hola mundo, hallo welt)
scala> val resultNested = scala.collection.mutable.ArrayBuffer.empty[Array[String]]
resultNested: scala.collection.mutable.ArrayBuffer[Array[String]] = ArrayBuffer()
scala> res0.foreach { line =>
| val words = line.split("\\s+")
| resultNested += words
| }
scala> resultNested
res12: scala.collection.mutable.ArrayBuffer[Array[String]] = ArrayBuffer(Array(hello, world, what, up), Array(hola, mundo), Array(hallo, welt))
// flatMap - the result is a flat collection - this requires nested loops!
scala> val resultFlat = scala.collection.mutable.ArrayBuffer.empty[String]
resultFlat: scala.collection.mutable.ArrayBuffer[String] = ArrayBuffer()
scala> res0.foreach { line =>
| val words = line.split("\\s+")
| words.foreach { word =>
| resultFlat += word
| }
| }
scala> resultFlat
res14: scala.collection.mutable.ArrayBuffer[String] = ArrayBuffer(hello, world, what, up, hola, mundo, hallo, welt)
```

Note also that all of these are methods but look like control structures because of Scala’s syntax, which allows you to omit the dot in certain cases of method selection and to use curly braces instead of round parentheses to delimit your argument list.

### 4.1.3. Dealing with successive failures¶

Trying successive choices until either one succeeds or there is none left and we have to give up.
Nested `try`

-`catch`

statements are often used to achieve this:

```
AuthorizeRequestStrategy authorizeRequest = null;
try {
logger.debug("looking for access token");
...
logger.debug("found access token");
authorizeRequest = (request) -> request.addHttpHeaders(authHeader);
} catch (final FileNotFoundException ex) {
try {
logger.debug("looking for API key in environment");
final String apiKey = sys.env("API_KEY");
logger.debug("found API key");
authorizeRequest = (request) -> request.addQueryStringParameter("key", apiKey);
} catch (final NoSuchElementException ex) {
logger.debug("no authorization information found, exiting");
System.exit(401);
}
}
```

Immutable equivalent using successive `Try`

blocks, flat-chained using `orElse`

:

```
val authorizeRequest = Try {
logger.debug("looking for access token in property file")
...
logger.debug("found access token")
val authHeader = KeyAuthorization -> s"Bearer $accessToken"
(request: WSRequest) => request.addHttpHeaders(authHeader)
} orElse Try {
logger.debug("looking for API key in environment")
val apiKey = sys.env("API_KEY")
logger.debug("found API key")
(request: WSRequest) => request.addQueryStringParameters("key" -> apiKey)
} getOrElse {
logger.debug("no authorization information found, exiting")
sys.exit(401)
}
```

The more familiar one becomes with the various predefined building blocks, the more quickly and productively one can put together at least an initial solution to a problem. Earlier versions of the process tree example illustrates this style, while later versions reflect greater emphasis on code quality, especially testability and avoidance of code duplication.

Todo

`for`

with blocks for embedding stateful steps such as logging

### 4.1.4. Challenges¶

Can we write (efficiently or not)

`length`

,`sum`

,`reverse`

,`filter`

,`find`

,`map`

as a fold, i.e.,`foldLeft`

or`foldRight`

?`foldLeft`

or`foldRight`

as`map`

?!?`reverse`

or`filter`

as a`map`

?

Some hints:

Look carefully at the respective domains and codomains (argument and result types). Can they fit?

Which is more general,

`map`

or`fold`

?

## 4.2. Defining algebraic data types¶

Most structures fall into one of these categories:

nonrecursive/scalars: boolean, finite enumerations (including numeric types), try

sublinear structures: (infinite set of) natural numbers, option

linear structures: lists, maps

nonlinear structures: trees, graphs, many custom domain models

The fundamental building blocks of these *algebraic data types* are
related to those discussed in Defining domain models in imperative and object-oriented languages:

(disjoint) sum: variation

product (tuple, record) of a given arity: aggregation

recursion (at the type level)

type parameters (genericity)

Using these building blocks, we can express the Shape domain model from the examples above as an algebraic data type:

```
Shape = Circle(Int)
| Rectangle(Int, Int)
| Group(Seq(Shape))
| Location(Int, Int, Shape)
```

We can separately define behaviors on Shapes as functions. Here is an example that illustrates this approach:

We identify the following structural and behavioral concerns:

structure

content

traversal

processing

So far, structure and content are combined within the definition of an algebraic data type, while traversal and processing are combined within the definition of a behavior on that algebraic data type.

### 4.2.1. Separation of structural concerns¶

We can, however, achieve a separation between structure and content with the help of *parametric polymorphism*, that is, making the algebraic data type *generic* in terms of the content.
The predefined collections are an example of this separation, as well as the generic org chart example.

## 4.3. Behaviors on algebraic data types¶

The following are additional examples of behaviors on algebraic data types. As expected, for recursive types, the behaviors are typically recursive as well.

In these examples, the traversal and processing concerns identified above remain combined.

### 4.3.1. Separation of behavioral concerns¶

A question that comes to mind is whether they can be separated, similarly to the predefined higher-order methods on collections, such as `foldLeft`

, `foldRight`

, `map`

, etc.
These methods go a step further than the Visitor pattern or our equivalent recursive behaviors:
They handle the *traversal* concern for us and separate it from the *processing* concern, which we handle by providing a suitable argument function.

This question has a two-part answer:
Yes, we can define custom implementations of such higher-order behaviors for our own algebraic data types.
In addition, and this is where it gets really interesting, we can have a single, universal implementation that works for all algebraic data types where the children of any node are either fixed in number or stored in a collection that has a `map`

method.

Another, seemingly esoteric, question is whether we can pull out recursion itself as a functional pattern.
Yes, we can.
In this factorial example,
the `Y`

-combinator handles the *recursion* concern *for behaviors* and separates it from the concern of what should happen in each step of the recursion.

We will soon study the equivalent idea at the type level.

## 4.4. A closer look at predefined behaviors on lists¶

In this section, we take a look “under the hood” of some key predefined behaviors on lists.

In terms of performance, we must keep in mind that lists are head/tail-optimized. In other words, these are basically singly-linked lists, so any behaviors where we access the first node of the list are constant-time, while behaviors involving nodes further down in the list are linear-time. In practice, acceptable performance usually means linear time for behavior where we process the entire list.

In addition, we need to be aware of *space complexity*.
Clearly, we are already using space for the arguments we are about to pass to the behavior and are willing to dedicate space to the result we are getting back, so the focus is on *additional* temporary space on the stack, which we like to keep constant if possible.
(This discussion is closely related to The importance of constant-space complexity, where the assumption is that the arguments and the result are stored *externally*.)

*Tail recursion*, where the very last step in a method or function body is the recursive invocation of the method itself, is an effective technique for achieving constant-space complexity as long the behavior can be expressed in a tail-recursive way.
In some cases, we can rewrite an implementation in a tail-recursive way by introducing an *accumulator* argument, where we essentially build up the result in the accumulator and then return that result once we reach the base case of the recursion.
A tail-recursive implementation can easily be transformed to a `while`

loop by introducing a mutable variable to represent the progress into the list structure.
This reverse example illustrates these concepts and techniques in more detail.

Here are some observations:

`foldLeft`

is usually what we want:*linear-time*and*constant-space*(naturally tail-recursive).`foldRight`

is*linear-time*and*linear-space*(*not*tail-recursive) but goes with the natural head-tail structure of the list.`xs.foldRight(z)(f) == xs.reverse.foldLeft(z)(g)`

where`g`

is`f`

with the arguments switched.

To look at the actual Scala library implementations of these functions, first find desired method in the API documentation, expand, look for *definition classes*, follow the link to the leftmost definition class, then the link to that class’s Scala source, and finally look for the actual method.
For performance reasons, these professional implementations tend to appear more complex than we might expect.
Here are some examples:

For more details on space complexity and tail recursion, please take a look at these references:

## 4.5. Separation of concerns at the type level¶

The overall approach is to separate recursion from structure by formalizing algebraic data types as initial F-algebras.

### 4.5.1. Key concepts¶

We first need to define some key concepts:

(Endo)functor: a type constructor (generic collection) with a

`map`

method that satisfies*identity*and*composition*laws:c.map(identity) == c c.map(g compose f) == c.map(f).map(g)

Some familiar examples of endofunctors are

`Option`

`List`

generic trees such as org chart

The

`Fix`

-combinator handles the*recursion*concern*for structures*and separates it from the nature of the structure itself.Generalized

`fold`

=*catamorphism*(`cata`

) for*breaking down*a data structure to a result value.F-algebra: This is the argument to

`fold`

, which has a functor`F`

and a carrier object, i.e., the result type of the fold.`unfold`

=*anamorphism*for*building up*a data structure from some other value.*F-coalgebra*: This is the argument to`unfold`

(generator), which also has a functor`F`

and a carrier object, i.e., type of seed and generated values wrapped in the functor.*Initial F-algebra*: This is the least fixpoint of our functor`F`

and equivalent to our original recursive type. We obtain this by applying the`Fix`

-combinator to`F`

.We get our original recursive behaviors back by combining

`cata`

and our specific F-algebraic version of the behavior.

Todo

Practical applications

### 4.5.2. Examples¶

It is perhaps best to look at some conventional and F-algebra-based examples side-by-side:

project 2a versus project 2b

Some other examples are available here.

### 4.5.3. What `Fix`

does¶

`Fix[F]`

basically ties the “recursive knot” by applying the functor `F`

to itself.
This forms the *fixpoint* of the functor, allowing all structures built from the functor to have the same type, as opposed to nested types corresponding to the nesting of the structure.

For instance, we can represent the familiar aggregation of an item and an (optional) next node using the functor `F[A] = (Int, Option[A])`

.
This enables us to define linked lists:

```
(1, Some((2, Some((3, None)))))
```

The problem is that the types of these lists are nested:

```
scala> (1, Some((2, Some((3, None)))))
res0: (Int, Some[(Int, Some[(Int, None.type)])]) = (1,Some((2,Some((3,None)))))
```

so that lists of different lengths have different types.

By using a suitable `Fix`

over our functor, they all end up having the *same* type, namely `Fix`

:

```
case class Fix(unFix: (Int, Option[Fix]))
scala> Fix((1, Some(Fix((2, Some(Fix((3, None))))))))
res1: Fix = Fix((1,Some(Fix((2,Some(Fix((3,None))))))))
```

That’s why we usually define such types recursively to begin with.

### 4.5.4. Generalized fold (catamorphism)¶

The next question is what the implementation of the universal fold method for `Fix`

looks like, also known as the *catamorphism*.
Continuing with our `Fix`

over `(Int, Option[A])`

example, we perform recursion over this functor by using `map`

, which preserves the first component and invokes a suitable `map`

on the second component of the pair:

```
case class Fix(unFix: (Int, Option[Fix])) {
def cata[B](f: ((Int, Option[B])) => B): B = f((this.unFix._1, this.unFix._2.map(_.cata(f))))
}
```

Now we can define *algebras* on our functor, such as:

```
def sum(arg: (Int, Option[Int])): Int = arg match {
case (i, None) => i
case (i, Some(s)) => i + s
}
res1.cata(sum) // 6
```

These are very similar to visitors without the responsibility to traverse the structure. That is why they are not recursive. Instead, the catamorphism takes care of the recursion.

For an arbitrary functor `F`

, the code looks like this:

```
case class Fix(unFix: F[Fix]) {
def cata[B](f: F[B] => B): B = f(this.unFix.map(_.cata(f)))
}
```

For an arbitrary *carrier type* `B`

, the argument `f`

of type `F[B] => B`

is an `F`

-algebra.
`Fix[F]`

is the *initial* `F`

-algebra, and the catamorphism `cata`

produces the unique structure-preserving mapping (homomorphism) between `Fix[F]`

and `f`

.

### 4.5.5. Key insights¶

By taking an F-algebraic perspective on recursive algebraic data types, we are able to recognize previously non-obvious structural commonalities among them.

non-generic:

`Nat`

,`Expr`

,`Shape`

, etc.generic:

`List`

,`Tree`

,`OrgChart`

, etc.

It also helps to study these questions:

How are, say,

`Option`

,`List`

, and`Tree`

related?How does

`Option`

relate to`List`

`List`

relate to`Tree`

`Tree`

relate to ?!?…

How do we represent an

*empty*structure?Why aren’t there multiple branches in the definition of

`cata`

above? When does the recursion terminate?Is

`cata`

tail-recursive? Can or should it be?

On the behavioral side, we recognize the great potential for code reuse resulting from common abstractions:

The various Typelevel.scala projects

For more details on F-algebras and datatype-generic programming, please take a look at these references:

Gibbons: origami programming (advanced)

Oliveira & Cook: F-algebras in Java (advanced)

If you want to dig a bit deeper, check out a generalization of `map`

called traverse.
Some of our examples include implementations of `traverse`

.

## 4.6. Other useful abstractions¶

In this subsection, we will discuss a few more useful yet relatively simple abstractions.

### 4.6.1. Monoid¶

A Monoid is a type with an associative binary operation and an identity element. (This is equivalent to a semigroup with an identity element.) Examples include:

integers with addition and zero

integers with multiplication one

lists with append and the empty list

strings with concatenation and the empty string

The *monoid laws* arise from the monoid’s definition: the operation must be associative, and the identity element must be a left and right identity.

Examples of monoids using the Scalaz library are available here

### 4.6.2. Monad¶

A Monad is a type constructor (generic collection) with two operations, `point`

(also called `return`

or `unit`

) and `flatMap`

(also called `bind`

).
Monads are an effective way to represent the *context* of a computation in which the computation is “wrapped”.
The monad abstraction thereby enables one to separate the concerns of the computation itself and its context.
Examples include:

`Option`

and`Try`

: potential failure in a computation`List`

: nondeterminism in a computation, meaning that the computation might have multiple results`Id`

: the identity monad, a wrapper that doesn’t actually do anything`Future`

: the computation takes place asynchronously (in the background)

Examples of monads using the Scalaz library are available here.

### 4.6.3. Observations¶

The Scala library includes various structures that are effectively monads, especially those just mentioned. What Scala does not define is a monad abstraction itself.

This is where libraries like Scalaz or Cats come in: They define these abstractions in such a way that we can retrofit existing types or our own types to become instances of the desired abstractions, using the

*Typeclass pattern*, a technique for representing Haskell-style typeclasses.Examples of the Typeclass pattern are the

`Functor`

and`Traverse`

instances in our expressions and shapes examples.A good reference for learning Scalaz, a library that defines these various abstractions, is available here.

## 4.7. References¶

Todo

put chapter-level references here