What problem do algebraic data types solve?

Question

Fair warning, I'm new to functional programming so I may hold many bad assumptions.

I've been learning about algebraic types. Many functional languages seem to have them, and they are fairly useful in conjunction with pattern matching. However, what problem do they actually solve? I can implement a seemingly (sort-of) algebraic type in C# like this:

public abstract class Option { }
public class None : Option { }
public class Some<T> : Option
{
    public T Value { get; set; }
}

var result = GetSomeValue();
if(result is None)
{
}
else
{
}

But I think most would agree this is a bastardization of object oriented programming, and you shouldn't ever do it. So does functional programming just add a cleaner syntax that makes this style of programming seem less gross? What else am I missing?

Answer 1

Classes with interfaces and inheritance present an open world: Anyone can add a new kind of data. For a given interface, there may be classes implementing it all over the world, in different files, in different projects, at different companies. They make it easy to add cases to the data structures, but because the implementations of the interface are decentralized, it is hard to add a new method to the interface. Once an interface is public, it is basically frozen. Nobody knows all the possible implementations.

Algebraic data types are the dual to that, they are closed. All the cases of the data are listed in one place and operations not only can list the variants exhaustively, they are encouraged to do so. Consequently writing a new function operating on an algebraic data type is trivial: Just write the damn function. In return, adding new cases is complicated because you need to go over basically the entire code base and extend every match. Similar to the situation with interfaces, in the Rust standard library, adding a new variant is a breaking change (for public types).

These are two sides of the expression problem. Algebraic data types are an incomplete solution to them, but so is OOP. Both have advantages depending on how many cases of data there are, how often those cases change, and how frequently the operations are extended or changed. (Which is why many modern languages provide both, or something similar, or go straight for more powerful and more complicated mechanisms that try to subsume both approaches.)

Answer 2

So does functional programming just add a cleaner syntax that makes this style of programming seem less gross?

That is a simplification perhaps, but yes.

What else am I missing?

Let's be clear on what algebraic data types are (summarizing this fine link from Learn you as Haskell):

• A sum type that says "this value can be an A or a B".
• A product type that says "this value is both an A and a B".

your example only really works with the first.

What you're perhaps missing is that by providing these two basic operations, functional languages let you build everything else. C# has structs, classes, enums, generics on top of those, and piles of rules to govern how these things behave.

Combined with some syntax to help, the functional languages can decompose operations down to these two paths, providing a clean, simple and elegant approach to types.

What problem do algebraic data types solve?

They solve the same problem as any other type system: "what values are legal to use here?" - they just take a different approach to it.

Answer 3

It may surprise you to learn that pattern matching is not considered the most idiomatic way to work with Options. See the documentation of Scala's Options for more about that. I'm not sure why so many FP tutorials encourage this usage.

Mostly what you're missing is there are a whole bunch of functions created to make working with Options easier. Consider the main example from the Scala docs:

val name: Option[String] = request getParameter "name"
val upper = name map { _.trim } filter { _.length != 0 } map { _.toUpperCase }
println(upper getOrElse "")

Notice how map and filter let you chain operations on Options, without having to check at each point whether you have None or not. Then at the end, you use getOrElse to specify a default value. At no point are you doing something "gross" like checking types. Any unavoidable type checking is done internal to the library. Haskell has its own set of analagous functions, not to mention the large set of functions that will work on any monad or functor.

Other algebraic data types have their own idiomatic ways to work with them, and pattern matching is low on the totem pole in most cases. Likewise, when you create your own types, you're expected to provide similar functions to work with them.