Abstract: I define a typeclass for functors from Kleisli categories to Hask. This class turns out having more interesting properties than I expected, encompassing various Haskell patterns such as concurrency, and monad transformers.
Monads are often described in terms of do notation.
Every bind (=<<) equates to one statement in the do block.
This is sufficient for explaining the usage of monads to newcomers.
But in terms of understanding the functionality of monads,
I think it somewhat misses the mark.
I like to think about monads in terms of composition.
Monads give you a special kind of composition called “Kleisli composition”,
written as the (<=<) operator.
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
(g <=< f) a = f a >>= g
This operator takes two functions of the form a -> m b,
and composes them monadically, passing the input to the first function,
then binding the output to g.
This form of function (a -> m b) is called a “Kleisli arrow”.
Compare the type signature of this to ordinary function composition.
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
(.) :: (b -> c) -> (a -> b) -> (a -> c)
They’re doing very similar jobs,
except that (<=<) allows functions to perform monadic effects.
Just as function composition is core to producing pure programs,
Kleisli composition is core to producing monadic programs.
In fact, we have some nice category theory to back this up. I’m not going to give a crash course of category theory here, but I’m only going to use some very basic categories. The only prerequisite knowledge for this post is knowing what a category is, how the category of sets works (more accurately, the category Hask), and how functors work.
As we’ve just seen, Kleisli arrows compose.
This composition forms a proper category,
called a (you guessed it) “Kleisli category”.
There is one Kleisli category for every monad instance,
which I will denote as Kleisli m (given a monad m).
The objects in this category are the same as the objects in Hask:
types in Haskell.
But the morphisms are Kleisli arrows.
So an arrow in Kleisli m that points from A to B
is a function of type A -> m B.
Composition in Kleisli m is the Kleisli composition operator (<=<),
and the identity morphism (which has type a -> m a) is return.
The laws are held trivially, so I won’t go into a proof here.
This category is useful on its own.
Composing Kleisli arrows represents creating monadic programs.
There’s a Category instance
in base for it that’s pretty useful.
But Kleisli arrows don’t give you anything that you can’t get from the monad.
So they’re really only a notational feature.
They don’t let you do anything you couldn’t do without them.
Kleisli Functors
After experimenting with the Data.Align class,
I realized a common pattern in the way we use monads.
We will often form functors from Kleisli m to Hask.
These aren’t traditional Haskell functors.
These map Kleisli arrows to Hask arrows.
class Monad m => KleisliFunctor m f where
kmap :: (a -> m b) -> f a -> f b
Terminology: I will use the phrasing “f is a Kleisli functor of m”
to explain that there is an instance of KleisliFunctor m f.
Before I get into the use-cases, it’s important to go over the laws, which are satisfyingly simple. They’re just the laws of functors between categories.
kmap return = id
kmap g . kmap f = kmap (g <=< f)
Mapping the identity arrow of Kleisli m results in the identity arrow of Hask.
And composing two mappings is equivalent to mapping a Kleisli composition.
This actually means Functor is a superclass of f in KleisliFunctor,
which I’ll explain later.
class (Monad m, Functor f) => KleisliFunctor m f where
kmap :: (a -> m b) -> f a -> f b
Conceptually, this class means you can map Kleisli arrows over f,
and f will happily absorb the monad m into itself.
Somehow, f preserves the powers of m,
and hides them behind its own interface.
This admits one extremely obvious instance.
A monad m should present a good candidate for a Kleisli functor of itself,
since it trivially preserves its own powers behind its own interface.
instance Monad m => KleisliFunctor m m where
kmap f a = a >>= f
Any monad can map its own Kleisli arrows easily enough. It’s the same as binding. This probably shouldn’t be surprising. The Kleisli category wouldn’t be very useful if we couldn’t use it from Hask, which is exactly what this represents.
Kleisli Maybe
Another obvious example is Kleisli functors of Maybe.
kmap :: (a -> Maybe b) -> f a -> f b
Look familiar?
It’s pretty common to filter elements by mapping them to Maybe.
The reflex FRP library even has a class for Kleisli functors of Maybe
(though it’s only there for domain-specific reason,
despite being a very general tool).
You could probably even make parser combinator monads into this kind of functor.
Monad Transformers
I also noticed that when the functor supports pure :: a -> f a,
it seems to generalize transformers.
Or at least, it can implement a lift operation for lifting m into f.
lift :: (KleisliFunctor m f, Applicative f) => m a -> f a
lift = kmap id . pure
I’m not sure what implications this has on the laws.
It seems like it means that if f is a Monad (or maybe just Applicative),
it should support laws similar to the MonadTrans laws.
Here’s an attempt at a law, but I don’t have much confidence in it.
Update: I fixed a type error in the laws I had and reduced them to one.
Still not all that confident in this being correct though.
kmap f (pure a) = kmap id (pure (f a))
Any given MonadTrans instance forms a KleisliFunctor instance,
supporting the theory that Kleisli functors are a more useful abstraction.
instance (MonadTrans t, Monad m, Monad (t m)) => KleisliFunctor m (t m) where
kmap f a = a >>= (lift . f)
Concurrency
I recently wrote about an abstraction over Async.Concurrently.
In the accompanying reddit thread,
some people pointed out that concurrency probably wasn’t the right abstraction.
The idea was that some monads pair with a similar applicative functor
to achieve some interesting extra behavior.
My example was Concurrently from the async package.
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
import qualified Control.Concurrent.Async as Async
class (Applicative f, Monad m) => Concurrently f m | f -> m, m -> f where
runConcurrently :: f a -> m a
runSequentially :: m a -> f a
instance Concurrently Async.Concurrently IO where
runConcurrently = Async.runConcurrently
runSequentially = Async.Concurrently
With it, I could define some useful functions for concurrent traversal.
traverse' :: (Concurrently f m, Traversable t) => (a -> m b) -> t a -> m (t b)
traverse' f = runConcurrently . traverse (runSequentially . f)
As it turns out, KleisliFunctor admits half of the Concurrently class.
The lift function I defined before is the runSequentially function.
And traverse' ends up returning f instead of m,
which is perhaps more natural, since it means no fundep is needed,
and the type signature visibly uses both parts of the abstraction.
traverse' :: (Traversable t, KleisliFunctor m f, Applicative f)
=> (a -> m b) -> t a -> f (t b)
traverse' f = traverse (kmap f . pure)
for' :: (Traversable t, KleisliFunctor m f, Applicative f)
=> t a -> (a -> m b) -> f (t b)
for' = flip traverse'
instance KleisliFunctor IO Async.Concurrently where
kmap f a = Async.Concurrently (Async.runConcurrently a >>= f)
x :: IO ()
x = Async.runConcurrently $ for' [1..100] $ \n -> do
-- I can perform arbitrary IO.
-- Each iteration of this loop will be running concurrently.
print n
We get to write monadic code, and have it execute according to the optimizations of the Kleisli functor.
One of the examples from the reddit thread was the validation applicative.
data Validation e a
= Failure e
| Success a
deriving (Eq, Ord, Show, Functor)
instance Semigroup e => Applicative (Validation e) where
pure = Success
Failure e1 <*> Failure e2 = Failure (e1 <> e2)
Failure e1 <*> Success _ = Failure e1
Success _ <*> Failure e2 = Failure e2
Success f <*> Success a = Success (f a)
Validation is equivalent to Either,
except that its applicative instance gives you more information.
It would break the (<*>) = ap law, so it can’t be a monad.
But it still would be nice to perform Either-style monadic effects
until we want to switch to Validation.
This is a pretty good candidate for KleisliFunctor.
instance KleisliFunctor (Either e) (Validation e) where
kmap f (Success a) = either Failure Success $ f a
kmap _ (Failure e) = Failure e
f :: [Int] -> Validation [String] Int
f ns = sum $ for' ns $ \n -> do
-- Any errors thrown with `Left` will short circuit this computation.
-- But all the other iterations of the loop will also yield their errors.
...
Misc. Properties
The KleisliFunctor class comes with some pretty novel properties,
which I’d like to briefly mention.
- If you give it
Identityas the monad, you recover theFunctorclass. This is becauseKleisli Identityis equivalent to Hask, so a functor between the two is still an endofunctor of Hask.
{-# LANGUAGE ConstraintKinds #-}
type Functor' = KleisliFunctor Identity
- If you give it
Const aas the functor, you get a Kleisli functor of any monad. Of course it’s a relatively useless Kleisli functor.
instance Monad m => KleisliFunctor m (Const a) where
kmap _ (Const a) = Const a
- And finally, as I mentioned earlier,
all Kleisli functors make regular Hask functors,
suggesting that
Functorshould be a superclass ofKleisliFunctor.
{-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
fmapDefault :: forall m f a b. KleisliFunctor m f => (a -> b) -> f a -> f b
fmapDefault f = kmap ((return @ m) . f)
The Dual of Kleisli Functors
I mentioned that KleisliFunctor gives us one half of
the Concurrently class I wrote about in the past.
In an attempt to find the other half,
I decided to look for duals to KleisliFunctor.
If a Kleisli functor is a functor from Kleisli m to Hask,
then the dual is a functor from Hask to Kleisli m.
So we get an obvious CoKleisliFunctor class to describe this.
class Monad m => CoKleisliFunctor m g where
-- | Laws:
-- cokmap id = return
-- cokmap (g . f) = cokmap g <=< cokmap f
cokmap :: (a -> b) -> g a -> m (g b)
Unfortunately, this class seems much less useful.
It’s hard to imagine any usage of m that isn’t clearly equivalent to return.
The one example I can think of is using m = IO to process the pure
function on a collection g of elements a concurrently.
But even this isn’t promising.
Now, when you have two functors going opposite directions, you’ll often find they form an adjunction. I won’t go into what that means mathematically, but the implications will be perhaps more obvious with some code.
class (KleisliFunctor m f, CoKleisliFunctor m g)
=> KleisliAdjunction m f g
| f g -> m where
unit :: a -> f (g a)
counit :: g (f a) -> m a
Basically, for two functors of opposite direction, they are adjoint if
we can construct them in one category, and destroy them in the other.
“Destroying” things in a Kleisli category is nice.
It lets our return type use m,
meaning “destroying” is more like “converting” to m’s effect system.
This counit might represent the other half of my Concurrently class.
It seems like you can use it to turn fs back into ms.
I’m just having trouble finding any instances of g to do this with.
The crazy thing about adjunctions is that when you have one, you’re given a new monad for free.
newtype KleisliMonad m f g a = KleisliMonad { runKleisliMonad :: f (g a) }
instance (KleisliFunctor m f, CoKleisliFunctor m g)
=> Functor (KleisliMonad m f g) where
fmap f (KleisliMonad a) = KleisliMonad $ kmap @m (cokmap f) a
instance KleisliAdjunction m f g => Applicative (KleisliMonad m f g) where
pure = return
(<*>) = ap
instance KleisliAdjunction m f g => Monad (KleisliMonad m f g) where
return = KleisliMonad . unit
KleisliMonad a >>= k = KleisliMonad $
kmap (counit <=< cokmap (runKleisliMonad . k)) a
I don’t actually have any idea what this monad does.
But that’s largely because I can’t think of any instances of this adjunction.
Please let me know if you can think of one;
this monad could provide wildly interesting.
Of course, it could also prove to be no more useful than m alone,
which would be disappointing, but ultimately unsurprising.
Conclusion
To summarize:
- Kleisli functors encompass a lot of patterns.
- Removing elements from a structure is
KleisliFunctor Maybe. - Executing sequential programs concurrently
is
KleisliFunctor IO Concurrently. - Collecting errors from many computations is
KleisliFunctor Either Validation. - There’s a reasonable chance that monad transformers are just
KleisliFunctor m (t m).
- Removing elements from a structure is
- The dual of Kleisli functors is confusing.
- If there’s a useful instance of it, it could yield a pretty wild monad.
I think I’ve opened about as many questions as I’ve answered, so I look forward to hearing people’s thoughts on this!