This post is inspired by this recent complaint Martin Escardo: "{- I think I am going to teach Haskell monads lik…" - Mathstodon
Monad is currently defined like this:
class Applicative m => Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
But really, we’d like to say that each Monad instance implies an Applicative instance. Like this:
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
instance Monad m => Applicative m
I’d argue we want to write such instance implications like this, because they are more intuitive in my opinion or if you don’t agree then at least it means we wouldn’t have to also write instances for Applicative and Functor manually.
But this wreaks havoc (in the form of overlapping instances). For example if you now tried to write an Applicative instance for a type manually. For example:
newtype ZipList a = ZipList [a]
instance Applicative ZipList where
pure x = ZipList (repeat x)
ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)
foo :: ZipList ()
foo = pure ()
You get an error like this:
T.hs:24:7: error: [GHC-43085]
• Overlapping instances for Applicative ZipList
arising from a use of ‘pure’
Matching instances:
instance Monad m => Applicative m -- Defined at T.hs:8:10
instance Applicative ZipList -- Defined at T.hs:16:10
• In the expression: pure ()
In an equation for ‘foo’: foo = pure ()
|
24 | foo = pure ()
| ^^^^
So it cannot choose between the implication instance and the manually written instance. But there is an easy solution to that: just require the user to explicitly state that no monad instance can ever be defined:
instance Unsatisfiable (Text "ZipList has no Monad instance") => Monad ZipList
This way the compiler can know that the implication instance cannot be used to get an instance for ZipList and can safely commit to the manually written instance. This does require the unsatisfiable instance to be in the same module as the Applicative instance. A bare Applicative instance without an accompanying unsatisfiable Monad instance should not be allowed.
In general my proposal is to add a special kind of “implication instance” of the form:
implication instance C1 a => C2 a
And require that each manual instance of the superclass (e.g. Applicative) would be accompanied by an unsatisfiable subclass (e.g. Monad) instance.
Some pre-emptive Q&As:
-
Q: If the implication instance is defined later in another module that could break existing instances. What should be done about that?
A: Only allow implication instances in the same module as the two type classes that are involved. -
Q: For some instances we can define a more performant implementation than the standard instance generated by implication from a subclass. Would that still be possible?
A: I’d say yes, these should be definable as usual but only in the same module as the subclass instance. -
Q: How does this interact with deriving?
A: I haven’t given it too much thought. I think most derived instances can be allowed without problems because they should be unique (except for GeneralizedNewtypeDeriving, DerivingVia, and DeriveAnyClass). But I think there would be little reason to use derived instances in addition to the implied instances you get automatically. -
Q: Wouldn’t this be a massive breaking change?
A: Yes, sadly. Perhaps that’s enough reason to not changeMonadin base in the foreseeable future. But we could still use this in alternative preludes. -
Q: Can’t we make the unsatisfiable instance implicit?
A: Yes, but I think that would be surprising behavior. -
Q: How does this interact with MultiParamTypeClasses and FunctionalDependencies?
A: I don’t know yet.
Here’s a full example of my proposed syntax:
class Functor f where
fmap :: (a -> b) -> f a -> f b
class Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
implication instance Applicative f => Functor f where
fmap f x = pure f <*> x
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
implication instance Monad m => Applicative m where
pure = return
p <*> q = p >>= \f -> q >>= \x -> return (f x)
-- Example instance
data List a = Nil | Cons a (List a)
append :: List a -> List a -> List a
append Nil ys = ys
append (Cons x xs) ys = Cons x (append xs ys)
-- We get 'instance Functor List' and 'instance Applicative List' for free
instance Monad List where
return x = Cons x Nil
Nil >>= _ = Nil
Cons x xs >>= k = append (k x) (xs >>= k)
-- Example non-superclass instance
newtype ZipList a = ZipList [a]
-- We get 'instance Functor ZipList' for free
instance Applicative ZipList where
pure x = ZipList (repeat x)
ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)
instance Unsatisfiable (Text "ZipList has no Monad instance") => Monad ZipList
foo :: ZipList ()
foo = pure () -- no error