Why do we need "Algebraic Data Types"?

Question

I've read some explanation of Algebraic Data Types:

• The Algebra of Algebraic Data types I
• The Algebra of Algebraic Data types II
• The Algebra of Algebraic Data types III
• The Algebra of Data, and Calculus of Mutation

These articles give very detail description and code samples.

At first I was thinking Algebraic Data Type was just for defining some types easily and we can match them with pattern matching. But after reading these articles, I found "pattern matching" is not even mentioned there, and the content looks interesting but far more complex than I expected.

So I have some questions (which are not answered in these articles):

• Why do we need it, say, in Haskell or Scala?
• What we can do if we have it, and what we can't do if we don't have it?

Answer 1

The blog post you mention is more about the mathematical aspects of algebraic data types that about their practical use in programming. I think most functional programmers first learnt about algebraic data types by using them in some programming language, and only later studied their algebraic properties.

Indeed, the intent of the blog post is clear from its very beginning:

In this series of posts I’ll explain why Haskell’s data types are called algebraic - without mentioning category theory or advanced math.

Anyway, the practical usefulness of algebraic types is best appreciated by playing around with them.

Suppose, for instance, you want to write a function to intersect two segments on a plane.

def intersect(s1: Segment, s2: Segment): ???

What should the result be? It's tempting to write

def intersect(s1: Segment, s2: Segment): Point

but what if there's no intersection? One might attempt to patch that corner case by returning null, or by throwing a NoIntersection exception. However, two segments might also overlap on more than one point, when they lie on the same straight line. What should we do in such cases? Throwing another exception?

The algebraic types approach is to design a type covering all the cases:

sealed trait Intersection
case object NoIntersection extends Intersection
case class SinglePoint(p: Point) extends Intersection
case class SegmentPortion(s: Segment) extends Intersection

def intersect(s1: Segment, s2: Segment): Intersection

There are many practical cases where such approach feels quite natural. In some other languages lacking algebraic types, one has to resort to exceptions, to nulls (also see the billion-dollar mistake), to non-sealed classes (making it impossible for the compiler to check for exhaustiveness of pattern matching), or to other features provided by the language. Arguably, the "best" option in OOP is to use the Visitor pattern to encode algebraic types and pattern matching in languages which have no such features. Still, having that directly supported in the language, as in scala, is much more convenient.