Algebraic Data Types vs. Class Hierarchies: The Expression Problem

Hello! Welcome to the final lesson in our module on Algebraic Data Types and Pattern Matching.

Introduction

In our previous lessons, we've built a solid foundation for understanding functional data modeling. We defined Algebraic Data Types (ADTs) as compositions of product types (records, tuples) and sum types (tagged unions). We then saw their power in practice, first by building a type-safe expression evaluator with GADTs, and then by using simple sum types like Option/Maybe to eliminate an entire class of runtime errors related to null values.

Today, we will address the learning outcome: Compare algebraic data types with class hierarchies for modeling data, introducing the Expression Problem as a key design challenge.

We'll synthesize the concepts from this module to compare the ADT-based approach, which is central to functional programming, with the class-based inheritance model that is the cornerstone of object-oriented programming. This comparison will lead us directly to a famous and fundamental challenge in programming language design known as the Expression Problem. Understanding this problem reveals the deep trade-offs between the two paradigms and provides a powerful framework for making architectural decisions.

1. Two Approaches to Modeling Data

Let's start with a classic example: modeling geometric shapes. We want to represent different shapes (like circles and squares) and perform operations on them (like calculating the area). There are two canonical ways to structure this code, corresponding to the object-oriented and functional paradigms.

A well-written blog post by Henrik Engström provides an excellent walkthrough of these two approaches using Java, a language whose syntax will be familiar.

As the article demonstrates, the two approaches differ fundamentally in where the "logic" resides:

• Object-Oriented (Polymorphism): The logic is attached to the data. Each Shape object knows how to calculate its own area. The calculateArea method is part of the Shape interface, and each class (Circle, Square) provides its own implementation.
• Functional (Pattern Matching): The logic is separate from the data. The Shape ADT is just a passive data structure. The logic for calculating the area resides in an external function, calculateArea(shape), which inspects the shape's type and acts accordingly.

At first glance, the polymorphic OO approach might seem more "natural" if you're accustomed to that paradigm. However, as we'll now see, each approach has distinct advantages and disadvantages when it comes to extensibility.

2. The Expression Problem

This duality in structuring code leads to a classic trade-off. What happens when we want to extend our system? There are two ways we might want to extend it:

1. Add a new type (e.g., add a Triangle to our set of shapes).
2. Add a new operation (e.g., add a perimeter() function that works on all shapes).

The difficulty of performing these two kinds of extensions is precisely what separates the OO and functional approaches. This challenge was formally named "The Expression Problem" by computer scientist Philip Wadler.

Let's get a formal definition and some historical context from the Wikipedia article on the topic.

Now, let's connect this formal definition back to our Shape example by reading the key section of the blog post we started with.

Let's summarize the trade-off in a table.

	Add New Type (e.g., Triangle)	Add New Operation (e.g., perimeter)
OO (Class Hierarchy)	Easy: Create a new Triangle class. No existing code is touched.	Hard: Modify the Shape interface, then modify every existing class (Circle, Square) to add the new method.
FP (ADT + Pattern Matching)	Hard: Modify the Shape ADT definition, then modify every existing function (area, perimeter) to add a case for Triangle.	Easy: Create a new perimeter function. No existing code is touched.

This is a fundamental duality. Neither approach solves the problem perfectly; they optimize for different axes of change. The choice between them is an architectural decision that depends on how you expect your system to evolve.

Given your experience in finance and product development, you've likely encountered this problem implicitly. When designing a system for financial instruments, for example, you face a choice:

• Do you optimize for adding new instrument types (equities, bonds, futures, exotic options)? An OO approach might be better.
• Or do you optimize for adding new operations on a stable set of instruments (pricing, risk analysis, reporting, compliance checks)? A functional approach might be better.

The Expression Problem gives us the vocabulary to discuss this trade-off explicitly.

3. Implementations and Perspectives

Let's look at these two approaches in action.

The OO Approach in Practice

This video clip shows a Swift implementation of the Shape problem using a protocol (Swift's version of an interface). It perfectly demonstrates the OO side of the trade-off.

The ADT Approach in Practice

The functional approach using ADTs and pattern matching is a cornerstone of languages like Haskell, OCaml, and Rust. This next video, while opinionated, makes a strong case for why this model is so powerful for building robust systems.

The Mario example is powerful because it shows the practical payoff of the "hard" part of the ADT trade-off. When you add a new state (a new type), the compiler forces you to update all your transition functions (collect in the video). This isn't just a burden; it's a compile-time safety check that prevents you from forgetting to handle the new case, which would otherwise become a runtime bug.

Conclusion

This lesson concludes our module on ADTs by placing them in a broader context, comparing them with the familiar class hierarchies of OOP.

Key Takeaways:

• Data modeling can be approached in two primary ways: the object-oriented style (grouping operations with data in objects) and the functional style (defining operations externally to passive data structures).
• The Expression Problem formalizes the trade-off between these two styles. Neither paradigm makes it easy to extend a system with both new data types and new operations simultaneously without modifying existing code.
• Class hierarchies make it easy to add new types but hard to add new operations.
• ADTs with pattern matching make it easy to add new operations but hard to add new types. However, the compiler assists in this "hard" direction by flagging non-exhaustive pattern matches.
• The choice of which paradigm to favor is a critical architectural decision that depends on the anticipated evolution of the software. Many modern multi-paradigm languages (like Rust, Scala, and Swift) offer features from both worlds, providing developers with more tools to manage this trade-off.

Next Lesson Preview:

We have now completed our deep dive into the functional approach to data structures. In the next module, "Evaluation Strategies and Laziness," we will shift our focus from data to computation. We'll begin by examining the most fundamental decision a language makes about executing code: how it evaluates function arguments. We will contrast call-by-value, the strategy used by most mainstream languages, with the less common but powerful call-by-name, exploring their historical origins in Algol 60 and their surprising effects on program behavior. This will lay the groundwork for understanding the concept of lazy evaluation.