Preface

Some twenty years ago I started my first job in the UK. This job involved a commute by train, giving me about an hour a day to read without distraction. Around about the same time I first heard about Structure and Interpretation of Computer Programs, referred to as the “wizard book” and spoken of in reverential terms. It sounded like the just the thing for a recent graduate looking to become a better developer. I purchased a copy and spent the journey reading it, doing most of the exercises in my head. Structure and Interpretation of Computer Programs was already an old book at this time, and it’s programming style was archaic. However it’s core concepts were timeless and it’s fair to say it absolutely blew my mind, putting me on a path I’m still on today.

Another notable stop on this path occured some ten years ago when Dave and I started writing Scala with Cats. In Scala with Cats we attempted to explain the core type classes found in the Cats library, and their use in building software. I’m proud of the book we wrote together, but time and experience showed that type classes are only a small piece of the puzzle of building software in a functional programming style. We needed a much wider scope if we were to show people how to effectively build software with all the tools that functional programming provides. Still, writing a book is a lot of work, and we were busy with other projects, so Scala with Cats remained largely untouched for many years.

Around 2020 I got the itch to return to Scala with Cats. My initial plan was simply to update the book for Scala 3. Dave was busy with other projects so I decided to go alone. As the writing got underway I realized I really wanted to cover the additional topics I thought were missing. If Scala with Cats was a good book, I wanted to aim to write a great book; one that would contain almost everything I had learned about building software. The title Scala with Cats no longer fit the content, and hence I adopted a new name for what is largely a new book. The result, Functional Programming Strategies in Scala with Cats, is what you are reading now. I hope you find it useful, and I hope that just maybe some young developer will find this book inspiring the same way I found Structure and Interpretation of Computer Programs inspiring all those years ago.

Preface from Scala with Cats

The aims of this book are two-fold: to introduce monads, functors, and other functional programming patterns as a way to structure program design, and to explain how these concepts are implemented in Cats.

Monads, and related concepts, are the functional programming equivalent of object-oriented design patterns—architectural building blocks that turn up over and over again in code. They differ from object-oriented patterns in two main ways:

• they are formally, and thus precisely, defined; and
• they are extremely (extremely) general.

This generality means they can be difficult to understand. Everyone finds abstraction difficult. However, it is generality that allows concepts like monads to be applied in such a wide variety of situations.

In this book we aim to show the concepts in a number of different ways, to help you build a mental model of how they work and where they are appropriate. We have extended case studies, a simple graphical notation, many smaller examples, and of course the mathematical definitions. Between them we hope you’ll find something that works for you.

Ok, let’s get started!

Versions

This book is written for Scala 3.3.3 and Cats 2.10.0. Here is a minimal build.sbt containing the relevant dependencies and settings¹:

scalaVersion := "3.3.3"

libraryDependencies +=
  "org.typelevel" %% "cats-core" % "2.10.0"

scalacOptions ++= Seq(
  "-Xfatal-warnings"
)

Template Projects

For convenience, we have created a Giter8 template to get you started. To clone the template type the following:

$ sbt new scalawithcats/cats-seed.g8

This will generate a sandbox project with Cats as a dependency. See the generated README.md for instructions on how to run the sample code and/or start an interactive Scala console.

The cats-seed template is very minimal. If you’d prefer a more batteries-included starting point, check out Typelevel’s sbt-catalysts template:

$ sbt new typelevel/sbt-catalysts.g8

This will generate a project with a suite of library dependencies and compiler plugins, together with templates for unit tests and documentation. See the project pages for catalysts and sbt-catalysts for more information.

Conventions Used in This Book

This book contains a lot of technical information and program code. We use the following typographical conventions to reduce ambiguity and highlight important concepts:

Typographical Conventions

New terms and phrases are introduced in italics. After their initial introduction they are written in normal roman font.

Terms from program code, filenames, and file contents, are written in monospace font. Note that we do not distinguish between singular and plural forms. For example, we might write String or Strings to refer to java.lang.String.

References to external resources are written as hyperlinks. References to API documentation are written using a combination of hyperlinks and monospace font, for example: scala.Option.

Source Code

Source code blocks are written as follows. Syntax is highlighted appropriately where applicable:

object MyApp extends App {
  println("Hello world!") // Print a fine message to the user!
}

Most code passes through mdoc to ensure it compiles. mdoc uses the Scala console behind the scenes, so we sometimes show console-style output as comments:

"Hello Cats!".toUpperCase
// res0: String = "HELLO CATS!"

Callout Boxes

We use two types of callout box to highlight particular content:

License

This work is licensed under CC BY-SA 4.0. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/4.0/

Portions of this work are based on Scala with Cats by Dave Pereira-Gurnell and Noel Welsh, which is licensed under CC BY-SA 3.0.

1 Functional Programming Strategies

This is a book on strategies for creating code in a functional programming (FP) style, seen through a Scala lens. If you understand most of the mechanics of Scala, but feel there is something missing in your understanding of how to use the language effectively, this book is for you. If you don’t know so much Scala, but are prepared to learn it as part of learning about functional programming, this book is also for you. It covers the usual functional programming abstractions like monads and monoids, but more than that it tries to teach you how to think like a functional programmer. It’s a book as much about process as it is about the code that results from process, and in particular it focuses on what I can metacognitive programming strategies.

I would guess most programmers would struggle to describe the process they use to write code. Some might mention “test driven development” and perhaps “pair programming”, but I wouldn’t expect much more from the general programming population. Both the above techniques come from eXtreme Programming, which dates to the late 90s, and you would hope our field had added new knowledge in that time. But it’s not really the fault of the developers—most of them haven’t been taught any explicit process. Our industry certainly likes to talk about process, in the form of agile, kanban boards, and so on, and in recent times a tremendous effort has spent on expanding those who are taught programming. However the actual programming—the bit that produces the code that is the whole point of the endeavour—is still largely treated as magic. It doesn’t have to be that way.

Functional programmers love fancy words for simple ideas, so it’s no surprise I’m drawn to metacognitive programming strategies. Let’s unpack that phrase to see what it means. Metacognition means thinking about thinking. A lot of research has shown the benefits of metacognition in learning, and that it is an important part of developing expertise. Metacognition is not just one thing—it’s not sufficient to just tell someone to think about their thinking. Rather we should expect metacognition to be a collection of different strategies, some of which are general and some of which are domain specific. From this we get the idea of metacognitive programming strategies—explicitly naming and describing different thinking strategies that proficient programmers use.

I believe metacognitive programming strategies are useful for both beginners and experts. For beginners we can make programming a more systematic and repeatable process. Producing code no longer requires magic in the majority of cases, but rather the application of some well defined steps. For experts, the benefit is exactly the same. At least that is my experience (and I believe I’ve been programming long enough to call myself an expert.) By having an explicit process I can run it exactly the same way every day, which makes my code simpler to write and read, and saves my brain cycles for more important problems. In some ways this is an attempt to bring to programming the benefit that process and standardization has brought to manufacturing, particularly the “Toyota Way”. In Toyota’s process individuals are expected to think about how their work is done and how it can be improved. This is, in effect, metacognition for assembly lines. This is only possible if the actual work itself does not require their full attention. The dramatic improvements in productivity and quality in car manufacturing that Toyota pioneered speak to the effectiveness of this approach. Software development is more varied than car manufacturing but we should still expect some benefit, particularly given the primitive state of our current industry.

The question then becomes: what metacognitive strategies can programmers use? I believe that functional programming is particularly well suited to answer this question. A major theme in functional programming research is finding and naming useful code structures. Once we have discovered a useful abstraction we can get the programmer to ask themselves “would this abstraction solve this problem?” This is essentially what the design patterns community did, also back in the nineties, but there is an important difference. The academic FP community strongly values formal models, which means that the building blocks of FP have a precision that design patterns lack. However there is more to process than categorizing the output. There is also the actual process of how the code comes to be. Code doesn’t usually spring fully formed from our keyboard, and in the iterative refinement of code we also find structure. Here the academic FP community has less to say, but there is a strong folklore of techniques such as “type driven development”

Over the last ten or so years of programming and teaching programming I’ve collected a wide range of strategies. Some come from others (for example, How to Design Programs and its many offshoots remain very influential for me) and some I’ve found myself. Ultimately I don’t think anything here is new; rather my contribution is in collecting and presenting these strategies as one coherent whole.

1.1 Three Levels for Thinking About Code

Let’s start thinking about thinking about programming, with a model that describes three different levels that we can use to think about code. The levels, from highest to lowest, are paradigm, theory, and craft. Each level provides guidance for the ones below.

The paradigm level refers to the programming paradigm, such as object-oriented or functional programming. You’re probably familiar with these terms, but what exactly is a programming paradigm? To me, the core of a programming paradigm is a set of principles that define, usually somewhat loosely, the properties of good code. A paradigm is also, implicitly, a claim that code that follows these principles will be better than code that does not. For functional programming I believe these principles are composition and reasoning. I’ll explain these shortly. Object-oriented programmers might point to, say, the SOLID principles as guiding their coding decisions.

The importance of the paradigm is that it provides criteria for choosing between different implementation strategies. There are many possible solutions for any programming problem, and we can use the principles in the paradigm to decide which approach to take. For example, if we’re a functional programmer we can consider how easily we can reason about a particular implementation, or how composable it is. Without the paradigm we have no basis for making a choice.

The theory level translates the broad principles of the paradigm to specific well defined techniques that apply to many languages within the paradigm. We are still, however, at a level above the code. Design patterns are an example in the object-oriented world. Algebraic data types are an example in functional programming. Most languages that are in the functional programming paradigm, such as Haskell and O’Caml, support algebraic data types, as do many languages that straddle multiple paradigms, such as Rust, Scala, and Swift.

The theory level is where we find most of our programming strategies.

At the craft level we get to actual code, and the language specific nuance that goes into it. An example in Scala is the implementation of algebraic data types in terms of sealed trait and final case class in Scala 2, or enum in Scala 3. There are many concerns at this level that are important for writing idiomatic code, such as placing constructors on companion objects in Scala, that are not relevant at the higher levels.

In the next section I’ll describe the functional programming paradigm. The remainder of this book is primarily concerned with theory and craft. The theory is language agnostic but the craft is firmly in the world of Scala. Before we move onto the functional programming paradigm are two points I want to emphasize:

1. Paradigms are social constructs. They change over time. Object-oriented programming as practiced todays differs from the style originally used in Simula and Smalltalk, and functional programming todays is very different from the original LISP code.

2. The three level organization is just a tool for thought. In real world is more complicated.

1.2 Functional Programming

This is a book about the techniques and practices of functional programming (FP). This naturally leads to the question: what is FP and what does it mean to write code in a functional style? It’s common to view functional programming as a collection of language features, such as first class functions, or to define it as a programming style using immutable data and pure functions. (Pure functions always return the same output given the same input.) This was my view when I started down the FP route, but I now believe the true goals of FP are enabling local reasoning and composition. Language features and programming style are in service of these goals. Let me attempt to explain the meaning and value of local reasoning and composition.

1.2.1 What Functional Programming Is

I believe that functional programming is a hypothesis about software quality: that it is easier to write and maintain software that can be understood before it is run, and is built of small reusable components. The first property is known as local reasoning, and the second as composition. Let’s address each in turn.

