5. The Functional Programming Paradigm

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

5.1. Core Elements

The functional paradigm is characterized by computation as the evaluation of functions. Functions are first-class citizens, programs are expressed declaratively, and emphasis is placed on immutability and avoidance of side effects.

5.1.1. Expression-Oriented Computation

  • Programs are built from expressions that yield values.

  • No distinction between statements and expressions in purely functional languages.

5.1.2. Immutability

  • Variables are bound once and cannot be reassigned.

  • Encourages referential transparency: expressions can be replaced with their values without changing program meaning.

5.1.3. First-Class and Higher-Order Functions

  • Functions as first-class values: can be passed as arguments, returned as results, and stored in data structures.

  • Higher-order functions: functions that take other functions as parameters or return them.

  • Lambdas: functions can be created on-the-fly and capture their lexical environment (closures).

5.1.4. Recursion

  • Primary mechanism for repetition.

  • Loops are replaced by recursive definitions.

5.1.5. Pattern Matching

Pattern matching is a central feature of functional programming languages. It provides a concise, declarative way to inspect the shape of a value and simultaneously bind its components to names:

val result: Option[Int] = Some(42)

result match
  case Some(n) => println(s"got $n")
  case None    => println("nothing")

Unlike a sequence of if-else checks, pattern matching is:

  • Exhaustiveness-checked: the compiler warns if you miss a case (for sealed types).

  • Structurally expressive: you match and destructure in one step.

  • Composable: patterns can be nested.

Note

Partial functions and ``collect``

A partial function of type PartialFunction[A, B] is a function that is only defined for some inputs of type A. In Scala, a match expression with fewer cases than possible inputs is, in effect, a partial function.

The collect method on collections applies a partial function and keeps only the results where it is defined:

val mixed: List[Any] = List(1, "hello", 2, "world", 3)

val ints: List[Int] = mixed.collect:
  case n: Int => n
// List(1, 2, 3)

val doubled: List[Int] = mixed.collect:
  case n: Int if n > 1 => n * 2
// List(4, 6)

collect is equivalent to filter followed by map, but expressed as a single partial-function pattern. Using partial functions with collect, orElse, and andThen gives a powerful compositional algebra for data transformation.

5.1.6. Lazy Evaluation

  • Expressions evaluated only when needed (default in Haskell).

  • Can improve modularity and performance.

5.1.7. Other Elements

  • Type inference: deduce function and variable types automatically (e.g., Haskell, Scala).

  • Purity: avoiding side effects; I/O and state modeled explicitly (monads, uniqueness types).

5.1.8. Examples Across Languages

Element

Java

Scala

Haskell

Scheme

First-class function

Function<Integer,Integer> f = x -> x+1;

val f = (x:Int) => x+1

f x = x+1

(define f (lambda (x) (+ x 1)))

Higher-order function

list.stream().map(x -> x+1)

List(1,2,3).map(_+1)

map (+1) [1,2,3]

(map (lambda (x) (+ x 1)) '(1 2 3))

Immutability

final var y = 5;

val y = 5

let y = 5 in ...

(define y 5) (by convention immutable)

Recursion

int fact(int n){ return n==0?1:n*fact(n-1); }

def fact(n:Int):Int = if (n==0) 1 else n*fact(n-1)

fact 0 = 1; fact n = n*fact(n-1)

(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))

Pattern matching

Not built-in

x match { case 0 => 1; case n => n*fact(n-1) }

fact 0 = 1; fact n = n*fact (n-1)

Not built-in (simulate with cond)

Lazy evaluation

Streams (Stream.of(1,2,3))

LazyList.from(1)

Default in Haskell

Not default; can simulate with thunks

Closure

Function<Integer,Integer> f = (x) -> x + y;

val f = (x:Int) => x + y

f = \x -> x + y

(define f (lambda (x) (+ x y)))

5.1.9. Discussion

Functional programming emphasizes declarative expression of computation rather than step-by-step instructions. It enables equational reasoning, parallelization, and safer abstractions by reducing reliance on mutable state.

Modern multiparadigm languages (Scala, Python, Java 8+) integrate functional features, while classic functional languages like Scheme, Haskell, and ML highlight the paradigm in its purest form.

5.2. Solving problems using built-in types and behaviors

