Type classes vs algebraic data types?

Question

I frequently start thinking about a problem in terms of type classes to be defined, and realize when I start coding that I don't need type classes and can solve my problem with algebraic data types instead, which seems more straightforward. As a result, I am wondering when type classes are necessary.

As I understand them, type classes are a way to say that certain functions exist for certain types. For example, when a type MyType is an instance of Monoid, then I can use the functions mempty :: MyType and mappend :: MyType -> MyType -> MyType, such that the monoid laws hold.

We could acheive the same with algebraic data types, by defining Monoid as a type rather than a typeclass:

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

and then say that a type MyType is a monoid by defining a new value of type Monoid MyType (which with typeclasses is done by declaring it an instance):

monoidMyType :: Monoid MyType
monoidMyType = Monoid { mempty = ...
                      , mappend = \a b -> ... }

Then, we can write functions that operate on monoids like:

dummyFun :: Monoid a -> a -> a
dummyFun m x = mempty m x

And use those functions by explicitly passing the appropriate "monoid value":

result = dummyFun monoidMyType valueOfMyType

The equivalent last two steps would happen very similarly with typeclasses:

dummyFun :: (Monoid a) => a -> a
dummyFun x = mempty x

result = dummyFun valueOfMyType

The only substantial difference that I see is that with algebraic data types, the monoid value must be passed explicitly when we call the function dummyFun. Although it is a bit more practical not to have to pass it explicitly, it doesn't look to me like a major obstacle.

In fact, I see an advantage that algebraic data types have over type classes: you can relate together types accross different functions:

data Bla a b = Bla {f1 :: a -> b, f2 :: b -> a, ...}

Doing this with typeclasses would (i believe) require using the multiple parameter type classes extension.

Is there a reason to use type classes that I'm not seeing here?

When designing software, can you interchangeably chose to use type classes or algebraic data types, or are there situations where you can't do without type classes?

Answer 1

You just invented type classes! A class is a dictionary of functions. During compilation, code like

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

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

mconcat :: Monoid a => [a] -> a
mconcat = foldr mappend

main = print $ mconcat ["foo", "bar"]

is translated into explicit dictionary-passing style.

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

list_monoid = Monoid [] (++)

mconcat :: Monoid a -> [a] -> a
mconcat monoid = foldr (mappend monoid)

main = print $ mconcat list_monoid ["foo", "bar"]

That translation is exactly the most important difference between type classes and dictionaries: classes are implicit. You don't have to explicitly pass the monoid variable around - the compiler takes care of the plumbing for you. It would be especially tedious to build composed instances like Ord a => Ord [a] by hand.

There's one other key difference between classes and dictionaries, and that's coherence. Basically, there's always at most one "best" instance to satisfy a given constraint, that instance is global and unique, and you can't override it. With dictionary-passing style, on the other hand, the function will just use whatever dictionary you passed in and there are no guarantees of uniqueness. This is sometimes good and sometimes bad.