Local reasoning means we can understand pieces of code in isolation. When we see the expression 1 + 1 we know what it means regardless of the weather, the database, or the current status of our Kubernetes cluster. None of these external events can change it. This is a trivial and slightly silly example, but it illustrates the point. A goal of functional programming is to extend this ability across our code base.

It can help to understand local reasoning by looking at what it is not. Shared mutable state is out because relying on shared state means that other code can change what our code does without our knowledge. It means no global mutable configuration, as found in many web frameworks and graphics libraries for example, as any random code can change that configuration. Metaprogramming has to be carefully controlled. No monkey patching, for example, as again it allows other code to change our code in non-obvious ways. As we can see, adapting code to enable local reasoning can mean quite some sweeping changes. However if we work in a language that embraces functional programming this style of programming is the default.

Composition means building big things out of smaller things. Numbers are compositional. We can take any number and add one, giving us a new number. Lego is also compositional. We compose Lego by sticking it together. In the particular sense we’re using composition we also require the original elements we combine don’t change in any way when they are composed. When we create by 2 by adding 1 and 1 we get a new result that doesn’t change what 1 means.

We can find compositional ways to model common programming tasks once we start looking for them. React components are one example familiar to many front-end developers: a component can consist of many components. HTTP routes can be modelled in a compositional way. A route is a function from an HTTP request to either a handler function or a value indicating the route did not match. We can combine routes as a logical or: try this route or, if it doesn’t match, try this other route. Processing pipelines are another example that often use sequential composition: perform this pipeline stage and then this other pipeline stage.

1.2.1.1 Types

Types are not strictly part of functional programming but statically typed FP is the most popular form of FP and sufficiently important to warrant a mention. Types help compilers generate efficient code but types in FP are as much for the programmer as they are the compiler. Types express properties of programs, and the type checker automatically ensures that these properties hold. They can tell us, for example, what a function accepts and what it returns, or that a value is optional. We can also use types to express our beliefs about a program and the type checker will tell us if those beliefs are correct. For example, we can use types to tell the compiler we do not expect an error at a particular point in our code and the type checker will let us know if this is the case. In this way types are another tool for reasoning about code.

Type systems push programs towards particular designs, as to work effectively with the type checker requires designing code in a way the type checker can understand. As modern type systems come to more languages they naturally tend to shift programmers in those languages towards a FP style of coding.

1.2.2 What Functional Programming Isn’t

In my view functional programming is not about immutability, or keeping to “the substitution model of evaluation”, and so on. These are tools in service of the goals of enabling local reasoning and composition, but they are not the goals themselves. Code that is immutable always allows local reasoning, for example, but it is not necessary to avoid mutation to still have local reasoning. Here is an example of summing a collection of numbers.

def sum(numbers: List[Int]): Int = {
  var total = 0
  numbers.foreach(x => total = total + x)
  total
}

In the implementation we mutate total. This is ok though! We cannot tell from the outside that this is done, and therefore all users of sum can still use local reasoning. Inside sum we have to be careful when we reason about total but this block of code is small enough that it shouldn’t cause any problems.

In this case we can reason about our code despite the mutation, but the Scala compiler can determine that this is ok. Scala allows mutation but it’s up to us to use it appropriately. A more expressive type system, perhaps with features like Rust’s, would be able to tell that sum doesn’t allow mutation to be observed by other parts of the system². Another approach, which is the one taken by Haskell, is to disallow all mutation and thus guarantee it cannot cause problems.

Mutation also interferes with composition. For example, if a value relies on internal state then composing it may produce unexpected results. Consider Scala’s Iterator. It maintains internal state that is used to generate the next value. If we have two Iterators we might want to combine them into one Iterator that yields values from the two inputs. The zip method does this.

This works if we pass two distinct generators to zip.

val it = Iterator(1, 2, 3, 4)

val it2 = Iterator(1, 2, 3, 4)

it.zip(it2).next()
// res0: Tuple2[Int, Int] = (1, 1)

However if we pass the same generator twice we get a surprising result.

val it3 = Iterator(1, 2, 3, 4)

it3.zip(it3).next()
// res1: Tuple2[Int, Int] = (1, 2)

The usual functional programming solution is to avoid mutable state but we can envisage other possibilities. For example, an effect tracking system would allow us to avoid combining two generators that use the same memory region. These systems are still research projects, however.

So in my opinion immutability (and purity, referential transparency, and no doubt more fancy words that I have forgotten) have become associated with functional programming because they guarantee local reasoning and composition, and until recently we didn’t have the language tools to automatically distinguish safe uses of mutation from those that cause problems. Restricting ourselves to immutability is the easiest way to ensure the desirable properties of functional programming, but as languages evolve this might come to be regarded as a historical artifact.

1.2.3 Why It Matters

I have described local reasoning and composition but have not discussed their benefits. Why are they are desirable? The answer is that they make efficient use of knowledge. Let me expand on this.

We care about local reasoning because it allows our ability to understand code to scale with the size of the code base. We can understand module A and module B in isolation, and our understanding does not change when we bring them together in the same program. By definition if both A and B allow local reasoning there is no way that B (or any other code) can change our understanding of A, and vice versa. If we don’t have local reasoning every new line of code can force us to revisit the rest of the code base to understand what has changed. This means it becomes exponentially harder to understand code as it grows in size as the number of interactions (and hence possible behaviours) grows exponentially. We can say that local reasoning is compositional. Our understanding of module A calling module B is just our understanding of A, our understanding of B, and whatever calls A makes to B.

We introduced numbers and Lego as examples of composition. They have an interesting property in common: the operations that we can use to combine them (for example, addition, subtraction, and so on for numbers; for Lego the operation is “sticking bricks together”) give us back the same kind of thing. A number multiplied by a number is a number. Two bits of Lego stuck together is still Lego. This property is called closure: when you combine things you end up with the same kind of thing. Closure means you can apply the combining operations (sometimes called combinators) an arbitrary number of times. No matter how many times you add one to a number you still have a number and can still add or subtract or multiply or…you get the idea. If we understand module A, and the combinators that A provides are closed, we can build very complex structures using A without having to learn new concepts! This is also one reason functional programmers tend to like abstractions such a monads (beyond liking fancy words): they allow us to use one mental model in lots of different contexts.

In a sense local reasoning and composition are two sides of the same coin. Local reasoning is compositional; composition allows local reasoning. Both make code easier to understand.

1.2.4 The Evidence for Functional Programming

I’ve made arguments in favour of functional programming and I admit I am biased—I do believe it is a better way to develop code than imperative programming. However, is there any evidence to back up my claim? There has not been much research on the effectiveness of functional programming, but there has been a reasonable amount done on static typing. I feel static typing, particularly using modern type systems, serves as a good proxy for functional programming so let’s look at the evidence there.

In the corners of the Internet I frequent the common refrain is that static typing has neglible effect on productivity. I decided to look into this and was surprised that the majority of the results I found support the claim that static typing increases productivity. For example, the literature review in this dissertation (section 2.3, p16–19) shows a majority of results in favour of static typing, in particular the most recent studies. However the majority of these studies are very small and use relatively inexperienced developers—which is noted in the review by Dan Luu that I linked. My belief is that functional programming comes into its own on larger systems. Furthermore, programming languages, like all tools, require proficiency to use effectively. I’m not convinced very junior developers have sufficient skill to demonstrate a significant difference between languages.

To me the most useful evidence of the effectiveness of functional programming is that industry is adopting functional programming en masse. Consider, say, the widespread and growing adoption of Typescript and React. If we are to argue that FP as embodied by Typescript or React has no value we are also arguing that the thousands of Javascript developers who have switched to using them are deluded. At some point this argument becomes untenable.

This doesn’t mean we’ll all be using Haskell in five years. More likely we’ll see something like the shift to object-oriented programming of the nineties: Smalltalk was the paradigmatic example of OO, but it was more familiar languages like C++ and Java that brought OO to the mainstream. In the case of FP this probably means languages like Scala, Swift, Kotlin, or Rust, and mainstream languages like Javascript and Java continuing to adopt more FP features.

1.2.5 Final Words

I’ve given my opinion on functional programming—that the real goals are local reasoning and composition, and programming practices like immutability are in service of these. Other people may disagree with this definition, and that’s ok. Words are defined by the community that uses them, and meanings change over time.

Functional programming emphasises formal reasoning, and there are some implications that I want to briefly touch on.

Firstly, I find that FP is most valuable in the large. For a small system it is possible to keep all the details in our head. It’s when a program becomes too large for anyone to understand all of it that local reasoning really shows its value. This is not to say that FP should not be used for small projects, but rather that if you are, say, switching from an imperative style of programming you shouldn’t expect to see the benefit when working on toy projects.

The formal models that underlie functional programming allow systematic construction of code. This is in some ways the reverse of reasoning: instead of taking code and deriving properties, we start from some properties and derive code. This sounds very academic but is in fact very practical, and how I develop most of my code.

Finally, reasoning is not the only way to understand code. It’s valuable to appreciate the limitations of reasoning, other methods for gaining understanding, and using a variety of strategies depending on the situation.

In this first part of the book we’re building the foundational strategies on which the rest of the book will build and elaborate. In Chapter 2 we look at algebraic data types, which are our main way of modelling data. We turn to codata in Chapter 3, which is the opposite, or dual, or algebraic data. Type classes are the focus on Chapter 4, while fundamentals of interpreters are discussed in Chapter 5. These four strategies all describe code artifacts. For example, we can label part of code as an algebraic data type or a type class. We’ll also see strategies that help us write code but don’t necessarily end up directly reflected in it, such as following the types.

2 Algebraic Data Types

This chapter has our first example of a programming strategy: algebraic data types. Any data we can describe using logical ands and logical ors is an algebraic data type. Once we recognize an algebraic data type we get three things for free:

• the Scala representation of the data;
• a structural recursion skeleton to transform the algebraic data type into any other type; and
• a structural corecursion skeleton to construct the algebraic data type from any other type.

The key point is this: from an implementation independent representation of data we can automatically derive most of the interesting implementation specific parts of working with that data.

We’ll start with some examples of data, from which we’ll extract the common structure that motivates algebraic data types. We will then look at their representation in Scala 2 and Scala 3. Next we’ll turn to structural recursion for transforming algebraic data types, followed by structural corecursion for constructing them. We’ll finish by looking at the algebra of algebraic data types, which is interesting but not essential.

2.1 Building Algebraic Data Types

Let’s start with some examples of data from a few different domains. These are simplified description but they are all representative of real applications.

A user in a discussion forum will typically have a screen name, an email address, and a password. Users also typically have a specific role: normal user, moderator, or administrator, for example. From this we get the following data:

• a user is a screen name, an email address, a password, and a role; and
• a role is normal, moderator, or administrator.

A product in an e-commerce store might have a stock keeping unit (a unique identifier for each variant of a product), a name, a description, a price, and a discount.

In two-dimensional vector graphics it’s typical to represent shapes as a path, which is a sequence of actions of a virtual pen. The possible actions are usually straight lines, Bezier curves, or movement that doesn’t result in visible output. A straight line has an end point (the starting point is implicit), a Bezier curve has two control points and an end point, and a move has an end point.