In this section, we’ll first return to the scripting style for a bit but with a functional touch, which encourages the use of immutable references and data structures. Arguably, this makes it easier to understand program behavior, especially in the presence of concurrency, defined as more than one activity (task, thread, or process) going on at the same time.

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:

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, a lightweight aggregation of heterogeneous types based on the Cartesian product. The main building blocks in scripting-style Scala are the collection and utility types we just mentioned, along with these behaviors:

  • important methods map, take / drop, filter / withFilter, find, flatMap, sum, foldLeft / foldRight, scanLeft, zip, groupBy, collect

  • for comprehensions

for comprehensions and flatMap

A for comprehension is syntactic sugar that desugars into calls to flatMap, map, withFilter, and foreach. The translation is:

// for comprehension:
for
  x <- xs
  y <- f(x)
  if p(y)
yield g(x, y)

// desugars to:
xs.flatMap(x => f(x).withFilter(y => p(y)).map(y => g(x, y)))

This means for comprehensions work with any type that provides flatMap/map — not just collections, but also Option, Try, Future, and custom effect types. The yield keyword corresponds to map; omitting it corresponds to foreach.

5.2.1. Examples

We recall this example of looping over all items in a finite collection or iterator using mutable state:

final Iterator<String> incoming = ...;
var sum = 0;
var count = 0;

incoming.forEachRemaining(s -> {
  sum += s.length();
  count += 1;
});

final var result = (float) sum / count;

What does this code compute?

In Scala, we can use an 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

As noted previously, you cannot “un-fuse” this loop equivalent because the iterator is stateful and you can iterate through it only once. On the other hand, if incoming is a collection (always finite) instead of an iterator (potentially unbounded), you can use map and sum, a specialized fold, for a terser equivalent:

val sum = incoming.map(s => s.length).sum
val count = incoming.size
val result = sum.toFloat / count

This is equivalent to two consecutive loops, one for map and one for sum.

It is also common to have unbounded loops until a condition is met, e.g., reading lines from standard input until end-of-file (EOF):

final var input = new Scanner(System.in);

System.out.print("enter next expression: ");
while (input.hasNextLine()) {
  final var line = input.nextLine();
  processExpr(line)
  System.out.print("enter next expression: ");
}

In Scala, we can use an immutable equivalent using Iterator with continually and takeWhile:

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

