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

Okay, by "open" here you're meaning "can be derived from" and not open in the sense of Ruby and Smalltalk, where you can extend a class with new methods at run-time, right?

In any case, notice two things: first, in most OO languages that are primarily inheritance-based, there is a way to declare a class to restrict it's ability to be inherited. Java has "final", and there are hacks for this in C++. So on that, it's just making as the default an option in other OO languages.

Second, you can still create a new type that uses the closed ADT and adds other methods or different implementations. So you aren't really restricted in that way. Again, they seem to formally have the same strength; what you can express in one can be expressed in the other.

The real thing is that functional programming really is a different paradigm ("pattern"). If you go into it with the expectation that it ought to be like an OO language, you'll be surprised regularly.

Answer 2

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 3

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 4

First, as counterpoint to Charlie's answer, this isn't intrinsic to functional programming. OCaml has the concept of open unions or polymorphic variants, which essentially do what you want.

As for why, I believe this choice was made for Haskell because

• this lets types be predictable - their are only a finite number of constructors for each
• it's easy to define your own types.
• many Haskell functions are polymorphic, and classes let you extend custom types to fit function parameters (think Java's Interfaces).

So if you'd rather have a data Color r b g = Red r | Blue b | Green g type, it's easy to make, and you can easily make it act like a monad or a functor or however other functions need.

Answer 5

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.

Answer 6

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 7

Another (more or less) intuitive way of looking at data types and typeclasses versus object oriented classes is the following:

A class Foo in an OO language represents both a concrete type Foo as well as the class of all Foo-types: those which are directly or indirectly derived from Foo.

In OO languages, you just happen to implicitly program against the class of Foo-types which allows you to "extend" Foo.