What is common between all the examples above is that the individual elements—the atoms, if you like—are connected by either a logical and or a logical or. For example, a user is a screen name and an email address and a password and a role. A 2D action is a straight line or a Bezier curve or a move. This is the core of algebraic data types: an algebraic data type is data that is combined using logical ands or logical ors. Conversely, whenever we can describe data in terms of logical ands and logical ors we have an algebraic data type.

2.1.1 Sums and Products

Being functional programmers we can’t let a simple concept go without attaching some fancy jargon:

• a product type means a logical and; and
• a sum type means a logical or.

So algebraic data types consist of sum and product types.

2.1.2 Closed Worlds

Algebraic data types are closed worlds, which means they cannot be extended after they have been defined. In practical terms this means we have to modify the source code where we define the algebraic data type if we want to add or remove elements.

The closed world property is important because it gives us guarantees we would not otherwise have. In particular, it allows the compiler to check that we handle all possible cases when we use an algebraic data type. This is known as exhaustivity checking. This is an example of how functional programming prioritizes reasoning about code—in this case automated reasoning by the compiler—over other properties such as extensibility. We’ll learn more about exhaustivity checking soon.

2.2 Algebraic Data Types in Scala

Now we know what algebraic data types are, we will turn to their representation in Scala. The important point here is that the translation to Scala is entirely determined by the structure of the data; no thinking is required! This means the work is in finding the structure of the data that best represents the problem at hand. Work out the structure of the data and the code directly follows from it.

As algebraic data types are defined in terms of logical ands and logical ors, to represent algebraic data types in Scala we must know how to represent these two concepts. Scala 3 simplifies the representation of algebraic data types compared to Scala 2, so we’ll look at each language version separately.

I’m assuming that you’re familiar with the language features we use to represent algebraic data types in Scala, so I won’t be going over them.

2.2.1 Algebraic Data Types in Scala 3

In Scala 3 a logical and (a product type) is represented by a final case class. If we define a product type A is B and C, the representation in Scala 3 is

final case class A(b: B, c: C)

Not everyone makes their case classes final, but they should. A non-final case class can still be extended by a class, which breaks the closed world criteria for algebraic data types.

A logical or (a sum type) is represented by an enum. For the sum type A is B or C, the Scala 3 representation is

enum A {
  case B
  case C
}

There are a few wrinkles to be aware of.

If we have a sum of products, such as:

• A is B or C; and
• B is D and E; and
• C is F and G

the representation is

enum A {
  case B(d: D, e: E)
  case C(f: F, g: G)
}

In other words we don’t write final case class inside an enum. You also can’t nest enum inside enum. Nested logical ors can be rewritten into a single logical or containing only logical ands (known as disjunctive normal form) so this is not a limitation in practice. However the Scala 2 representation is still available in Scala 3 should you want more expressivity.

2.2.2 Algebraic Data Types in Scala 2

A logical and (product type) has the same representation in Scala 2 as in Scala 3. If we define a product type A is B and C, the representation in Scala 2 is

final case class A(b: B, c: C)

A logical or (a sum type) is represented by a sealed abstract class. For the sum type A is a B or C the Scala 2 representation is

sealed abstract class A
final case class B() extends A
final case class C() extends A

Scala 2 has several little tricks to defining algebraic data types.

Firstly, instead of using a sealed abstract class you can use a sealed trait. There isn’t much practical difference between the two. When teaching beginners I’ll often use sealed trait to avoid having to introduce abstract class. I believe sealed abstract class has slightly better performance and Java interoperability, but I haven’t tested this. I also think sealed abstract class is closer, semantically, to the meaning of a sum type.

For extra style points we can extend Product with Serializable from sealed abstract class. Compare the reported types below with and without this little addition.

Let’s first see the code without extending Product and Serializable.

sealed abstract class A
final case class B() extends A
final case class C() extends A

val list = List(B(), C())
// list: List[A extends Product with Serializable] = List(B(), C())

Notice how the type of list includes Product and Serializable.

Now we have extending Product and Serializable.

sealed abstract class A extends Product with Serializable
final case class B() extends A
final case class C() extends A

val list = List(B(), C())
// list: List[A] = List(B(), C())

Much easier to read!

You’ll only see this in Scala 2. Scala 3 has the concept of transparent traits, which aren’t reported in inferred types, so you’ll see the same output in Scala 3 no matter whether you add Product and Serializable or not.

Finally, if a logical and holds no data we can use a case object instead of a case class. For example, if we’re defining some type A that holds no data we can just write

case object A

There is no need to mark the case object as final, as objects cannot be extended.

2.2.3 Examples

Let’s make the discussion above more concrete with some examples.

2.2.3.1 Role and User

In the discussion forum example, we said a role is normal, moderator, or administrator. This is a logical or, so we can directly translate it to Scala using the appropriate pattern. In Scala 3 we write

enum Role {
  case Normal
  case Moderator
  case Administrator
}

In Scala 2 we write

sealed abstract class Role extends Product with Serializable
case object Normal extends Role
case object Moderator extends Role
case object Administrator extends Role

The cases within a role don’t hold any data, so we used a case object in the Scala 2 code.

We defined a user as a screen name, an email address, a password, and a role. In both Scala 3 and Scala 2 this becomes

final case class User(
  screenName: String,
  emailAddress: String,
  password: String,
  role: Role
)

I’ve used String to represent most of the data within a User, but in real code we might want to define distinct types for each field.

2.2.3.2 Paths

We defined a path as a sequence of actions of a virtual pen. The possible actions are straight lines, Bezier curves, or movement that doesn’t result in visible output. A straight line has an end point (the starting point is implicit), a Bezier curve has two control points and an end point, and a move has an end point.

This has a straightforward translation to Scala. We can represent paths as the following in both Scala 3 and Scala 2.

final case class Path(actions: Seq[Action])

An action is a logical or, so we have different representations in Scala 3 and Scala 2. In Scala 3 we’d write

enum Action {
  case Line(end: Point)
  case Curve(cp1: Point, cp2: Point, end: Point)
  case Move(end: Point)
}

where Point is a suitable representation of a two-dimensional point.

In Scala 2 we have to go with the more verbose

sealed abstract class Action extends Product with Serializable 
final case class Line(end: Point) extends Action
final case class Curve(cp1: Point, cp2: Point, end: Point)
  extends Action
final case class Move(end: Point) extends Action

2.2.4 Representing ADTs in Scala 3

We’ve seen that the Scala 3 representation of algebraic data types, using enum, is more compact than the Scala 2 representation. However the Scala 2 representation is still available. Should you ever use the Scala 2 representation in Scala 3? There are a few cases where you may want to:

• Scala 3’s doesn’t currently support nested enums (enums within enums). This may change in the future, but right now it can be more convenient to use the Scala 2 representation to express this without having to convert to disjunctive normal form.

• Scala 2’s representation can express things that are almost, but not quite, algebraic data types. For example, if you define a method on an enum you must be able to define it for all the members of the enum. Sometimes you want a case of an enum to have methods that are only defined for that case. To implement this you’ll need to use the Scala 2 representation instead.

Exercise: Tree

To gain a bit of practice defining algebraic data types, code the following description in Scala (your choice of version, or do both.)

A Tree with elements of type A is:

• a Leaf with a value of type A; or
• a Node with a left and right child, which are both Trees with elements of type A.

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
}

sealed abstract class Tree[A] extends Product with Serializable
final case class Leaf[A](value: A) extends Tree[A]
final case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A]

2.3 Structural Recursion

Structural recursion is our second programming strategy. Algebraic data types tell us how to create data given a certain structure. Structural recursion tells us how to transform an algebraic data types into any other type. Given an algebraic data type, the transformation can be implemented using structural recursion.

As with algebraic data types, there is distinction between the concept of structural recursion and the implementation in Scala. This is more obvious because there are two ways to implement structural recursion in Scala: via pattern matching or via dynamic dispatch. We’ll look at each in turn.

2.3.1 Pattern Matching

I’m assuming you’re familiar with pattern matching in Scala, so I’ll only talk about how to implement structural recursion using pattern matching. Remember there are two kinds of algebraic data types: sum types (logical ors) and product types (logical ands). We have corresponding rules for structural recursion implemented using pattern matching:

1. For each branch in a sum type we have a distinct case in the pattern match; and
2. Each case corresponds to a product type with the pattern written in the usual way.

Let’s see this in code, using an example ADT that includes both sum and product types:

• A is B or C; and
• B is D and E; and
• C is F and G

which we represent (in Scala 3) as

enum A {
  case B(d: D, e: E)
  case C(f: F, g: G)
}

Following the rules above means a structural recursion would look like

anA match {
  case B(d, e) => ???
  case C(f, g) => ???
}

The ??? bits are problem specific, and we cannot give a general solution for them. However we’ll soon see strategies to help create them.

2.3.2 The Recursion in Structural Recursion

At this point you might be wondering where the recursion in structural recursion comes from. This is an additional rule for recursion: whenever the data is recursive the method is recursive in the same place.

Let’s see this in action for a real data type.

We can define a list with elements of type A as:

• the empty list; or
• a pair containing an A and a tail, which is a list of A.

This is exactly the definition of List in the standard library. Notice it’s an algebraic data type as it consists of sums and products. It is also recursive: in the pair case the tail is itself a list.

We can directly translate this to code, using the strategy for algebraic data types we saw previously. In Scala 3 we write

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
}

Let’s implement map for MyList. We start with the method skeleton specifying just the name and types.

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    ???
}

Our first step is to recognize that map can be written using a structural recursion. MyList is an algebraic data type, map is transforming this algebraic data type, and therefore structural recursion is applicable. We now apply the structural recursion strategy, giving us

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    this match {
      case Empty() => ???
      case Pair(head, tail) => ???
    }
}

I forgot the recursion rule! The data is recursive in the tail of Pair, so map is recursive there as well.

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    this match {
      case Empty() => ???
      case Pair(head, tail) => ??? tail.map(f)
    }
}

I left the ??? to indicate that we haven’t finished with that case.

Now we can move on to the problem specific parts. Here we have three strategies to help us:

1. reasoning independently by case;
2. assuming recursion the is correct; and
3. following the types

The first two are specific to structural recursion, while the final one is a general strategy we can use in many situations. Let’s briefly discuss each and then see how they apply to our example.

The first strategy is relatively simple: when we consider the problem specific code on the right hand side of a pattern matching case, we can ignore the code in any other pattern match cases. So, for example, when considering the case for Empty above we don’t need to worry about the case for Pair, and vice versa.

The next strategy is a little bit more complicated, and has to do with recursion. Remember that the structural recursion strategy tells us where to place any recursive calls. This means we don’t have to think through the recursion. Instead we assume the recursive call will correctly compute what it claims, and only consider how to further process the result of the recursion. The result is guaranteed to be correct so long as we get the non-recursive parts correct.

In the example above we have the recursion tail.map(f). We can assume this correctly computes map on the tail of the list, and we only need to think about what we should do with the remaining data: the head and the result of the recursive call.

It’s this property that allows us to consider cases independently. Recursive calls are the only thing that connect the different cases, and they are given to us by the structural recursion strategy.

Our final strategy is following the types. It can be used in many situations, not just structural recursion, so I consider it a separate strategy. The core idea is to use the information in the types to restrict the possible implementations. We can look at the types of inputs and outputs to help us.

Now let’s use these strategies to finish the implementation of map. We start with

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    this match {
      case Empty() => ???
      case Pair(head, tail) => ??? tail.map(f)
    }
}

