What Are The Uses of Algebraic Data Types

data typesfunctional programming

I'm reading about Algebraic Data Types (thanks to Richard Minerich I found this excellent explanation of the concept). While I think I understand the notion of sum types and product types etc., what I'm not quite understanding is how Algebraic Data Types are useful beyond specifying pattern matching. What other things can one do with ADT's beyond pattern matching?

EDIT: I'm not asking what can a developer do with ADT's that can't be done with objects. I'm asking if there are other operations that ADT's allow; for example, can one do additional reasoning about the types involved if ADT's are employed? Do ADT's facilitate some sort of type analysis that wouldn't be possible without them?

Best Answer

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.

Related Topic