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