Our first strategy is to consider the cases independently. Let’s start with the Empty case. There is no recursive call here, so reasoning about recursion doesn’t come into play. Let’s instead use the types. There is no input here other than the Empty case we have already matched, so we cannot use the input types to further restrict the code. Let’s instead consider the output type. We’re trying to create a MyList[B]. There are only two ways to create a MyList[B]: an Empty or a Pair. To create a Pair we need a head of type B, which we don’t have. So we can only use Empty. This is the only possible code we can write. The types are sufficiently restrictive that we cannot write incorrect code for this case.

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    this match {
      case Empty() => Empty()
      case Pair(head, tail) => ??? tail.map(f)
    }
}

Now let’s move to the Pair case. We can apply both the structural recursion reasoning strategy and following the types. Let’s use each in turn.

The case for Pair is

case Pair(head, tail) => ??? tail.map(f)

Remember we can consider this independently of the other case. We assume the recursion is correct. This means we only need to think about what we should do with the head, and how we should combine this result with tail.map(f). Let’s now follow the types to finish the code. Our goal is to produce a MyList[B]. We already the following available:

• tail.map(f), which has type MyList[B];
• head, with type A;
• f, with type A => B; and
• the constructors Empty and Pair.

We could return just Empty, matching the case we’ve already written. This has the correct type but we might expect it is not the correct answer because it does not use the result of the recursion, head, or f in any way.

We could return just tail.map(f). This has the correct type but we might expect it is not correct because we don’t use head or f in any way.

We can call f on head, producing a value of type B, and then combine this value and the result of the recursive call using Pair to produce a MyList[B]. This is the correct solution.

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    this match {
      case Empty() => Empty()
      case Pair(head, tail) => Pair(f(head), tail.map(f))
    }
}

If you’ve followed this example you’ve hopefully see how we can use the three strategies to systematically find the correct implementation. Notice how we interleaved the recursion strategy and following the types to guide us to a solution for the Pair case. Also note how following the types alone gave us three possible implementations for the Pair case. In this code, and as is usually the case, the solution was the implementation that used all of the available inputs.

2.3.3 Exhaustivity Checking

Remember that algebraic data types are a closed world: they cannot be extended once defined. The Scala compiler can use this to check that we handle all possible cases in a pattern match, so long as we write the pattern match in a way the compiler can work with. This is known as exhaustivity checking.

Here’s a simple example. We start by defining a straight-forward algebraic data type.

// Some of the possible units for lengths in CSS
enum CssLength {
  case Em(value: Double)
  case Rem(value: Double)
  case Pt(value: Double)
}

If we write a pattern match using the structural recursion strategy, the compiler will complain if we’re missing a case.

import CssLength.*

CssLength.Em(2.0) match {
  case Em(value) => value
  case Rem(value) => value
}
// -- [E029] Pattern Match Exhaustivity Warning: ----------------------------------
// 1 |CssLength.Em(2.0) match {
//   |^^^^^^^^^^^^^^^^^
//   |match may not be exhaustive.
//   |
//   |It would fail on pattern case: CssLength.Pt(_)
//   |
//   | longer explanation available when compiling with `-explain`

Exhaustivity checking is incredibly useful. For example, if we add or remove a case from an algebraic data type, the compiler will tell us all the pattern matches that need to be updated.

2.3.4 Dynamic Dispatch

Using dynamic dispatch to implement structural recursion is an implementation technique that may feel more natural to people with a background in object-oriented programming.

The dynamic dispatch approach consists of:

1. defining an abstract method at the root of the algebraic data types; and
2. implementing that abstract method at every leaf of the algebraic data type.

This implementation technique is only available if we use the Scala 2 encoding of algebraic data types.

Let’s see it in the MyList example we just looked at. Our first step is to rewrite the definition of MyList to the Scala 2 style.

sealed abstract class MyList[A] extends Product with Serializable
final case class Empty[A]() extends MyList[A]
final case class Pair[A](head: A, tail: MyList[A]) extends MyList[A]

Next we define an abstract method for map on MyList.

sealed abstract class MyList[A] extends Product with Serializable {
  def map[B](f: A => B): MyList[B]
}
final case class Empty[A]() extends MyList[A]
final case class Pair[A](head: A, tail: MyList[A]) extends MyList[A]

Then we implement map on the concrete subtypes Empty and Pair.

sealed abstract class MyList[A] extends Product with Serializable {
  def map[B](f: A => B): MyList[B]
}
final case class Empty[A]() extends MyList[A] {
  def map[B](f: A => B): MyList[B] = 
    Empty()
}
final case class Pair[A](head: A, tail: MyList[A]) extends MyList[A] {
  def map[B](f: A => B): MyList[B] =
    Pair(f(head), tail.map(f))
}

We can use exactly the same strategies we used in the pattern matching case to create this code. The implementation technique is different but the underlying concept is the same.

Given we have two implementation strategies, which should we use? If we’re using enum in Scala 3 we don’t have a choice; we must use pattern matching. In other situations we can choose between the two. I prefer to use pattern matching when I can, as it puts the entire method definition in one place. However, Scala 2 in particular has problems inferring types in some pattern matches. In these situations we can use dynamic dispatch instead. We’ll learn more about this when we look at generalized algebraic data types.

Exercise: Methods for Tree

In a previous exercise we created a Tree algebraic data type:

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
}

Or, in the Scala 2 encoding:

sealed abstract class Tree[A] extends Product with Serializable
final case class Leaf[A](value: A) extends Tree[A]
final case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A]

Let’s get some practice with structural recursion and write some methods for Tree. Implement

• size, which returns the number of values (Leafs) stored in the Tree;
• contains, which returns true if the Tree contains a given element of type A, and false otherwise; and
• map, which creates a Tree[B] given a function A => B

Use whichever you prefer of pattern matching or dynamic dispatch to implement the methods.

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def size: Int = 
    ???

  def contains(element: A): Boolean =
    ???
    
  def map[B](f: A => B): Tree[B] =
    ???
}

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def size: Int = 
    this match { 
      case Leaf(value)       => ???
      case Node(left, right) => left.size ??? right.size
    }

  def contains(element: A): Boolean =
    this match { 
      case Leaf(value)       => ???
      case Node(left, right) => left.contains(element) ??? right.contains(element)
    }
    
  def map[B](f: A => B): Tree[B] =
    this match { 
      case Leaf(value)       => ???
      case Node(left, right) => left.map(f) ??? right.map(f)
    }
}

def size: Int = 
  this match { 
    case Leaf(value)       => 1
    case Node(left, right) => left.size ??? right.size
  }

def size: Int = 
  this match { 
    case Leaf(value)       => 1
    case Node(left, right) => left.size ??? right.size
  }

def size: Int = 
  this match { 
    case Leaf(value)       => 1
    case Node(left, right) => left.size + right.size
  }

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def size: Int = 
    this match { 
      case Leaf(value)       => 1
      case Node(left, right) => left.size + right.size
    }

  def contains(element: A): Boolean =
    this match { 
      case Leaf(value)       => element == value
      case Node(left, right) => left.contains(element) || right.contains(element)
    }
    
  def map[B](f: A => B): Tree[B] =
    this match { 
      case Leaf(value)       => Leaf(f(value))
      case Node(left, right) => Node(left.map(f), right.map(f))
    }
}

2.3.5 Folds as Structural Recursions

Let’s finish by looking at the fold method as an abstraction over structural recursion. If you did the Tree exercise above, you will have noticed that we wrote the same kind of code again and again. Here are the methods we wrote. Notice the left-hand sides of the pattern matches are all the same, and the right-hand sides are very similar.

def size: Int = 
  this match { 
    case Leaf(value)       => 1
    case Node(left, right) => left.size + right.size
  }

def contains(element: A): Boolean =
  this match { 
    case Leaf(value)       => element == value
    case Node(left, right) => left.contains(element) || right.contains(element)
  }
  
def map[B](f: A => B): Tree[B] =
  this match { 
    case Leaf(value)       => Leaf(f(value))
    case Node(left, right) => Node(left.map(f), right.map(f))
  }

This is the point of structural recursion: to recognize and formalize this similarity. However, as programmers we might want to abstract over this repetition. Can we write a method that captures everything that doesn’t change in a structural recursion, and allows the caller to pass arguments for everything that does change? It turns out we can. For any algebraic data type we can define at least one method, called a fold, that captures all the parts of structural recursion that don’t change and allows the caller to specify all the problem specific parts.

Let’s see how this is done using the example of MyList. Recall the definition of MyList is

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
}

We know the structural recursion skeleton for MyList is

def doSomething[A](list: MyList[A]) =
  list match {
    case Empty()          => ???
    case Pair(head, tail) => ??? doSomething(tail)
  } 

Implementing fold for MyList means defining a method

def fold[A, B](list: MyList[A]): B =
  list match {
    case Empty() => ???
    case Pair(head, tail) => ??? fold(tail)
  }

where B is the type the caller wants to create.

To complete fold we add method parameters for the problem specific (???) parts. In the case for Empty, we need a value of type B (notice that I’m following the types here).

def fold[A, B](list: MyList[A], empty: B): B =
  list match {
    case Empty() => empty
    case Pair(head, tail) => ??? fold(tail, empty)
  }

For the Pair case, we have the head of type A and the recursion producing a value of type B. This means we need a function to combine these two values.

def foldRight[A, B](list: MyList[A], empty: B, f: (A, B) => B): B =
  list match {
    case Empty() => empty
    case Pair(head, tail) => f(head, foldRight(tail, empty, f))
  }

This is foldRight (and I’ve renamed the method to indicate this). You might have noticed there is another valid solution. Both empty and the recursion produce values of type B. If we follow the types we can come up with

def foldLeft[A,B](list: MyList[A], empty: B, f: (A, B) => B): B =
  list match {
    case Empty() => empty
    case Pair(head, tail) => foldLeft(tail, f(head, empty), f)
  }

which is foldLeft, the tail-recursive variant of fold for a list. (We’ll talk about tail-recursion in a later chapter.)

We can follow the same process for any algebraic data type to create its folds. The rules are:

• a fold is a function from the algebraic data type and additional parameters to some generic type that I’ll call B below for simplicity;
• the fold has one additional parameter for each case in a logical or;
• each parameter is a function, with result of type B and parameters that have the same type as the corresponding constructor arguments except recursive values are replaced with B; and
• if the constructor has no arguments (for example, Empty) we can use a value of type B instead of a function with no arguments.

Returning to MyList, it has:

• two cases, and hence two parameters to fold (other than the parameter that is the list itself);
• Empty is a constructor with no arguments and hence we use a parameter of type B; and
• Pair is a constructor with one parameter of type A and one recursive parameter, and hence the corresponding function has type (A, B) => B.

Exercise: Tree Fold

Implement a fold for Tree defined earlier. There are several different ways to traverse a tree (pre-order, post-order, and in-order). Just choose whichever seems easiest.

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def fold[B]: B =
    ???
}

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def fold[B]: B =
    this match {
      case Leaf(value)       => ???
      case Node(left, right) => left.fold ??? right.fold
    }
}

enum Tree[A] {
  case Leaf(value: A => B)
  case Node(left: Tree[A], right: Tree[A])
  
