Monthly Archives: September 2022

Monadology 0.1

Monadology is intended as a collection of the best ideas in monad-related classes and types, with a focus on correctness and elegance, and theoretical understanding, rather than practical performance. I am interested in hearing further ideas, so at least initially expect a lot of change version-to-version.

Re-exported Transformers

Monadology is built on the existing transformers package. It re-exports most of it. (It does not re-export ListT).

Result

This general-purpose “result” monad represents either success or failure, of any type. This sort of thing is so useful it could have been in base, but it isn’t.

data Result e a
    = SuccessResult a
    | FailureResult e

Of course, it’s isomorphic to Either. But whereas Either has a more general-purpose “symmetrical” feel, Result is more intelligible to the reader as a monad.

Exceptions

Monadology makes two separate approaches to exceptions: one type and many types. For example, for the IO monad, there are many different exception types that can be both thrown and caught. But there is also the one type SomeException that represents all the possible exceptions.

Many Types

For the many-types approach, Monadology simply provides MonadThrow and MonadCatch classes, along with various functions:

class Monad m => MonadThrow e m where
    throw :: forall a. e -> m a

class MonadThrow e m => MonadCatch e m where
    catch :: forall a. m a -> (e -> m a) -> m a

One Type

In principle, every monad m has a single type of all the exceptions it can throw and catch. For this approach, this type is named Exc m:

class Monad m => MonadException m where
    type Exc m :: Type
    throwExc :: Exc m -> m a
    catchExc :: m a -> (Exc m -> m a) -> m a

type Exc Identity = Void
type Exc ((->) r) = Void
type Exc Maybe = ()
type Exc (Result e) = e
type Exc (ExceptT e m) = Either e (Exc m)
type Exc (StateT s m) = Exc m
type Exc IO = SomeException

Functions such as finally and bracket, that make no reference to any particular exception type, make use of this to ensure that they work for all exceptions that can be thrown.

Composing Monads

You can compose two functors to get a functor. And you can compose two applicative functors to get an applicative functor. But, famously, you cannot compose two monads to get a monad.

At least, you cannot in general. But you can, of course, in certain cases. And we can capture the most useful cases by specifying the constraints we need on one of the monads so as to leave the other unconstrained.

Inner Monad

MonadInner is just the right constraint on the inner monad so as to compose with any outer monad to get a monad.

class (Traversable m, Monad m) => MonadInner m where
    retrieveInner :: forall a. m a -> Result (m Void) a

newtype ComposeInner inner outer a = MkComposeInner (outer (inner a))

instance (MonadInner inner, Monad outer) => Monad (ComposeInner inner outer)
instance MonadInner inner => MonadTrans (ComposeInner inner)

Essentially, inner a must be isomorphic to Either P (Q,a) for some P, Q. If you examine the structure of the WriterT, ExceptT, and MaybeT monad transformers, you’ll see that they are cases of this composition pattern.

Outer Monad

MonadOuter is just the right constraint on the outer monad so as to compose with any inner monad to get a monad.

newtype WExtract m = MkWExtract (forall a. m a -> a)

class Monad m => MonadOuter m where
    getExtract :: m (WExtract m)

newtype ComposeOuter outer inner a = MkComposeOuter (outer (inner a))

instance (MonadOuter outer, Monad inner) => Monad (ComposeOuter outer inner)
instance MonadOuter outer => MonadTrans (ComposeOuter outer)

Essentially, outer a must be isomorphic to P -> a for some P. If you examine the structure of the ReaderT monad transformer, you’ll see that it’s a case of this composition pattern.

Lifecycles

LifecycleT is a monad transformer for managing the closing of opened resources, such as file handles, database sessions, GUI windows, and the like. You can think of it as a conceptually simpler version of ResourceT.

The actual code is slightly different in the contents of the MVar, but it basically looks like this:

newtype LifecycleT m a = MkLifecycleT (MVar (IO ()) -> m a)

runLifecycle :: (MonadException m, MonadTunnelIO m) => LifecycleT m a -> m a

lifecycleOnClose :: MonadAskUnliftIO m => m () -> LifecycleT m ()

type Lifecycle = LifecycleT IO -- the most common usage

That MVar simply stores all the “close” operations to be run at the end of each “lifecycle” when called by runLifecycle, in reverse order of their opening. You can add your own close operations with lifecycleOnClose.

Of course you may be thinking, what if I want to close things in a different order? For example, GUI windows get closed when the close box is clicked, not in the reverse order of opening.

For this you want to get a closer function:

lifecycleGetCloser :: MonadIO m => LifecycleT m a -> LifecycleT m (a, IO ())

For example,

newGUIWindow :: Lifecycle Window

makeMyWindow :: Lifecycle Window
makeMyWindow = do
    (window,closer) <- lifecycleGetCloser newGUIWindow
    lift $ onCloseBoxClicked window closer
    return window