5.2.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 section 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> res0.map(s => s.split("\\s+"))
val res1: Seq[Array[String]] = List(Array(hello, world, what, up), Array(hola, mundo), Array(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
res2: 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> res0.flatMap(s => s.split("\\s+"))
val res3: Seq[String] = List(hello, world, what, up, hola, mundo, hallo, welt)

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
res4: 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.

5.2.3. Collection methods with a meaningful product type

Using a product type (case class) as the element type makes collection method examples more realistic and pedagogically compelling. Consider a Person domain model:

case class Person(name: String, age: Int, city: String)

val people = List(
  Person("Alice", 30, "Chicago"),
  Person("Bob",   25, "Chicago"),
  Person("Carol", 35, "New York"),
  Person("Dave",  28, "Chicago"),
  Person("Eve",   22, "New York"),
)

Projection — extract a single field (analogous to SQL SELECT):

val names: List[String] = people.map(_.name)
// List(Alice, Bob, Carol, Dave, Eve)

Selection / filtering — keep only records matching a predicate (analogous to SQL WHERE):

val chicagoans: List[Person] = people.filter(_.city == "Chicago")
// List(Person(Alice,30,Chicago), Person(Bob,25,Chicago), Person(Dave,28,Chicago))

Aggregation — compute a summary value over a collection (analogous to SQL aggregate functions):

val totalAge: Int    = people.map(_.age).sum               // 140
val averageAge: Double = totalAge.toDouble / people.size   // 28.0
val oldest: Person   = people.maxBy(_.age)                 // Person(Carol,35,New York)

Grouping — partition records by a key (analogous to SQL GROUP BY):

val byCity: Map[String, List[Person]] = people.groupBy(_.city)
// Map(Chicago -> List(Alice, Bob, Dave), New York -> List(Carol, Eve))

val avgAgeByCity: Map[String, Double] =
  byCity.map: (city, ps) =>
    city -> ps.map(_.age).sum.toDouble / ps.size
// Map(Chicago -> 27.67, New York -> 28.5)

These operations compose cleanly: filter followed by map is selection then projection; groupBy followed by map is grouping then aggregation—familiar ideas from relational databases, expressed as functional pipeline steps. Note also the connection to the scalaworkshop tutorial for further exercises.

5.2.4. foldLeft vs. scanLeft: accumulating vs. recording each step

Both foldLeft and scanLeft traverse a collection from left to right, combining each element with an accumulator. The key difference is:

  • foldLeft returns only the final accumulated value.

  • scanLeft returns a collection of all intermediate accumulated values, including the initial one.

val nums = List(1, 2, 3, 4, 5)

// foldLeft: total sum — returns a single Int
val total: Int = nums.foldLeft(0)(_ + _)
// 15

// scanLeft: running totals — returns List[Int] with one more element than the input
val running: List[Int] = nums.scanLeft(0)(_ + _)
// List(0, 1, 3, 6, 10, 15)

The imperative equivalent of scanLeft is a loop that records the accumulator at each step:

val running = scala.collection.mutable.ArrayBuffer(0)
var acc = 0
for n <- nums do
  acc += n
  running += acc
// ArrayBuffer(0, 1, 3, 6, 10, 15)

scanLeft is useful whenever you need a history of accumulated values, such as computing a running balance, cumulative word counts, or prefix sums for range queries.

5.2.5. Reification: making concepts first-class values

Note

Definition (Reification)

Reification is the process of making an abstract concept concrete and explicit by representing it as a first-class value in the programming language. Something is reified when it can be stored in a variable, passed to a function, returned from a function, and manipulated like any other value.

Reification is a powerful idea that appears throughout programming language design. One of the clearest examples is the treatment of failure and exceptions:

  • In imperative Java, an exception is thrown and caught via control flow (throw / try-catch). The exception is not a value—it cannot be stored in a variable or passed around as data.

  • In functional Scala, the Try[A] type reifies the possibility of failure as a first-class value: a computation that either succeeds with a value of type A (Success(value)) or fails with a Throwable (Failure(exception)).

// Without reification: control-flow-based
val result: Int =
  try Integer.parseInt(input)
  catch case _: NumberFormatException => 0

// With reification: failure as a value
import scala.util.{ Try, Success, Failure }
val result: Try[Int] = Try(Integer.parseInt(input))
result match
  case Success(n)  => println(s"parsed: $n")
  case Failure(ex) => println(s"error: ${ex.getMessage}")

Because Try[A] is a value, we can:

  • Store it in a collection, return it from a method, or pass it to a higher-order function.

  • Chain computations with map, flatMap, recover, and orElse (see “Dealing with successive failures” below).

  • Reason about it equationally, just like any other data.

The same principle applies to other effect types:

  • Option[A] reifies the possibility that a value may be absent.

  • Either[E, A] reifies the choice between two outcomes (often an error and a success).

  • Future[A] reifies the possibility that a computation will complete asynchronously.

Reification is a recurring theme as programming languages gain expressive power: things that were formerly implicit (side effects, partiality, asynchrony) become explicit values that can be composed and reasoned about.

5.2.6. 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 var 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.

5.2.7. Using for comprehensions with stateful steps

for comprehensions are syntactic sugar over flatMap / map / foreach, making sequences of transformations readable. They also work nicely when you want to embed stateful side-effects (like logging) inside an otherwise functional pipeline.

For example, suppose we want to attempt two ways to obtain a configuration value, logging each attempt, and only fail if both options are exhausted:

val result: Option[String] =
  for
    _      <- Some(logger.debug("trying primary source"))
    value  <- primarySource.get("key")
    _      <- Some(logger.debug(s"found value: $value"))
  yield value

The _  <- Some(...) idiom embeds a side-effect (here, logging) as a step inside the for comprehension: wrapping the effectful call in Some(...) gives it the correct type for the generator, while binding to _ discards the unit result.

Similarly, for comprehensions over Try allow you to sequence fallible steps cleanly:

import scala.util.Try

val result: Try[Int] =
  for
    raw    <- Try(System.getenv("PORT"))
    parsed <- Try(raw.toInt)
  yield parsed

5.2.8. 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?

5.2.9. Fibonacci and Sieve of Eratosthenes as functional examples

These two classic algorithms illustrate the progression from imperative to functional style and the power of lazy, corecursive streams.

Fibonacci numbers

The imperative version uses a simple loop with mutable state:

def fibImperative(k: Int): BigInt =
  var (m, n) = (BigInt(0), BigInt(1))
  for _ <- 0 until k do
    val tmp = m
    m = n
    n = tmp + n
  m

A naive recursive version is elegant but exponential in time:

def fibNaive(k: Int): BigInt =
  if k <= 0 then 0
  else if k == 1 then 1
  else fibNaive(k - 1) + fibNaive(k - 2)

A tail-recursive (accumulator) version is efficient but does not memoize:

@scala.annotation.tailrec
def fib(k: Int, i: Int = 0, m: BigInt = 0, n: BigInt = 1): BigInt =
  if i >= k then m else fib(k, i + 1, n, m + n)

As a corecursive LazyList (the stream approach), the sequence defines itself in terms of its own tail—this generates all Fibonacci numbers on demand:

def fibFrom(a: BigInt, b: BigInt): LazyList[BigInt] = a #:: fibFrom(b, a + b)
val fibs: LazyList[BigInt] = fibFrom(0, 1)

fibs.take(10).toList  // List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

Using LazyList.iterate (an anamorphism — building a structure from a seed):

val fibs: LazyList[BigInt] =
  LazyList.iterate((BigInt(0), BigInt(1)))((m, n) => (n, m + n)).map(_._1)

Similarly, Seq.unfold is the equivalent of LazyList.iterate for building finite sequences and is also an anamorphism:

val firstTenFibs: Seq[BigInt] =
  Seq.unfold((BigInt(0), BigInt(1))): (m, n) =>
    Some((m, (n, m + n)))
  .take(10)

Sieve of Eratosthenes

The classic sieve can be expressed as a corecursive stream. This Iterator-based version produces an infinite stream of primes:

def era(ns: Iterator[Int]): (Int, Iterator[Int]) =
  val p = ns.next()
  (p, ns.filter(_ % p != 0))

val primes: Iterator[Int] =
  Iterator.iterate((0, Iterator.from(2)))((_, ns) => era(ns))
    .drop(1)
    .map(_._1)

primes.take(10).toList  // List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)

Note

Both Fibonacci and the Sieve are examples of corecursion (also called anamorphism or unfold): instead of consuming a structure by recursing down to a base case (catamorphism / fold), they produce a potentially infinite structure by repeatedly applying a step function to a seed. LazyList.iterate and Seq.unfold are the canonical ways to express this pattern in Scala.

5.2.10. Modularity and dependency injection in the functional style

In the functional programming paradigm, first-class functions, i.e., the ability to pass functions as argument values to other functions, methods, and constructors, provides an alternative modular composition mechanism to the object-oriented ones discussed previously.

The iterators example illustrates functional modularity in its functional/modular package.

5.3. 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 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.

5.3.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.

5.4. 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.

5.4.1. Behaviors based on recursive thinking

To understand recursive thinking, let us explore the familiar shapes example. We’ll start with a suitable algebraic type definition and some sample instances:

enum Shape:
  case Rectangle(width: Int, height: Int)
  // ...
  case Location(x: Int, y: Int, shape: Shape)
  case Group(shapes: Shape*)

val r = Rectangle(20, 40)
val q = Rectangle(20, 40)
val p = Rectangle(20, 30)

val g = Group(r, Group(q, p), Location(10, 15, r))

Let’s now try to implement a countGroup behavior. This is incomplete but should compile; ??? is a convenient placeholder for “not yet implemented” (NYI).

def countGroup(s: Shape): Int = s match
  case Rectangle(w, h) => 0
  case Location(x, y, c) => ???
  case Group(shapes*) => ???

As expected, countGroup returns 0 for rectangles but would raise a NYI exception for group or location nodes.

Now we need to apply recursive thinking:

  • For location, the child might have group nodes.

  • For group, the current node is a group node, plus the children might have group nodes.

Accordingly:

def countGroup(s: Shape): Int = s match
  case Rectangle(w, h) => 0
  case Location(x, y, c) => countGroup(c)
  case Group(shapes*) =>
    var sum = 1
    for c <- shapes do
      sum += countGroup(c)
    sum

Now countGroup(g) returns 2 as expected, though this is a Java-style, imperative implementation. Equivalently, we can use the foreach method instead of the so-called for comprehension:

case Group(shapes*) =>
  var sum = 1
  shapes.foreach: c =>
    sum += countGroup(c)
  sum

Now…drum roll…we have an opportunity to convert this code into functional, applicative, immutable style:

case Group(shapes*) =>
  1 + shapes.map(c => countGroup(c)).sum

where map transforms each item in a collection with the result of applying the given function to the item and sum adds all the items in a collection.

Some points to think about:

  • Which design pattern describes the function we pass to the map method?

  • How would you compare these three implementations in terms of whatever functional and/or nonfunctional criteria you can think of?

5.4.2. 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.

5.5. 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:

Note

The Scala standard library source is available at https://github.com/scala/scala3 (Scala 3) and https://github.com/scala/scala (Scala 2). Collection operations like foreach, foldLeft, map, and foldRight are defined in the scala.collection package; the Scala 3 collection API documentation is the most up-to-date reference.

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

5.6. Separation of concerns at the type level

Note

This section is aimed primarily at graduate students, but advanced undergraduates are encouraged to work through it as well.

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

5.6.1. Key concepts

We first need to define some key concepts:

Note

Definition (Endofunctor)

An (endo)functor is a type constructor (generic collection) with a map method satisfying the 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, and generic trees such as the org chart example.

Note

Definition (F-algebra and catamorphism)

An F-algebra is a pair (carrier, algebra) where carrier is a type and algebra :: F[carrier] => carrier maps the functor F applied to the carrier into the carrier. A catamorphism (cata, generalized fold) folds an F-algebraic structure down to a result value of type carrier.

Note

Definition (F-coalgebra and anamorphism)

An F-coalgebra is a pair (carrier, coalgebra) where coalgebra :: carrier => F[carrier] generates the next layer of the structure from a seed value. An anamorphism (unfold) builds up a data structure from a seed using an F-coalgebra.

  • The Fix-combinator handles the recursion concern for structures and separates it from the nature of the structure itself.

  • Initial F-algebra: the least fixpoint of the functor F, equivalent to our original recursive type, obtained 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.

5.6.2. Practical applications

F-algebras are used in practice wherever a program needs to separate the shape of a recursive data structure from the logic that processes it:

  • Error-accumulating validation (Cats Validated): instead of failing fast on the first error (as Either does), an F-algebra-based approach accumulates all validation errors using a semigroup.

  • Recursive data processing with the Droste library: the Droste library for Scala provides generic cata, ana, hylo, and para operators over any fixpoint type, enabling concise, reusable recursion schemes.

  • Compiler IR transformations: the tree-rewriting passes in production compilers (e.g., optimisation, CPS conversion) are naturally expressed as catamorphisms over the abstract syntax tree functor.

5.6.3. Examples

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

  • expressions-scala versus expressions-algebraic-scala

  • shapes-oo-scala versus expressions-algebraic-scala: the conventional recursive-ADT approach (shapes-oo) and the F-algebraic approach (expressions-algebraic) placed side by side. In the F-algebraic version, the recursive knot is untied by separating the functor ShapeF from its fixpoint Fix[ShapeF], so that behaviours (evaluation, printing) can be expressed as non-recursive F-algebras.

Some other examples are available here.

5.6.4. 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.

5.6.5. 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.

5.6.6. 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:

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

If you want to dig a bit deeper, check out a generalization of map called traverse. Some of our examples include implementations of traverse.

5.7. Other useful abstractions

Note

This section is aimed primarily at graduate students, but advanced undergraduates are encouraged to work through it as well.

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

5.7.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.

The Cats library provides a Monoid typeclass along with instances for common types:

import cats.Monoid
import cats.syntax.semigroup.*   // enables |+| operator

// Monoid[Int] uses addition; empty = 0
Monoid[Int].combine(3, 4)              // 7
Monoid[Int].empty                      // 0
Monoid[Int].combineAll(List(1, 2, 3))  // 6

// Monoid[String] uses concatenation; empty = ""
Monoid[String].combine("hello", " world")  // "hello world"

// |+| is the infix alias for combine
"foo" |+| "bar"          // "foobar"
List(1, 2) |+| List(3)  // List(1, 2, 3)

// Any type with a Monoid can be folded for free
def sum[A: Monoid](xs: List[A]): A = xs.foldLeft(Monoid[A].empty)(_ |+| _)
sum(List("a", "b", "c"))  // "abc"
sum(List(1, 2, 3))        // 6

The [A: Monoid] context bound in sum above is the typeclass pattern: the function works for any type A as long as a Monoid[A] instance is available.

5.7.2. Monad

A Monad is a type constructor (generic container) with two operations:

  • pure (also called point, return, or unit): lifts a plain value into the context — e.g., Some(x), List(x).

  • flatMap (also called bind): sequences a context-aware computation — i.e., applies a function that itself returns a wrapped value.

Monads represent the context in which a computation runs, allowing the concern of context management to be separated from the computation itself. The wrapper types introduced earlier in this chapter are all monads:

Type

Context

What flatMap does

Option[A]

Possible absence of a value

Short-circuits to None if any step is absent

Try[A]

Possible failure with an exception

Short-circuits to Failure if any step throws

Either[E, A]

Possible failure with an error value

Short-circuits to Left if any step fails

List[A]

Nondeterminism (multiple possible results)

Applies the function to every element and concatenates results

Future[A]

Asynchronous (background) computation

Sequences the next step to run after this one completes

Id[A]

No context (identity)

Equivalent to plain function application

The Scala standard library does not define a unified Monad abstraction — it simply provides flatMap and map on each type individually. Cats provides the abstraction explicitly, allowing generic code to work with any monad:

import cats.Monad
import cats.syntax.flatMap.*   // enables >>= / flatMap syntax
import cats.syntax.functor.*   // enables map syntax

// Option as a Monad
val m = Monad[Option]
m.pure(42)                                   // Some(42)
m.flatMap(Some(3))(x => Some(x * 2))         // Some(6)
m.flatMap(None: Option[Int])(_ => Some(0))   // None

// for-comprehension desugars to flatMap + map (works for any Monad)
def addIfPresent[F[_]: Monad](fa: F[Int], fb: F[Int]): F[Int] =
  for
    a <- fa
    b <- fb
  yield a + b

addIfPresent(Option(3), Option(4))      // Some(7)
addIfPresent(Option(3), None)           // None
addIfPresent(List(1, 2), List(10, 20))  // List(11, 21, 12, 22)  — all combinations (nondeterminism)

The [F[_]: Monad] context bound makes addIfPresent work for any monad — Option, List, Either, Future, or a custom type — without changing the implementation.

5.7.3. Observations

  • The Scala standard library provides flatMap and map on many types, making for comprehensions work uniformly. What it does not define is a common Monad abstraction across those types.

  • The Cats library fills this gap using the typeclass pattern: it defines Monad[F[_]] as a typeclass and provides instances for Option, List, Either, Future, Id, and many others, as well as tools for defining your own instances.

  • Examples of the typeclass pattern we have already seen in this chapter are the Functor and Traverse instances in the expressions and shapes examples.

  • The Cats documentation is the primary reference for these abstractions.

5.8. References

  • Jeremy Gibbons, Origami Programming (2003): PDF — introduces folds and unfolds as general-purpose programming patterns.

  • Luca Cardelli and Peter Wegner, On Understanding Types, Data Abstraction, and Polymorphism (1985): PDF — foundational paper on parametric and subtype polymorphism.

  • Typelevel Cats documentation — practical guide to functors, monads, and related abstractions in Scala.

  • Droste recursion-schemes library — Scala implementation of catamorphisms and anamorphisms.

  • Bartosz Milewski, Category Theory for Programmers (2018): online — accessible introduction to the categorical foundations of functional programming.

  • Scala 3 official documentation — authoritative reference for all language features used in this chapter.

  • Runar Bjarnason and Paul Chiusano, Functional Programming in Scala (Manning, 2014) — deep treatment of pure FP patterns including monads and monad transformers.

  • Learn You a Haskell for Great Good! — approachable introduction to Haskell and typeclasses that illuminates Scala’s abstractions.