  def fold[B](leaf: A => B): B =
    this match {
      case Leaf(value)       => leaf(value)
      case Node(left, right) => left.fold ??? right.fold
    }
}

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def fold[B](leaf: A => B)(node: (B, B) => B): B =
    this match {
      case Leaf(value)       => leaf(value)
      case Node(left, right) => node(left.fold(leaf)(node), right.fold(leaf)(node))
    }
}

Exercise: Using Fold

Prove to yourself that you can replace structural recursion with calls to fold, by redefining size, contains, and map for Tree using only fold.

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def fold[B](leaf: A => B)(node: (B, B) => B): B =
    this match {
      case Leaf(value)       => leaf(value)
      case Node(left, right) => node(left.fold(leaf)(node), right.fold(leaf)(node))
    }
    
  def size: Int = 
    this.fold(_ => 1)(_ + _)

  def contains(element: A): Boolean =
    this.fold(_ == element)(_ || _)
    
  def map[B](f: A => B): Tree[B] =
    this.fold(v => Leaf(f(v)))((l, r) => Node(l, r))
}

2.4 Structural Corecursion

Structural corecursion is the opposite—more correctly, the dual—of structural recursion. Whereas structural recursion tells us how to take apart an algebraic data type, structural corecursion tells us how to build up, or construct, an algebraic data type. Whereas we can use structural recursion whenever the input of a method or function is an algebraic data type, we can use structural corecursion whenever the output of a method or function is an algebraic data type.

Structural recursion works by considering all the possible inputs (which we usually represent as patterns), and then working out what we do with each input case. Structural corecursion works by considering all the possible outputs, which are the constructors of the algebraic data type, and then working out the conditions under which we’d call each constructor.

Let’s return to the list with elements of type A, defined as:

• the empty list; or
• a pair containing an A and a tail, which is a list of A.

In Scala 3 we write

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
}

We can use structural corecursion if we’re writing a method that produces a MyList. A good example is map:

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    ???
}

The output of this method is a MyList, which is an algebraic data type. Since we need to construct a MyList we can use structural corecursion. The structural corecursion strategy says we write down all the constructors and then consider the conditions that will cause us to call each constructor. So our starting point is to just write down the two constructors, and put in dummy conditions.

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    if ??? then Empty()
    else Pair(???, ???)
}

We can also apply the recursion rule: where the data is recursive so is the method.

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    if ??? then Empty()
    else Pair(???, ???.map(f))
}

To complete the left-hand side we can use the strategies we’ve already seen:

• we can use structural recursion to tell us there are two possible conditions; and
• we can follow the types to align these conditions with the code we have already written.

In short order we arrive at the correct solution

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    this match {
      case Empty() => Empty()
      case Pair(head, tail) => Pair(f(head), tail.map(f))
    }
}

There are a few interesting points here. Firstly, we should acknowledge that map is both a structural recursion and a structural corecursion. This is not always the case. For example, foldLeft and foldRight are not structural corecursions because they are not constrained to only produce an algebraic data type. Secondly, note that when we walked through the process of creating map as a structural recursion we implicitly used the structural corecursion pattern, as part of following the types. We recognised that we were producing a List, that there were two possibilities for producing a List, and then worked out the correct conditions for each case. Formalizing structural corecursion as a separate strategy allows us to be more conscious of where we apply it. Finally, notice how I switched from an if expression to a pattern match expression as we progressed through defining map. This is perfectly fine. Both kinds of expression achieve the same effect. Pattern matching is a little bit safer due to exhaustivity checking. If we wanted to continue using an if we’d have to define a method (for example, isEmpty) that allows us to distinguish an Empty element from a Pair. This method would have to use pattern matching in its implementation, so avoiding pattern matching directly is just pushing it elsewhere.

2.4.1 Unfolds as Structural Corecursion

Just as we could abstract structural recursion as a fold, for any given algebraic data type we can abstract structural corecursion as an unfold. Unfolds are much less commonly used than folds, but they are still a nice tool to have.

Let’s work through the process of deriving unfold, using MyList as our example again.

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
}

The corecursion skeleton is

if ??? then MyList.Empty()
else MyList.Pair(???, recursion(???))

Our starting point is writing the skeleton for unfold. It’s a little bit unusual in that I’ve added a parameter seed. This is the information we use to create an element. We’ll need this, but we cannot derive it from our strategies, so I’ve added it in here as a starting assumption.

def unfold[A, B](seed: A): MyList[B] =
  ???

Now we start using our strategies to fill in the missing pieces. I’m using the corecursion skeleton and I’ve applied the recursion rule immediately in the code below, to save a bit of time in the derivation.

def unfold[A, B](seed: A): MyList[B] =
  if ??? then MyList.Empty()
  else MyList.Pair(???, unfold(seed))

We can abstract the condition using a function from A => Boolean.

def unfold[A, B](seed: A, stop: A => Boolean): MyList[B] =
  if stop(seed) then MyList.Empty()
  else MyList.Pair(???, unfold(seed, stop))

Now we need to handle the case for Pair. We have a value of type A (seed), so to create the head element of Pair we can ask for a function A => B

def unfold[A, B](seed: A, stop: A => Boolean, f: A => B): MyList[B] =
  if stop(seed) then MyList.Empty()
  else MyList.Pair(f(seed), unfold(???, stop, f))

Finally we need to update the current value of seed to the next value. That’s a function A => A.

def unfold[A, B](seed: A, stop: A => Boolean, f: A => B, next: A => A): MyList[B] =
  if stop(seed) then MyList.Empty()
  else MyList.Pair(f(seed), unfold(next(seed), stop, f, next))

At this point we’re done. Let’s see that unfold is useful by declaring some other methods in terms of it. We’re going to declare map, which we’ve already seen is a structural corecursion, using unfold. We will also define fill and iterate, which are methods that construct lists and correspond to the methods with the same names on List in the Scala standard library.

To make this easier to work with I’m going to declare unfold as a method on the MyList companion object. I have made a slight tweak to the definition to make type inference work a bit better. In Scala, types inferred for one method parameter cannot be used for other method parameters in the same parameter list. However, types inferred for one method parameter list can be used in subsequent lists. Separating the function parameters from the seed parameter means that the value inferred for A from seed can be used for inference of the function parameters’ input parameters.

I have also declared some destructor methods, which are methods that take apart an algebraic data type. For MyList these are head, tail, and the predicate isEmpty. We’ll talk more about these a bit later.

Here’s our starting point.

enum MyList[A] {
  case Empty()
  case Pair(_head: A, _tail: MyList[A])

  def isEmpty: Boolean =
    this match {
      case Empty() => true
      case _       => false
    }
    
  def head: A =
    this match {
      case Pair(head, _) => head
    }
    
  def tail: MyList[A] =
    this match {
      case Pair(_, tail) => tail
    }
}
object MyList {
  def unfold[A, B](seed: A)(stop: A => Boolean, f: A => B, next: A => A): MyList[B] =
    if stop(seed) then MyList.Empty()
    else MyList.Pair(f(seed), unfold(next(seed))(stop, f, next))
}

Now let’s define the constructors fill and iterate, and map, in terms of unfold. I think the constructors are a bit simpler, so I’ll do those first.

object MyList {
  def unfold[A, B](seed: A)(stop: A => Boolean, f: A => B, next: A => A): MyList[B] =
    if stop(seed) then MyList.Empty()
    else MyList.Pair(f(seed), unfold(next(seed))(stop, f, next))
    
  def fill[A](n: Int)(elem: => A): MyList[A] =
    ???
    
  def iterate[A](start: A, len: Int)(f: A => A): MyList[A] =
    ???
}

Here I’ve just added the method skeletons, which are taken straight from the List documentation. To implement these methods we can use one of two strategies:

• reasoning about loops in the way we might in an imperative language; or
• reasoning about structural recursion over the natural numbers.

Let’s talk about each in turn.

You might have noticed that the parameters to unfold are almost exactly those you need to create a for-loop in a language like Java. A classic for-loop, of the for(i = 0; i < n; i++) kind, has four components:

1. the initial value of the loop counter;
2. the stopping condition of the loop;
3. the statement that advances the counter; and
4. the body of the loop that uses the counter.

These correspond to the seed, stop, next, and f parameters of unfold respectively.

Loop variants and invariants are the standard way of reasoning about imperative loops. I’m not going to describe them here, as you have probably already learned how to reason about loops (though perhaps not using these terms). Instead I’m going to discuss the second reasoning strategy, which relates writing unfold to something we’ve already discussed: structural recursion.

Our first step is to note that natural numbers (the integers 0 and larger) are conceptually algebraic data types even though the implementation in Scala—using Int—is not. A natural number is either:

• zero; or
• 1 + a natural number.

It’s the simplest possible algebraic data type that is both a sum and a product type.

Once we see this, we can use the reasoning tools for structural recursion for creating the parameters to unfold. Let’s show how this works with fill. The n parameter tells us how many elements there are in the List we’re creating. The elem parameter creates those elements, and is called once for each element. So our starting point is to consider this as a structural recursion over the natural numbers. We can take n as seed, and stop as the function x => x == 0. These are the standard conditions for a structural recursion over the natural numbers. What about next? Well, the definition of natural numbers tells us we should subtract one in the recursive case, so next becomes x => x - 1. We only need f, and that comes from the definition of how fill is supposed to work. We create the value from elem, so f is just _ => elem

object MyList {
  def unfold[A, B](seed: A)(stop: A => Boolean, f: A => B, next: A => A): MyList[B] =
    if stop(seed) then MyList.Empty()
    else MyList.Pair(f(seed), unfold(next(seed))(stop, f, next))
    
  def fill[A](n: Int)(elem: => A): MyList[A] =
    unfold(n)(_ == 0, _ => elem, _ - 1)
    
  def iterate[A](start: A, len: Int)(f: A => A): MyList[A] =
    ???
}

We should check that our implementation works as intended. We can do this by comparing it to List.fill.

List.fill(5)(1)
// res6: List[Int] = List(1, 1, 1, 1, 1)
MyList.fill(5)(1)
// res7: MyList[Int] = MyList(1, 1, 1, 1, 1)

Here’s a slightly more complex example, using a stateful method to create a list of ascending numbers. First we define the state and method that uses it.

var counter = 0
def getAndInc(): Int = {
  val temp = counter
  counter = counter + 1
  temp 
}

Now we can create it to create lists.

List.fill(5)(getAndInc())
// res8: List[Int] = List(0, 1, 2, 3, 4)
counter = 0
MyList.fill(5)(getAndInc())
// res10: MyList[Int] = MyList(0, 1, 2, 3, 4)

Exercise: Iterate

Implement iterate using the same reasoning as we did for fill. This is slightly more complex than fill as we need to keep two bits of information: the value of the counter and the value of type A.

object MyList {
  def unfold[A, B](seed: A)(stop: A => Boolean, f: A => B, next: A => A): MyList[B] =
    if stop(seed) then MyList.Empty()
    else MyList.Pair(f(seed), unfold(next(seed))(stop, f, next))
    
  def fill[A](n: Int)(elem: => A): MyList[A] =
    unfold(n)(_ == 0)(_ => elem, _ - 1)
    
  def iterate[A](start: A, len: Int)(f: A => A): MyList[A] =
    unfold((len, start)){
      (len, _) => len == 0,
      (_, start) => start,
      (len, start) => (len - 1, f(start))
    }
}

