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!

Zielsdorf

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.

Heliport

The type-class-as-dictionary interpretation is rather ghc-specific. There's nothing in the haskell spec that requires it, and other implementations (e.g. jhc) use a different approach. – Token

@JohnL It still is a useful mental tool for understanding the sense in which it is polymorphic. – Heliport

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.

Madaras

Thank you for the answer. I had the interface/implementation intuition before. My question was rather about whether or not one can later extend the interface given by the type class, i.e by defining another constructor for that data type outside the initial scope? – Zielsdorf

You can extend interface by defining new type class only, however there is notion of inheritance which allows you to extend it. You can use class (Interface BetterInterface) => BetterInterface type where.... Compare how Monad can be implemented as extension of Functor. – Madaras

OK, I understand. I was thinking more along the lines of open data types being such that their constructors may appear scattered, while semantically acting as if they were closed (defined in one place). – Zielsdorf

@Zielsdorf It should be noted that with Type Families data types are now open too. – Nicholasnichole

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

Gametophore