Here, closer is an idempotent operation that will call the closer of newGUIWindow, that is, to close the window. Subsequent calls do nothing. It also gets called at the end of the lifecycle, to ensure that the window is eventually closed if it hasn’t been already.

Also, you may come across certain functions that make use of the “with” pattern, to manage opening and closing. Here are a couple from the base library:

withFile :: FilePath -> IOMode -> (Handle -> IO r) -> IO r

withBinaryFile :: FilePath -> IOMode -> (Handle -> IO r) -> IO r

Monadology is capable of “unpicking” this pattern coroutine-style, and converting it to a Lifecycle:

lifecycleWith ::  (forall r. (a -> IO r) -> IO r) -> Lifecycle a

fileHandle :: FilePath -> IOMode -> Lifecycle Handle
fileHandle path mode = lifecycleWith $ withFile path mode

Coroutines

Speaking of coroutines, Monadology has a class for that.

class Monad m => MonadCoroutine m where
    coroutineSuspend :: ((p -> m q) -> m r) -> CoroutineT p q m r

This is experimental, as the only useful instances I’ve come across are monads based on IO, which supports coroutines by using threads.

The CoroutineT transformer is a special case of the StepT transformer, which is for step-by-step execution.

Transitive Constraints

For many transformers, certain constraints on a monad are transitive to the transformed monad. For example:

Monad m => Monad (ReaderT r m)
(MonadPlus m, Monoid w) => MonadPlus (WriterT w m)
MonadIO m => MonadIO (ExceptT m)

Monadology has a class for this:

class TransConstraint c t where
    hasTransConstraint :: forall m. c m => Dict (c (t m))

instance TransConstraint Monad (ReaderT r)
instance Monoid w => TransConstraint MonadPlus (WriterT w)
instance TransConstraint MonadIO ExceptT

Why not just use GHC’s QuantifiedConstraints extension? Because GHC has issues satisfying quantified constraints. So there’s an explicit class instead.

Tunnelling, Hoisting and Commuting

Tunnelling allows you to manipulate monads underneath a transformer. Each tunnellable transformer is associated with a tunnel monad, that represents the “effect” of the transformer.

type p --> q = forall a. p a -> q a

class (MonadTrans t, TransConstraint Monad t) => MonadTransHoist t where
    hoist :: forall m1 m2. (Monad m1, Monad m2) =>
        (m1 --> m2) -> t m1 --> t m2

class (MonadTransHoist t, MonadInner (Tunnel t)) => MonadTransTunnel t where
    type Tunnel t :: Type -> Type
    tunnel :: forall m r. Monad m =>
        ((forall m1 a. Monad m1 => t m1 a -> m1 (Tunnel t a)) -> m (Tunnel t r)) -> t m r

Tunnel monads are, curiously enough, always instances of the aforementioned MonadInner. For example:

type Tunnel (ReaderT s) = Identity
type Tunnel (WriterT w) = (,) w
type Tunnel (StateT s) = (,) (Endo s)
type Tunnel MaybeT = Maybe
type Tunnel (ExceptT e) = Either e
type Tunnel (ComposeInner inner) = inner
type Tunnel (ComposeOuter outer) = Identity

(This is essentially a correction and generalisation of MonadTransControl.)

It’s straightforward to derive hoisting from tunnelling, which is why MonadTransHoist is a superclass of MonadTransTunnel. And furthermore, you can commute two transformers in a stack, if you can commute their tunnel monads (which you always can).

commuteTWith :: (MonadTransTunnel ta, MonadTransTunnel tb, Monad m) =>
    (forall r. Tunnel tb (Tunnel ta r) -> Tunnel ta (Tunnel tb r)) ->
    ta (tb m) --> tb (ta m)

commuteInner :: (MonadInner m, Applicative f) => m (f a) -> f (m a)

commuteT :: (MonadTransTunnel ta, MonadTransTunnel tb, Monad m) =>
    ta (tb m) --> tb (ta m)
commuteT = commuteTWith commuteInner

Unlifting

Monadology has two classes for unlifting transformers.

type Unlift c t = forall m. c m => t m --> m
newtype WUnlift c t = MkWUnlift (Unlift c t)

class (...) => MonadTransUnlift t where
    -- | lift with an unlifting function that accounts for the transformer's effects (using MVars where necessary)
    liftWithUnlift :: forall m r. MonadIO m =>
        (Unlift MonadTunnelIOInner t -> m r) -> t m r
   -- | return an unlifting function that discards the transformer's effects (such as state change or output)
    getDiscardingUnlift :: forall m. Monad m =>
        t m (WUnlift MonadTunnelIOInner t)

-- | A transformer that has no effects (such as state change or output)
class MonadTransUnlift t => MonadTransAskUnlift t where
    askUnlift :: forall m. Monad m => t m (WUnlift Monad t)

Only ReaderT (and IdentityT) and the like can be instances of the more restrictive MonadTransAskUnlift.