List.iterate(0, 5)(x => x - 1)
// res11: List[Int] = List(0, -1, -2, -3, -4)
MyList.iterate(0, 5)(x => x - 1)
// res12: MyList[Int] = MyList(0, -1, -2, -3, -4)

Exercise: Map

Once you’ve completed iterate, try to implement map in terms of unfold. You’ll need to use the destructors to implement it.

def map[B](f: A => B): MyList[B] =
  MyList.unfold(this)(
    _.isEmpty,
    pair => f(pair.head),
    pair => pair.tail
  )

List.iterate(0, 5)(x => x + 1).map(x => x * 2)
// res13: List[Int] = List(0, 2, 4, 6, 8)
MyList.iterate(0, 5)(x => x + 1).map(x => x * 2)
// res14: MyList[Int] = MyList(0, 2, 4, 6, 8)

Now a quick discussion on destructors. The destructors do two things:

1. distinguish the different cases within a sum type; and
2. extract elements from each product type.

So for MyList the minimal set of destructors is isEmpty, which distinguishes Empty from Pair, and head and tail. The extractors are partial functions in the conceptual, not Scala, sense; they are only defined for a particular product type and throw an exception if used on a different case. You may have also noticed that the functions we passed to fill are exactly the destructors for natural numbers.

The destructors are another part of the duality between structural recursion and corecursion. Structural recursion is:

• defined by pattern matching on the constructors; and
• takes apart an algebraic data type into smaller pieces.

Structural corecursion instead is:

• defined by conditions on the input, which may use destructors; and
• build up an algebraic data type from smaller pieces.

One last thing before we leave unfold. If we look at the usual definition of unfold we’ll probably find the following definition.

def unfold[A, B](in: A)(f: A => Option[(A, B)]): List[B]

This is equivalent to the definition we used, but a bit more compact in terms of the interface it presents. We used a more explicit definition that makes the structure of the method clearer.

2.5 The Algebra of Algebraic Data Types

A question that sometimes comes up is where the “algebra” in algebraic data types comes from. I want to talk about this a little bit and show some of the algebraic manipulations that can be done on algebraic data types.

The term algebra is used in the sense of abstract algebra, an area of mathematics. Abstract algebra deals with algebraic structures. An algebraic structure consists of a set of values, operations on that set, and properties that those operations must maintain. An example is the set of integers, the operations addition and multiplication, and the familiar properties of these operations such as associativity, which says that a + (b+c) = (a+b) + c. The abstract in abstract algebra means that it doesn’t deal with concrete values like integers—that would be far too easy to understand—and instead with abstractions with wacky names like semigroup, monoid, and ring. The example of integers above is an instance of a ring. We’ll see a lot more of these soon enough!

Algebraic data types also correspond to the algebraic structure called a ring. A ring has two operations, which are conventionally written + and ×. You’ll perhaps guess that these correspond to sum and product types respectively, and you’d be absolutely correct. What about the properties of these operations? We’ll they are similar to what we know from basic algebra:

• + and × are associative, so a + (b+c) = (a+b) + c and likewise for ×;
• a + b = b + a, known as commutivitiy;
• there is an identity 0 such that a + 0 = a;
• there is an identity 1 such that a × 1 = a;
• there is distribution, so that a × (b+c) = (a×b) + (a×c)

So far, so abstract. Let’s make it concrete by looking at actual examples in Scala.

Remember the algebraic data types work with types, so the operations + and × take types as parameters. So Int × String is equivalent to

final case class IntAndString(int: Int, string: String)

We can use tuples to avoid creating lots of names.

type IntAndString = (Int, String)

We can do the same thing for +. Int + String is

enum IntOrString {
  case IsInt(int: Int)
  case IsString(string: String)
}

or just

type IntOrString = Either[Int, String]

Exercise: Identities

Can you work out which Scala type corresponds to the identity 1 for product types?

What about the Scala type corresponding to the identity 0 for sum types?

What about the distribution law? This allows us to manipulate algebraic data types to form equivalent, but perhaps more useful, representations. Consider this example of a user data type.

final case class Person(name: String, permissions: Permissions)
enum Permissions {
  case User
  case Moderator
}

Written in mathematical notation, this is

Person = String × Permissions Permissions = User + Moderator

Performing substitution gets us

Person = String × (User+Moderator)

Applying distribution results in

Person = (String×User) + (String×Moderator)

which in Scala we can represent as

enum Person {
  case User(name: String)
  case Moderator(name: String)
}

Is this representation more useful? I can’t say without the context of where the data is being used. However I can say that knowing this manipulation is possible, and correct, is useful.

There is a lot more that could be said about algebraic data types, but at this point I feel we’re really getting into the weeds. I’ll finish up with a few pointers to other interesting facts:

• Exponential types exist. They are functions! A function A => B is equivalent to b^a.
• Quotient types also exist, but they are a bit weird. Read up about them if you’re interested.
• Another interesting algebraic manipulation is taking the derivative of an algebraic data type. This gives us a kind of iterator, known as a zipper, for that type.

2.6 Conclusions

We have covered a lot of material in this chapter. Let’s recap the key points.

Algebraic data types allow us to express data types by combining existing data types with logical and and logical or. A logical and constructs a product type while a logical or constructs a sum type. Algebraic data types are the main way to represent data in Scala.

Structural recursion gives us a skeleton for transforming any given algebraic data type into any other type. Structural recursion can be abstracted into a fold method.

We use several reasoning principles to help us complete the problem specific parts of a structural recursion:

1. reasoning independently by case;
2. assuming recursion is correct; and
3. following the types.

Following the types is a very general strategy that is can be used in many other situations.

Structural corecursion gives us a skeleton for creating any given algebraic data type from any other type. Structural corecursion can be abstracted into an unfold method. When reasoning about structural corecursion we can reason as we would for an imperative loop, or, if the input is an algebraic data type, use the principles for reasoning about structural recursion.

Notice that the two main themes of functional programming—composition and reasoning—are both already apparent. Algebraic data types are compositional: we compose algebraic data types using sum and product. We’ve seen many reasoning principles in this chapter.

I haven’t covered everything there is to know about algebraic data types; I think doing so would be a book in its own right. Below are some references that you might find useful if you want to dig in further, as well as some biographical remarks.

Algebraic data types are standard in introductory material on functional programming. Structural recursion is certainly extremely common in functional programming, but strangely seems to rarely be explicitly defined as I’ve done here. I learned about both from How to Design Programs [Felleisen et al. 2018].

I’m not aware of any approachable yet thorough treatment of either algebraic data types or structural recursion. Both seem to have become assumed background of any researcher in the field of programming languages, and relatively recent work is caked in layers of mathematics and obtuse notation that I find difficult reading. The infamous Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire [Meijer et al. 1991] is an example of such work. I suspect the core ideas of both date back to at least the emergence of computability theory in the 1930s, well before any digital computers existed.

The earliest reference I’ve found to structural recursion is Proving Properties of Programs by Structural Induction [Burstall 1969]. Algebraic data types don’t seem to have been fully developed, along with pattern matching, until NPL in 1977. NPL was quickly followed by the more influential language Hope, which spread the concept to other programming languages.

Corecursion is a bit better documented in the contemporary literature. How to Design Co-Programs [Gibbons 2021] covers the main ideas we have looked at here, while Gibbons and Jones [1998] discusses uses of unfold.

The Derivative of a Regular Type is its Type of One-Hole Contexts [McBride 2001] describes the derivative of algebraic data types.

3 Objects as Codata

In this chapter we will look at codata, the dual of algebraic data types. Algebraic data types focus on how things are constructed. Codata, in contrast, focuses on how things are used. We define codata by specifying the operations that can be performed on the type. This is very similar to the use of interfaces in object-oriented programming, and this is the first reason that we are interested in codata: codata puts object-oriented programming into a coherent conceptual framework with the other strategies we are discussing.

We’re not only interested in codata as a lens to view object-oriented programming. Codata also has properties that algebraic data does not. Codata allows us to create structures with an infinite number of elements, such as a list that never ends or a server loop that runs indefinitely. Codata has a different form of extensibility to algebraic data. Whereas we can easily write new functions that transform algebraic data, we cannot add new cases to the definition of an algebraic data type without changing the existing code. The reverse is true for codata. We can easily create new implementations of codata, but functions that transform codata are limited by the interface the codata defines.

In the previous chapter we saw structural recursion and structural corecursion as strategies to guide us in writing programs using algebraic data types. The same holds for codata. We can use codata forms of structural recursion and corecursion to guide us in writing programs that consume and produce codata respectively.

We’ll begin our exploration of codata by more precisely defining it and seeing some examples. We’ll then talk about representing codata in Scala, and the relationship to object-oriented programming. Once we can create codata, we’ll see how to work with it using structural recursion and corecursion, using an example of an infinite structure. Next we will look at transforming algebraic data to codata, and vice versa. We will finish by examining differences in extensibility.

A quick note about terminology before we proceed. We might expect to use the term algebraic codata for the dual of algebraic data, but conventionally just codata is used. I assume this is because data is usually understood to have a wider meaning than just algebraic data, but codata is not used outside of programming language theory. For simplicity and symmetry, within this chapter I’ll just use the term data to refer to algebraic data types.

3.1 Data and Codata

Data describes what things are, while codata describes what things can do.

We have seen that data is defined in terms of constructors producing elements of the data type. Let’s take a very simple example: a Bool is either True or False. We know we can represent this in Scala as

enum Bool {
  case True
  case False
}

The definition tells us there are two ways to construct an element of type Bool. Furthermore, if we have such an element we can tell exactly which case it is, by using a pattern match for example. Similarly, if the instances themselves hold data, as in List for example, we can always extract all the data within them. Again, we can use pattern matching to achieve this.

Codata, in contrast, is defined in terms of operations we can perform on the elements of the type. These operations are sometimes called destructors (which we’ve already encountered), observations, or eliminators. A common example of codata is a data structures such as a set. We might define the operations on a Set with elements of type A as:

• contains which takes a Set[A] and an element A and returns a Boolean indicating if the set contains the element;
• insert which takes a Set[A] and an element A and returns a Set[A] containing all the elements from the original set and the new element; and
• union which takes a Set[A] and a set Set[A] and returns a Set[A] containing all the elements of both sets.

In Scala we could implement this definition as

trait Set[A] {
  
  /** True if this set contains the given element */
  def contains(elt: A): Boolean
  
  /** Construct a new set containing all elements in this set and the given element */
  def insert(elt: A): Set[A]
  
  /** Construct the union of this and that set */
  def union(that: Set[A]): Set[A]
}

This definition does not tell us anything about the internal representation of the elements in the set. It could use a hash table, a tree, or something more exotic. It does, however, tell us what we can do with the set. We know we can take the union but not the intersection, for example.

If you come from the object-oriented world you might recognize the description of codata above as programming to an interface. In some ways codata is just taking concepts from the object-oriented world and presenting them in a way that is consistent with the rest of the functional programming paradigm. However, this does not mean adopting all the features of object-oriented programming. We won’t use state, which is difficult to reason about. We also won’t use implementation inheritance either, for the same reason. In our subset of object-oriented programming we’ll either be defining interfaces (which may have default implementations of some methods) or final classes that implement those interfaces. Interestingly, this subset of object-oriented programming is often recommended by advocates of object-oriented programming.

