Extensible Haskell Type Classes

Question

I am reading a paper on dependently-typed programming and came across the following quote:

"[...] in contrast to Haskell's type classes, the data type [...] is closed", in the sense that one cannot add new types to the universe without extending the data type.

My newbie question is: in what sense are Haskell type classes open? How are they extensible? Also, what are the type-theoretical consequences of having this property (open vs closed)?

Thank you!

Answer 1

Given a type class like:

class Monoid m where
    mempty  :: m
    mappend :: m -> m -> m

... it is (basically) implemented under the hood as a dictionary type:

data Monoid m = Monoid
    { mempty  :: m
    , mappend :: m -> m -> m
    }

Instances like:

instance Monoid [a] where
    mempty  = []
    mappend = (++)

... get translated to dictionaries:

listIsAMonoid :: Monoid [a]
listIsAMonoid = Monoid
    { mempty  = []
    , mappend = (++)
    }

... and the compiler consults above dictionary whenever you use lists in their capacity as Monoids.

This brings us to your questions:

in what sense are Haskell type classes open? How are they extensible?

They are open in the same sense that polymorphic values are open. We have some polymorphic data type:

data Monoid m = ...

... and we can instantiate the polymorphic m type variable to any type where we can provide suitable values for the mempty and mappend fields.

Answer 2

Type classes are open, because you can make arbitrary type an instance of it. When you create type class you specify interface, but not the types which belong to it. Then in any code which includes typeclass definition you can make your type instance of it providing necessary functions from interface using instance TypeClass type of syntax.

Answer 3

Type classes are "open" because they can always have more types added to them "after the fact" by adding more instance declarations. This can even be done in "client" code that merely uses the module containing the type class.

The key point is that I can write code that operates on values with some type-class constraint, and that same code with no modification can be used on types that weren't in existence when I wrote the type class.

Concrete data types in Haskell are "closed" in that this cannot happen. If I write code that operates on members a specific data type (even if it's polymorphic), then there's no way you can use that code to operate on new kinds of thing I hadn't thought of unless you're able to modify the type (which then probably requires modifying all the places where it is used).

Answer 4

Ralf Laemmel has some very good video lectures on Channel9 about this - highly recommended.