Why are Haskell algebraic data types "closed"?

Question

Correct me if I'm wrong, but it seems like algebraic data types in Haskell are useful in many of the cases where you would use classes and inheritance in OO languages. But there is a big difference: once an algebraic data type is declared, it can not be extended elsewhere. It is "closed". In OO, you can extend already defined classes. For example:

data Maybe a = Nothing | Just a

There is no way that I can somehow add another option to this type later on without modifying this declaration. So what are the benefits of this system? It seems like the OO way would be much more extensible.

Answer 1

The answer has to do with in what ways the code is easy to extend, a tension between classes and algebraic data types that Phil Wadler dubbed "the expression problem":

• With algebraic data types,

  • It is very cheap to add a new operation on things: you just define a new function. All the old functions on those things continue to work unchanged.

  • It is very expensive to add a new kind of thing: you have to add a new constructor an existing data type, and you have to edit and recompile every function which uses that type.

• With classes,

  • It is very cheap to add a new kind of thing: just add a new subclass, and as needed you define specialized methods, in that class, for all the existing operations. The superclass and all the other subclasses continue to work unchanged.

  • It is very expensive to add a new operation on things: you have to add a new method declaration to the superclass and potentially add a method definition to every existing subclass. In practice, the burden varies depending on the method.

So, algebraic data types are closed because a closed type supports certain kinds of program evolution well. For example, if your data types define a language, it is easy to add new compiler passes without invalidating old ones or changing the data.

It is possible to have "open" data types, but except under carefully controlled circumstances, the type checking becomes difficult. Todd Millstein did some very beautiful work on a language design that supports open algebraic types and extensible functions, all with a modular type checker. I found his paper a great pleasure to read.

Answer 2

The fact that ADT are closed makes it a lot easier to write total functions. That are functions that always produce a result, for all possible values of its type, eg.

maybeToList :: Maybe a -> [a]
maybeToList Nothing  = []
maybeToList (Just x) = [x]

If Maybe were open, someone could add a extra constructor and the maybeToList function would suddenly break.

In OO this isn't an issue, when you're using inheritance to extend a type, because when you call a function for which there is no specific overload, it can just use the implementation for a superclass. I.e., you can call printPerson(Person p) just fine with a Student object if Student is a subclass of Person.

In Haskell, you would usually use encapsulation and type classes when you need to extent your types. For example:

class Eq a where
   (==) :: a -> a -> Bool

instance Eq Bool where
  False == False = True
  False == True  = False
  True  == False = False
  True  == True  = True

instance Eq a => Eq [a] where
  []     == []     = True
  (x:xs) == (y:ys) = x == y && xs == ys
  _      == _      = False

Now, the == function is completely open, you can add your own types by making it an instance of the Eq class.

---

Note that there has been work on the idea of extensible datatypes, but that is definitely not part of Haskell yet.

Answer 3

If you write a function like

maybeToList Nothing = []
maybeToList (Just x) = [x]

then you know that it's never going to produce a runtime error because you've covered all of the cases. This ceases to be true as soon as the Maybe type is extensible. In those cases where you need an extensible type (and they are rarer than you think), the canonical Haskell solution is to use a type class.

Answer 4

Check "Open data types and open functions" http://lambda-the-ultimate.org/node/1453

In object-oriented languages, it is easy to extend data by defining new classes, but it is difficult to add new functions. In functional languages, the situation is reversed: adding new functions poses no problems, but extending data (adding new data constructors) requires modifying existing code. The problem of supporting both directions of extensibility is known as the expression problem. We present open data types and open functions as a lightweight solution to the expression problem in the Haskell language. The idea is that constructors of open data types, and equations of open functions can appear scattered throughout a program. In particular, they may reside in different modules. The intended semantics is as follows: the program should behave as if the data types and functions were closed, defined in one place. The order of function equations is determined by best-fit pattern matching, where a specific pattern takes precedence over an unspecific one. We show that our solution is applicable to the expression problem, generic programming, and exceptions. We sketch two implementations. A simple one, derived from the semantics, and one based on mutually recursive modules that permits separate compilation.