Let’s now be a little more precise in our definition of codata, which will make the duality between data and codata clearer. Remember the definition of data: it is defined in terms of sums (logical ors) and products (logical ands). We can transform any data into a sum of products. Each product in the sum is a constructor, and the product itself is the parameters that the constructor accepts. Finally, we can think of constructors as functions which take some arbitrary input and produce an element of data. Our end point is a sum of functions from arbitrary input to data.

More abstractly, if we are constructing an element of some data type A we call one of the constructors

• A1: (B, C, ...) => A; or
• A2: (D, E, ...) => A; or
• A3: (F, G, ...) => A; and so on.

Now we’ll turn to codata. Codata is defined as a product of functions, these functions being the destructors. The input to a destructor is always an element of the codata type and possibly some other parameters. The output is usually something that is not of the codata type. Thus constructing an element of some codata type A means defining

• A1: (A, B, ...) => C; and
• A2: (A, D, ...) => E; and
• A3: (A, F, ...) => G; and so on.

This hopefully makes the duality between the two clearer.

Now we understand what codata is, we will turn to representing codata in Scala.

3.2 Codata in Scala

We have already seen an example of codata, which I have repeated below.

trait Set[A] {
  
  def contains(elt: A): Boolean
  
  def insert(elt: A): Set[A]
  
  def union(that: Set[A]): Set[A]
}

The abstract definition of this, which is a product of functions, defines a Set with elements of type A as:

• a function contains taking a Set[A] and an element A and returning a Boolean,
• a function insert taking a Set[A] and an element A and returning a Set[A], and
• a function union taking a Set[A] and a set Set[A] and returning a Set[A].

Notice that the first parameter of each function is the type we are defining, Set[A].

The translation to Scala is:

• the overall type becomes a trait; and
• each function becomes a method on that trait. The first parameter is the hidden this parameter, and other parameters become normal parameters to the method.

This gives us the Scala representation we started with.

This is only half the story for codata. We also need to actually implement the interface we’ve just defined. There are three approaches we can use:

1. a final subclass, in the case where we want to name the implementation;
2. an anonymous subclass; or
3. more rarely, an object.

Neither final nor anonymous subclasses can be further extended, meaning we cannot create deep inheritance hierarchies. This in turn avoids the difficulties that come from reasoning about deep hierarchies. Using a class rather than a case class means we don’t expose implementation details like constructor arguments.

Some examples are in order. Here’s a simple example of Set, which uses a List to hold the elements in the set.

final class ListSet[A](elements: List[A]) extends Set[A] {

  def contains(elt: A): Boolean =
    elements.contains(elt)

  def insert(elt: A): Set[A] =
    ListSet(elt :: elements)

  def union(that: Set[A]): Set[A] =
    elements.foldLeft(that) { (set, elt) => set.insert(elt) }
}
object ListSet {
  def empty[A]: Set[A] = ListSet(List.empty)
}

This uses the first implementation approach, a final subclass. Where would we use an anonymous subclass? They are most useful when implementing methods that return our codata type. Let’s take union as an example. It returns our codata type, Set, and we could implement it as shown below.

trait Set[A] {
  
  def contains(elt: A): Boolean
  
  def insert(elt: A): Set[A]
  
  def union(that: Set[A]): Set[A] = {
    val self = this
    new Set[A] {
      def contains(elt: A): Boolean =
        self.contains(elt) || that.contains(elt)
        
      def insert(elt: A): Set[A] =
        // Arbitrary choice to insert into self
        self.insert(elt).union(that)
    }
  }
}

This uses an anonymous subclass to implement union on the Set trait, and hence defines the method for all subclasses. I haven’t made the method final so that subclasses can override it with a more efficient implementation. This does open up the danger of implementation inheritance. This is an example of where theory and craft diverge. In theory we never want implementation inheritance, but in practice it can be useful as an optimization.

It can also be useful to implement utility methods defined purely in terms of the destructors. Let’s say we wanted to implement a method containsAll that checks if a Set contains all the elements in an Iterable collection.

def containsAll(elements: Iterable[A]): Boolean

We can implement this purely in terms of contains on Set and forall on Iterable.

trait Set[A] {
  
  def contains(elt: A): Boolean
  
  def insert(elt: A): Set[A]
  
  def union(that: Set[A]): Set[A]
  
  def containsAll(elements: Iterable[A]): Boolean =
    elements.forall(elt => this.contains(elt))
}

Once again we could make this a final method. In this case it’s probably more justified as it’s difficult to imagine a more efficient implementation.

Data and codata are both realized in Scala as variations of the same language features of classes and objects. This means we can define types that have properties of both data and codata. We have actually already done this. When we define data we must define names for the fields within the data, thus defining destructors. This is the same in most languages, which don’t make a hard distinction between data and codata.

Part of the appeal, I think, of classes and objects is that they can express so many conceptually different abstractions with the same language constructs. This gives them a surface appearance of simplicity; it seems we need to learn only one abstraction to solve a huge of number of coding problems. However this apparent simplicity hides real complexity, as this variety of uses forces us to reverse engineer the conceptual intention from the code.

3.3 Structural Recursion and Corecursion for Codata

In this section we’ll build a library for streams, also known as lazy lists. These are the codata equivalent of lists. Whereas a list must have a finite length, streams have an infinite length. We’ll use this example to explore structural recursion and structural corecursion as applied to codata.

Let’s start by reviewing structural recursion and corecursion. The key idea is to use the input or output type, respectively, to drive the process of writing the method. We’ve already seen how this works with data, where we emphasized structural recursion. With codata it’s more often the case that structural corecursion is used. The steps for using structural corecursion are:

1. recognize the output of the method or function is codata;
2. write down the skeleton to construct an instance of the codata type, usually using an anonymous subclass; and
3. fill in the methods, using strategies such as structural recursion or following the types to help.

It’s important that any computation takes places within the methods, and so only runs when the methods are called. Once we start creating streams the importance of this will become clear.

For structural recursion the steps are:

1. recognize the input of the method or function is codata;
2. note the codata’s destructors as possible sources of values in writing the method; and
3. complete the method, using strategies such as following the types or structural corecursion and the methods identified above.

Our first step is to define our stream type. As this is codata, it is defined in terms of its destructors. The destructors that define a Stream of elements of type A are:

• a head of type A; and
• a tail of type Stream[A].

Note these are almost the destructors of List. We haven’t defined isEmpty as a destructor because our streams never end and thus this method would always return false. (A lot of real implementations, such as the LazyList in the Scala standard library, do define such a method which allows them to represent finite and infinite lists in the same structure. We’re not doing this for simplicity and because we want to work with codata in its purest form.)

We can translate this to Scala, as we’ve previously seen, giving us

trait Stream[A] {
  def head: A
  def tail: Stream[A]
}

Now we can create an instance of Stream. Let’s create a never-ending stream of ones. We will start with the skeleton below and apply strategies to complete the code.

val ones: Stream[Int] = ???

The first strategy is structural corecursion. We’re returning an instance of codata, so we can insert the skeleton to construct a Stream.

val ones: Stream[Int] =
  new Stream[Int] {
    def head: Int = ???
    def tail: Stream[Int] = ???
  }

Here I’ve used the anonymous subclass approach, so I can just write all the code in one place.

The next step is to fill in the method bodies. The first method, head, is trivial. The answer is 1 by definition.

val ones: Stream[Int] =
  new Stream[Int] {
    def head: Int = 1
    def tail: Stream[Int] = ???
  }

It’s not so obvious what to do with tail. We want to return a Stream[Int] so we could apply structural corecursion again.

val ones: Stream[Int] =
  new Stream[Int] {
    def head: Int = 1
    def tail: Stream[Int] =
      new Stream[Int] {
        def head: Int = 1
        def tail: Stream[Int] = ???
      }
  }

This approach doesn’t seem like it’s going to work. We’ll have to write this out an infinite number of times to correctly implement the method, which might be a problem.

Instead we can follow the types. We need to return a Stream[Int]. We have one in scope: ones. This is exactly the Stream we need to return: the infinite stream of ones!

val ones: Stream[Int] =
  new Stream[Int] {
    def head: Int = 1
    def tail: Stream[Int] = ones
  }

You might be alarmed to see the circular reference to ones in tail. This works because it is within a method, and so is only evaluated when that method is called. This delaying of evaluation is what allows us to represent an infinite number of elements, as we only ever evaluate a finite portion of them. This is a core difference from data, which is fully evaluated when it is constructed.

Let’s check that our definition of ones does indeed work. We can’t extract all the elements from an infinite Stream (at least, not in finite time) so in general we’ll have to resort to checking a finite sequence of elements.

ones.head
// res0: Int = 1
ones.tail.head
// res1: Int = 1
ones.tail.tail.head
// res2: Int = 1

This all looks correct. We’ll often want to check our implementation in this way, so let’s implement a method, take, to make this easier.

trait Stream[A] {
  def head: A
  def tail: Stream[A]
  
  def take(count: Int): List[A] =
    count match {
      case 0 => Nil
      case n => head :: tail.take(n - 1)
    }
}

We can use either the structural recursion or structural corecursion strategies for data to implement take. Since we’ve already covered these in detail I won’t go through them here. The important point is that take only uses the destructors when interacting with the Stream.

Now we can more easily check our implementations are correct.

ones.take(5)
// res4: List[Int] = List(1, 1, 1, 1, 1)

For our next task we’ll implement map. Implementing a method on Stream allows us to see both structural recursion and corecursion for codata in action. As usual we begin by writing out the method skeleton.

trait Stream[A] {
  def head: A
  def tail: Stream[A]
  
  def map[B](f: A => B): Stream[B] = 
    ???
}

Now we have a choice of strategy to use. Since we haven’t used structural recursion yet, let’s start with that. The input is codata, a Stream, and the structural recursion strategy tells us we should consider using the destructors. Let’s write them down to remind us of them.

trait Stream[A] {
  def head: A
  def tail: Stream[A]
  
  def map[B](f: A => B): Stream[B] = {
    this.head ???
    this.tail ???
  }
}

To make progress we can follow the types or use structural corecursion. Let’s choose corecursion to see another example of it in use.

trait Stream[A] {
  def head: A
  def tail: Stream[A]
  
  def map[B](f: A => B): Stream[B] = {
    this.head ???
    this.tail ???
    
    new Stream[B] {
      def head: B = ???
      def tail: Stream[B] = ???
    }
  }
}

Now we’ve used structural recursion and structural corecursion, a bit of following the types is in order. This quickly arrives at the correct solution.

trait Stream[A] {
  def head: A
  def tail: Stream[A]
  
  def map[B](f: A => B): Stream[B] = {
    val self = this 
    new Stream[B] {
      def head: B = f(self.head)
      def tail: Stream[B] = self.tail.map(f)
    }
  }
}

There are two important points. Firstly, notice how I gave the name self to this. This is so I can access the value inside the new Stream we are creating, where this would be bound to this new Stream. Next, notice that we access self.head and self.tail inside the methods on the new Stream. This maintains the correct semantics of only performing computation when it has been asked for. If we performed the computation outside of the methods that we would do it too early, which is some cases can lead to an infinite loop.

As our final example, let’s return to constructing Stream, and implement the universal constructor unfold. We start with the skeleton for unfold, remembering the seed parameter.

