A limitation of typeclasses

typeclass_problem.md

Its common to refer to Haskell's typeclasses as a more powerful version of traits in other languages. However, because Haskell is pure and keeps track of effects in the type system, certain traits in other languages can't be modeled as easily with typeclasses. For example, in Rust you can write a trait describing a store that performs side effects:

pub trait Store<K, V> {
    fn get(&self, key: K) -> Option<V>;
    fn set(&mut self, key: K, value: V);
}

You might think that you can model this with a multi-parameter typeclass in Haskell like this:

class Monad m => MonadStore k v m where
  get :: k -> m (Maybe v)
  set :: k -> v -> m ()

Is this equivalent to the Rust version? Not really. In the Rust version, you can have multiple Store<K, V> implementations for the same underlying "side effect monad". So you can have one store as the actual store and another as a cache and use them both in the same context:

pub fn get_with_cache<K, V, S1, S2>(main_store: S1, cache: S2, key: K) -> Option<V>
where
    K: Copy,
    S1: Store<K, V>,
    S2: Store<K, V>,
{
    match cache.get(key) {
        Some(v) => Some(v),
        None => main_store.get(key),
    }
}

You can't really do this with the Haskell typeclass version. You can only have a single global instance and since m is included, you can only have a single instance of MonadStore for m. We can sort of work around this by abstracting over transformers:

getWithCache :: (MonadStore k v m, MonadStore k v m', MonadTrans t, m ~ t m')
             => k -> m (Maybe v)
getWithCache k = lift (get k) >>= \case
  Just v  -> return $ Just v
  Nothing -> get k

However, the question now becomes "how do I run this thing?". You can no longer run this in a single monad like IO, you need to use a transformer stack where every layer is a different effect. Every slightly different set of effects requires a new newtype and you need to implement an exponential amount of typeclass instances. The problem is that we are attempting to hack around the restriction of these typeclasses that prevents you from having more than one instance per monad.

The solution is to not use typeclasses in the first place. Beginners may not realize that typeclasses were created in the first place to be a more restricted version of records of functions that trades off boilerplate for the rigidity of unique global instances. For category theory based code, unique global instances are a feature, not a problem and the reduction of boilerplate is crucial to writing pure code. Languages without typeclasses like OCaml, tend to have so much boilerplate with lawful code that it becomes impractical to work with. However, just because typeclasses are useful doesn't mean we have to use them for everything. For implementing this Store trait, we really want to work with multiple instances in the same monad so we write it as a record of functions:

data Store k v m = Store
  { get :: k -> m (Maybe v)
  , set :: k -> v -> m ()
  }

Now we can easily work with multiple Store values in the same monad and implement the Rust version:

getWithCache :: Monad m => Store k v m -> Store k v m -> k -> m (Maybe v)
getWithCache store cache k = get cache k >>= \case
  Just v  -> return $ Just v
  Nothing -> get store k