However, MonadTransUnlift also has instances for StateT and WriterT. These allow correct unlifting without discarding effects (though another function is provided if you want discarding). How is this possible? Magic! MVars! Unlifting StateT simply holds the state in an MVar. Unlifting WriterT uses an MVar to collect effects at the end of each unlift.

Using MVars also makes everything thread-safe. Here’s an example:

longComputation1 :: IO ()
longComputation2 :: IO ()

ex :: StateT Int IO ()
ex = liftWithUnlift $ \unlift -> do
    a <- async $ do
        longComputation1
        unlift $ modify succ
    longComputation2
    unlift $ modify succ
    wait a

Here, longComputation1 and longComputation2 can run in parallel, in different threads. But unlift forces synchronisation, meaning that the modify statements never overlap. Instead, state is passed from one to the other. So ex is guaranteed to add two to its state.

As mentioned earlier, the tunnel monads of transformers in MonadTransTunnel are all instances of MonadInner. But if the transformer is an instance of MonadTransUnlift, its tunnel monad will be an instance of the stricter class MonadExtract. And if the transformer is an instance of MonadTransAskUnlift, then its tunnel monad will be an instance of MonadIdentity, monads equivalent to the identity monad.

The Same, but Monads Relative to IO

Often a monad can be understood as some transformer over IO. In such a case, we might want to know the properties of that transfomer.

Monadology provides classes for such monads, that mirror classes for transformers:

MonadTransMonadIO
MonadTransHoistMonadHoistIO
MonadTransTunnelMonadTunnelIO
MonadTransUnliftMonadUnliftIO
MonadTransAskUnliftMonadAskUnliftIO

Composing and Stacking Transformers

The ComposeT transformer allows you to compose monad transformers (unlike composing monads, there is no restriction on this). Generally speaking, if t1 and t2 both have some property, then ComposeT t1 t2 will have it too.

The StackT transformer allows you to deal with whole stacks of transformers, parameterized by a list of their types:

type TransKind = (Type -> Type) -> (Type -> Type)

type StackT :: [TransKind] -> TransKind
newtype StackT tt m a = MkStackT (ApplyStack tt m a)

type ApplyStack :: forall k. [k -> k] -> k -> k
type family ApplyStack f a where
    ApplyStack '[] a = a
    ApplyStack (t ': tt) a = t (ApplyStack tt a)

Monad Data

The concepts of “reader”, “writer”, and “state” monads each imply a kind of data: readers have parameters, writers have products, and states have references. And pretty much any monad has exceptions. So, why not make that data explicit, so we can manipulate it directly?

data Param m a = MkParam
    { paramAsk :: m a
    , paramWith :: a -> m --> m
    }

readerParam :: Monad m => Param (ReaderT r m) r

data Ref m a = MkRef
    { refGet :: m a
    , refPut :: a -> m ()
    }

stateRef :: Monad m => Ref (StateT s m) s

data Prod m a = MkProd
    { prodTell :: a -> m ()
    , prodListen :: forall r. m r -> m (r, a)
    }

writerProd :: Monad m => Prod (WriterT w m) w

data Exn m e = MkExn
    { exnThrow :: forall a. e -> m a
    , exnCatch :: forall a. m a -> (e -> m a) -> m a
    }

allExn :: forall m. MonadException m => Exn m (Exc m)
someExn :: forall e m. MonadCatch e m => Exn m e

Parameters and references can be mapped by lenses. Not so much products, though there is one thing we can do with them.

mapParam :: Functor m => Lens' a b -> Param m a -> Param m b

mapRef :: Monad m => Lens' a b -> Ref m a -> Ref m b

foldProd :: (Applicative f, Foldable f, Applicative m) => Prod m a -> Prod m (f a)

Of course, other monads have their own references:

ioRef :: IORef a -> Ref IO a

stRef :: STRef s a -> Ref (ST s) a 

Odd Stuff

ReaderStateT and TransformT are odd things that I make use of elsewhere, but don’t really understand. Both of them convert Params into Refs.

newtype WRaised f m = MkWRaised (forall a. f a -> m a)
type ReaderStateT f m = StateT (WRaised f m) m
readerStateParamRef :: Monad m => Param f a -> Ref (ReaderStateT f m) a

newtype TransformT m a = MkTransformT (forall r. (a -> m r) -> m r)
transformParamRef :: Monad m => Param m a -> Ref (TransformT m) a

Not Included

  • ListT. This does not transform every monad to a monad, so is not a monad transformer.
  • Any notion of a “base” monad. While every transformer stack must logically have some base monad, the concept is non-parametric as transformed monads cannot be base monads.
  • Lifted “batteries” functions. Just use lift.
  • An effect system.

And also…

I have substantially expanded, cleaned up and reorganised witness, my package for type witnesses, which Monadology makes use of. I have also published type-rig, which provides the Summable and Productable classes used for monad data.

— Ashley Yakeley