trait Stream[A] {
  def head: A
  def tail: Stream[A]
}
object Stream {
  def unfold[A, B](seed: A): Stream[B] =
    ???
}

It’s natural to apply structural corecursion to make progress.

trait Stream[A] {
  def head: A
  def tail: Stream[A]
}
object Stream {
  def unfold[A, B](seed: A): Stream[B] =
    new Stream[B]{
      def head: B = ???
      def tail: Stream[B] = ???
    }
}

Now we can follow the types, adding parameters as we need them. This gives us the complete method shown below.

trait Stream[A] {
  def head: A
  def tail: Stream[A]
}
object Stream {
  def unfold[A, B](seed: A, f: A => B, next: A => A): Stream[B] =
    new Stream[B]{
      def head: B = 
        f(seed)
      def tail: Stream[B] = 
        unfold(next(seed), f, next)
    }
}

We can use this to implement some interesting streams. Here’s a stream that alternates between 1 and -1.

val alternating = Stream.unfold(
  true, 
  x => if x then 1 else -1, 
  x => !x
)

We can check it works.

alternating.take(5)
// res11: List[Int] = List(1, -1, 1, -1, 1)

Exercise: Stream Combinators

It’s time for you to get some practice with structural recursion and structural corecursion using codata. Implement filter, zip, and scanLeft on Stream. They have the same semantics as the same methods on List, and the signatures shown below.

trait Stream[A] {
  def head: A
  def tail: Stream[A]

  def filter(pred: A => Boolean): Stream[A]
  def zip[B](that: Stream[B]): Stream[(A, B)]
  def scanLeft[B](zero: B)(f: (B, A) => B): Stream[B]
}

trait Stream[A] {
  def head: A
  def tail: Stream[A]

  def filter(pred: A => Boolean): Stream[A] = {
    val self = this
    new Stream[A] {
      def head: A = {
        def loop(stream: Stream[A]): A =
          if pred(stream.head) then stream.head
          else loop(stream.tail)
          
        loop(self)
      }
      
      def tail: Stream[A] = {
        def loop(stream: Stream[A]): Stream[A] =
          if pred(stream.head) then stream.tail
          else loop(stream.tail)
          
        loop(self)
      }
    }
  }

  def zip[B](that: Stream[B]): Stream[(A, B)] = {
    val self = this 
    new Stream[(A, B)] {
      def head: (A, B) = (self.head, that.head)
      
      def tail: Stream[(A, B)] =
        self.tail.zip(that.tail)
    }
  }

  def scanLeft[B](zero: B)(f: (B, A) => B): Stream[B] = {
    val self = this
    new Stream[B] {
      def head: B = f(zero, self.head)
      
      def tail: Stream[B] =
        self.tail.scanLeft(this.head)(f)
    }
  }
}

We can do some neat things with the methods defined above. For example, here is the stream of natural numbers.

val naturals = Stream.ones.scanLeft(0)((b, a) => b + a)

As usual, we should check it works.

naturals.take(5)
// res15: List[Int] = List(1, 2, 3, 4, 5)

We could also define naturals using unfold. More interesting is defining it in terms of itself.

val naturals: Stream[Int] =
  new Stream {
    def head = 1
    def tail = naturals.map(_ + 1)
  }

This might be confusing. If so, spend a bit of time thinking about it. It really does work!

naturals.take(5)
// res17: List[Int] = List(1, 2, 3, 4, 5)

3.3.1 Efficiency and Effects

You may have noticed that our implement recomputes values, possibly many times. A good example is the implementation of filter. This recalculates the head and tail on each call, which could be a very expensive operation.

def filter(pred: A => Boolean): Stream[A] = {
  val self = this
  new Stream[A] {
    def head: A = {
      def loop(stream: Stream[A]): A =
        if pred(stream.head) then stream.head
        else loop(stream.tail)
        
      loop(self)
    }
    
    def tail: Stream[A] = {
      def loop(stream: Stream[A]): Stream[A] =
        if pred(stream.head) then stream.tail
        else loop(stream.tail)
        
      loop(self)
    }
  }
}

We know that delaying the computation until the method is called is important, because that is how we can handle infinite and self-referential data. However we don’t need to redo this computation on succesive calls. We can instead cache the result from the first call and use that next time. Scala makes this easy with lazy val, which is a val that is not computed until its first call. Additionally, Scala’s use of the uniform access principle means we can implement a method with no parameters using a lazy val. Here’s a quick example demonstrating it in use.

def always[A](elt: => A): Stream[A] =
  new Stream[A] {
    lazy val head: A = elt
    lazy val tail: Stream[A] = always(head)
  }
  
val twos = always(2)

As usual we should check our work.

twos.take(5)
// res18: List[Int] = List(2, 2, 2, 2, 2)

We get the same result whether we use a method or a lazy val, because we are assuming that we are only dealing with pure computations that have no dependency on state that might change. In this case a lazy val simply consumes additional space to save on time.

Recomputing a result every time it is needed is known as call by name, while caching the result the first time it is computed is known as call by need. These two different evaluation strategies can be applied to individual values, as we’ve done here, or across an entire programming. Haskell, for example, uses call by need. All values in Haskell are only computed the first time they are need. This is approach is sometimes known as lazy evaluation. Another alternative, called call by value, computes results when they are defined instead of waiting until they are needed. This is the default in Scala.

We can illustrate the difference between call by name and call by need if we use an impure computation. For example, we can define a stream of random numbers. Random number generators depend on some internal state.

Here’s the call by name implementation, using the methods we have already defined.

import scala.util.Random

val randoms: Stream[Double] = 
  Stream.unfold(Random, r => r.nextDouble(), r => r)

Notice that we get different results each time we take a section of the Stream. We would expect these results to be the same.

randoms.take(5)
// res19: List[Double] = List(
//   0.6334382512313489,
//   0.7396049793308253,
//   0.3922997735119247,
//   0.501891892971581,
//   0.6230535998247712
// )
randoms.take(5)
// res20: List[Double] = List(
//   0.2833341188592764,
//   0.6911714726693775,
//   0.8789224476608815,
//   0.27127277488637436,
//   0.46046234590888224
// )

Now let’s define the same stream in a call by need style, using lazy val.

val randomsByNeed: Stream[Double] =
  new Stream[Double] {
    lazy val head: Double = Random.nextDouble()
    lazy val tail: Stream[Double] = randomsByNeed
  }

This time we get the same result when we take a section, and each number is the same.

randomsByNeed.take(5)
// res21: List[Double] = List(
//   0.5198235372150013,
//   0.5198235372150013,
//   0.5198235372150013,
//   0.5198235372150013,
//   0.5198235372150013
// )
randomsByNeed.take(5)
// res22: List[Double] = List(
//   0.5198235372150013,
//   0.5198235372150013,
//   0.5198235372150013,
//   0.5198235372150013,
//   0.5198235372150013
// )

If we wanted a stream that had a different random number for each element but those numbers were constant, we could redefine unfold to use call by need.

def unfoldByNeed[A, B](seed: A, f: A => B, next: A => A): Stream[B] =
  new Stream[B]{
    lazy val head: B = 
      f(seed)
    lazy val tail: Stream[B] = 
      unfoldByNeed(next(seed), f, next)
  }

Now redefining randomsByNeed using unfoldByNeed gives us the result we are after. First, redefine it.

val randomsByNeed2 =
  unfoldByNeed(Random, r => r.nextDouble(), r => r)

Then check it works.

randomsByNeed2.take(5)
// res23: List[Double] = List(
//   0.2004412758108174,
//   0.6721532116774,
//   0.2960856144992955,
//   0.48769348667396584,
//   0.5995184771230712
// )
randomsByNeed2.take(5)
// res24: List[Double] = List(
//   0.2004412758108174,
//   0.6721532116774,
//   0.2960856144992955,
//   0.48769348667396584,
//   0.5995184771230712
// )

These subtleties are one of the reasons that functional programmers try to avoid using state as far as possible.

3.4 Relating Data and Codata

In this section we’ll explore the relationship between data and codata, and in paritcular converting one to the other. We’ll look at it in two ways: firstly a very surface-level relationship between the two, and then a deep connection via fold.

Remember that data is a sum of products, where the products are constructors and we can view constructors as functions. So we can view data as a sum of functions. Meanwhile, codata is a product of functions. We can easily make a direct correspondence between the functions-as-constructors and the functions in codata. What about the difference between the sum and the product that remains. Well, when we have a product of functions we only call one at any point in our code. So the logical or is in the choice of function to call.

Let’s see how this works with a familiar example of data, List. As an algebraic data type we can define

enum List[A] {
  case Pair(head: A, tail: List[A])
  case Empty()
}

The codata equivalent is

trait List[A] {
  def pair(head: A, tail: List[A]): List[A]
  def empty: List[A]
}

In the codata implementation we are explicitly representing the constructors as methods, and pushing the choice of constructor to the caller. In a few chapters we’ll see a use for this relationship, but for now we’ll leave it and move on.

The other way to view the relationship is a connection via fold. We’ve already learned how to derive the fold for any algebraic data type. For Bool, defined as

enum Bool {
  case True
  case False
}

the fold method is

enum Bool {
  case True
  case False
  
  def fold[A](t: A)(f: A): A =
    this match {
      case True => t
      case False => f
    }
}

We know that fold is universal: we can write any other method in terms of it. It therefore provides a universal destructor and is the key to treating data as codata. In this case the fold is something we use all the time, except we usually call it if.

Here’s the codata version of Bool, with fold renamed to if. (Note that Scala allows us to define methods with the same name as key words, in this case if, but we have to surround them in backticks to use them.)

trait Bool {
  def `if`[A](t: A)(f: A): A
}

Now we can define the two instances of Bool purely as codata.

val True = new Bool {
  def `if`[A](t: A)(f: A): A = t
}

val False = new Bool {
  def `if`[A](t: A)(f: A): A = f
}

Let’s see this in use by defining and in terms of if, and then creating some examples. First the definition of and.

def and(l: Bool, r: Bool): Bool =
  new Bool {
    def `if`[A](t: A)(f: A): A =
      l.`if`(r)(False).`if`(t)(f)
  }

Now the examples. This is simple enough that we can try the entire truth table.

and(True, True).`if`("yes")("no")
// res1: String = "yes"
and(True, False).`if`("yes")("no")
// res2: String = "no"
and(False, True).`if`("yes")("no")
// res3: String = "no"
and(False, False).`if`("yes")("no")
// res4: String = "no"

Exercise: Or and Not

Test your understanding of Bool by implementing or and not in the same way we implemented and above.

def or(l: Bool, r: Bool): Bool =
  new Bool {
    def `if`[A](t: A)(f: A): A =
      l.`if`(True)(r).`if`(t)(f)
  }

def not(b: Bool): Bool =
  new Bool {
    def `if`[A](t: A)(f: A): A =
      b.`if`(False)(True).`if`(t)(f)
  }

or(True, True).`if`("yes")("no")
// res5: String = "yes"
or(True, False).`if`("yes")("no")
// res6: String = "yes"
or(False, True).`if`("yes")("no")
// res7: String = "yes"
or(False, False).`if`("yes")("no")
// res8: String = "no"

not(True).`if`("yes")("no")
// res9: String = "no"
not(False).`if`("yes")("no")
// res10: String = "yes"