Functional Programming – What Problem Do Algebraic Data Types Solve?

algebraic-data-typefunctional programming

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?

Best Answer

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

Related Solutions

What Are The Uses of Algebraic Data Types

Algebraic Data Types are distinct in that they can be constructed from several types of "things". For instance, a Tree can contain either nothing (Empty), a Leaf, or a Node.

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

Since a Node is composed of two Trees, algebraic data types can be recursive.

Pattern matching allows algebraic data types to be deconstructed in a way that maintains type safety. Consider the following implementation of depth and its pseudocode equivalent:

depth :: Tree -> Int
depth Empty = 0
depth (Leaf n) = 1
depth (Node l r) = 1 + max (depth l) (depth r)

compared to:

switch on (data.constructor)
  case Empty:
    return 0
  case Leaf:
    return 1
  case Node:
    let l = data.field1
    let r = data.field2
    return 1 + max (depth l) (depth r)

This has the disadvantage that the programmer must remember to case Empty before Leaf so that field1 is not accessed on an Empty tree. Likewise, the Leaf case must be declared before the Node case so that field2 is not accessed on Leaf. Thus type safety is thus not maintained by the language but rather imposes additional cognitive load on the programmer. By the way, I'm grabbing these examples directly from the wikipedia pages.

Of course, a duck-typing langauge could do something like this:

class Empty
  def depth
    0
  end
end

class Leaf
  def depth
    1
  end
end

class Node
  attr_accessor :field1, :field2

  def depth
    1 + [field1.depth, field2.depth].max
  end
end

So algebraic data types may not be strictly better than their OOP equivalent, but they do provide a different set of tensions to work with when constructing software.

Functional Programming – Understanding Values, Types, and Kinds

According to the basic Wikipedia entry about kinds "a kind is the type of a type constructor or, less commonly, the type of a higher-order type operator". So I understand that to mean the type of a kind is a kind and it's kinds all the way down (which makes sense - otherwise we would need an infinite number of names, one for each meta-type(i)).

From the same reference:

"(* => *) => * is the kind of a higher-order type operator from unary type constructors to proper types. These are very seldom encountered, even in programming language theory, but see Pierce (2002), chapter 32 for an application."

would seem to indicate it has limited but non-zero usefulness.

Not a great answer, but hopefully it will stop the "not a real question" close votes until someone who, say, implemented a Haskell compiler and really knows what he's talking about comes along...

Best Answer

Related Solutions

What Are The Uses of Algebraic Data Types

Functional Programming – Understanding Values, Types, and Kinds

Related Topic