Nested monads by Mark Seemann
You can stack some monads in such a way that the composition is also a monad.
This article is part of a series of articles about functor relationships. In a previous article you learned that nested functors form a functor. You may have wondered if monads compose in the same way. Does a monad nested in a monad form a monad?
As far as I know, there's no universal rule like that, but some monads compose well. Fortunately, it's been my experience that the combinations that you need in practice are among those that exist and are well-known. In a Haskell context, it's often the case that you need to run some kind of 'effect' inside IO. Perhaps you want to use Maybe or Either nested within IO.
In .NET, you may run into a similar need to compose task-based programming with an effect. This happens more often in F# than in C#, since F# comes with other native monads (option and Result, to name the most common).
Abstract shape #
You'll see some real examples in a moment, but as usual it helps to outline what it is that we're looking for. Imagine that you have a monad. We'll call it F in keeping with tradition. In this article series, you've seen how two or more functors compose. When discussing the abstract shapes of things, we've typically called our two abstract functors F and G. I'll stick to that naming scheme here, because monads are functors (that you can flatten).
Now imagine that you have a value that stacks two monads: F<G<T>>. If the inner monad G is the 'right' kind of monad, that configuration itself forms a monad.
In the diagram, I've simply named the combined monad FG, which is a naming strategy I've seen in the real world, too: TaskResult, etc.
As I've already mentioned, if there's a general theorem that says that this is always possible, I'm not aware of it. To the contrary, I seem to recall reading that this is distinctly not the case, but the source escapes me at the moment. One hint, though, is offered in the documentation of Data.Functor.Compose:
"The composition of applicative functors is always applicative, but the composition of monads is not always a monad."
Thankfully, the monads that you mostly need to compose do, in fact, compose. They include Maybe, Either, State, Reader, and Identity (okay, that one maybe isn't that useful). In other words, any monad F that composes with e.g. Maybe, that is, F<Maybe<T>>, also forms a monad.
Notice that it's the 'inner' monad that determines whether composition is possible. Not the 'outer' monad.
For what it's worth, I'm basing much of this on my personal experience, which was again helpfully guided by Control.Monad.Trans.Class. I don't, however, wish to turn this article into an article about monad transformers, because if you already know Haskell, you can read the documentation and look at examples. And if you don't know Haskell, the specifics of monad transformers don't readily translate to languages like C# or F#.
The conclusions do translate, but the specific language mechanics don't.
Let's look at some common examples.
TaskMaybe monad #
We'll start with a simple, yet realistic example. The article Asynchronous Injection shows a simple operation that involves reading from a database, making a decision, and potentially writing to the database. The final composition, repeated here for your convenience, is an asynchronous (that is, Task-based) process.
return await Repository.ReadReservations(reservation.Date) .Select(rs => maîtreD.TryAccept(rs, reservation)) .SelectMany(m => m.Traverse(Repository.Create)) .Match(InternalServerError("Table unavailable"), Ok);
The problem here is that TryAccept returns Maybe<Reservation>, but since the overall workflow already 'runs in' an asynchronous monad (Task), the monads are now nested as Task<Maybe<T>>.
The way I dealt with that issue in the above code snippet was to rely on a traversal, but it's actually an inelegant solution. The way that the SelectMany invocation maps over the Maybe<Reservation> m is awkward. Instead of composing a business process, the scaffolding is on display, so to speak. Sometimes this is unavoidable, but at other times, there may be a better way.
In my defence, when I wrote that article in 2019 I had another pedagogical goal than teaching nested monads. It turns out, however, that you can rewrite the business process using the Task<Maybe<T>> stack as a monad in its own right.
A monad needs two functions: return and either bind or join. In C# or F#, you can often treat return as 'implied', in the sense that you can always wrap new Maybe<T> in a call to Task.FromResult. You'll see that in a moment.
While you can be cavalier about monadic return, you'll need to explicitly implement either bind or join. In this case, it turns out that the sample code base already had a SelectMany implementation:
public static async Task<Maybe<TResult>> SelectMany<T, TResult>( this Task<Maybe<T>> source, Func<T, Task<Maybe<TResult>>> selector) { Maybe<T> m = await source; return await m.Match( nothing: Task.FromResult(new Maybe<TResult>()), just: x => selector(x)); }
The method first awaits the Maybe value, and then proceeds to Match on it. In the nothing case, you see the implicit return being used. In the just case, the SelectMany method calls selector with whatever x value was contained in the Maybe object. The result of calling selector already has the desired type Task<Maybe<TResult>>, so the implementation simply returns that value without further ado.
This enables you to rewrite the SelectMany call in the business process so that it instead looks like this:
return await Repository.ReadReservations(reservation.Date) .Select(rs => maîtreD.TryAccept(rs, reservation)) .SelectMany(r => Repository.Create(r).Select(i => new Maybe<int>(i))) .Match(InternalServerError("Table unavailable"), Ok);
At first glance, it doesn't look like much of an improvement. To be sure, the lambda expression within the SelectMany method no longer operates on a Maybe value, but rather on the Reservation Domain Model r. On the other hand, we're now saddled with that graceless Select(i => new Maybe<int>(i)).
Had this been Haskell, we could have made this more succinct by eta reducing the Maybe case constructor and used the <$> infix operator instead of fmap; something like Just <$> create r. In C#, on the other hand, we can do something that Haskell doesn't allow. We can overload the SelectMany method:
public static Task<Maybe<TResult>> SelectMany<T, TResult>( this Task<Maybe<T>> source, Func<T, Task<TResult>> selector) { return source.SelectMany(x => selector(x).Select(y => new Maybe<TResult>(y))); }
This overload generalizes the 'pattern' exemplified by the above business process composition. Instead of a specific method call, it now works with any selector function that returns Task<TResult>. Since selector only returns a Task<TResult> value, and not a Task<Maybe<TResult>> value, as actually required in this nested monad, the overload has to map (that is, Select) the result by wrapping it in a new Maybe<TResult>.
This now enables you to improve the business process composition to something more readable.
return await Repository.ReadReservations(reservation.Date) .Select(rs => maîtreD.TryAccept(rs, reservation)) .SelectMany(Repository.Create) .Match(InternalServerError("Table unavailable"), Ok);
It even turned out to be possible to eta reduce the lambda expression instead of the (also valid, but more verbose) r => Repository.Create(r).
If you're interested in the sample code, I've pushed a branch named use-monad-stack to the GitHub repository.
Not surprisingly, the F# bind function is much terser:
let bind f x = async { match! x with | Some x' -> return! f x' | None -> return None }
You can find that particular snippet in the code base that accompanies the article Refactoring registration flow to functional architecture, although as far as I can tell, it's not actually in use in that code base. I probably just added it because I could.
You can find Haskell examples of combining MaybeT with IO in various articles on this blog. One of them is Dependency rejection.
TaskResult monad #
A similar, but slightly more complex, example involves nesting Either values in asynchronous workflows. In some languages, such as F#, Either is rather called Result, and asynchronous workflows are modelled by a Task container, as already demonstrated above. Thus, on .NET at least, this nested monad is often called TaskResult, but you may also see AsyncResult, AsyncEither, or other combinations. Depending on the programming language, such names may be used only for modules, and not for the container type itself. In C# or F# code, for example, you may look in vain after a class called TaskResult<T>, but rather find a TaskResult static class or module.
In C# you can define monadic bind like this:
public static async Task<Either<L, R1>> SelectMany<L, R, R1>( this Task<Either<L, R>> source, Func<R, Task<Either<L, R1>>> selector) { if (source is null) throw new ArgumentNullException(nameof(source)); Either<L, R> x = await source.ConfigureAwait(false); return await x.Match( l => Task.FromResult(Either.Left<L, R1>(l)), selector).ConfigureAwait(false); }
Here I've again passed the eta-reduced selector straight to the right case of the Either value, but r => selector(r) works, too.
The left case shows another example of 'implicit monadic return'. I didn't bother defining an explicit Return function, but rather use Task.FromResult(Either.Left<L, R1>(l)) to return a Task<Either<L, R1>> value.
As is the case with C#, you'll also need to add a special overload to enable the syntactic sugar of query expressions:
public static Task<Either<L, R1>> SelectMany<L, U, R, R1>( this Task<Either<L, R>> source, Func<R, Task<Either<L, U>>> k, Func<R, U, R1> s) { return source.SelectMany(x => k(x).Select(y => s(x, y))); }
You'll see a comprehensive example using these functions in a future article.
In F# I'd often first define a module with a few functions including bind, and then use those implementations to define a computation expression, but in one article, I jumped straight to the expression builder:
type AsyncEitherBuilder () = // Async<Result<'a,'c>> * ('a -> Async<Result<'b,'c>>) // -> Async<Result<'b,'c>> member this.Bind(x, f) = async { let! x' = x match x' with | Success s -> return! f s | Failure f -> return Failure f } // 'a -> 'a member this.ReturnFrom x = x let asyncEither = AsyncEitherBuilder ()
That article also shows usage examples. Another article, A conditional sandwich example, shows more examples of using this nested monad, although there, the computation expression is named taskResult.
Stateful computations that may fail #
To be honest, you mostly run into a scenario where nested monads are useful when some kind of 'effect' (errors, mostly) is embedded in an I/O-bound computation. In Haskell, this means IO, in C# Task, and in F# either Task or Async.
Other combinations are possible, however, but I've rarely encountered a need for additional nested monads outside of Haskell. In multi-paradigmatic languages, you can usually find other good designs that address issues that you may occasionally run into in a purely functional language. The following example is a Haskell-only example. You can skip it if you don't know or care about Haskell.
Imagine that you want to keep track of some statistics related to a software service you offer. If the variance of some number (say, response time) exceeds 10 then you want to issue an alert that the SLA was violated. Apparently, in your system, reliability means staying consistent.
You have millions of observations, and they keep arriving, so you need an online algorithm. For average and variance we'll use Welford's algorithm.
The following code uses these imports:
import Control.Monad import Control.Monad.Trans.State.Strict import Control.Monad.Trans.Maybe
First, you can define a data structure to hold the aggregate values required for the algorithm, as well as an initial, empty value:
data Aggregate = Aggregate { count :: Int, meanA :: Double, m2 :: Double } deriving (Eq, Show) emptyA :: Aggregate emptyA = Aggregate 0 0 0
You can also define a function to update the aggregate values with a new observation:
update :: Aggregate -> Double -> Aggregate update (Aggregate count mean m2) x = let count' = count + 1 delta = x - mean mean' = mean + delta / fromIntegral count' delta2 = x - mean' m2' = m2 + delta * delta2 in Aggregate count' mean' m2'
Given an existing Aggregate record and a new observation, this function implements the algorithm to calculate a new Aggregate record.
The values in an Aggregate record, however, are only intermediary values that you can use to calculate statistics such as mean, variance, and sample variance. You'll need a data type and function to do that, as well:
data Statistics = Statistics { mean :: Double, variance :: Double, sampleVariance :: Maybe Double } deriving (Eq, Show) extractStatistics :: Aggregate -> Maybe Statistics extractStatistics (Aggregate count mean m2) = if count < 1 then Nothing else let variance = m2 / fromIntegral count sampleVariance = if count < 2 then Nothing else Just $ m2 / fromIntegral (count - 1) in Just $ Statistics mean variance sampleVariance
This is where the computation becomes 'failure-prone'. Granted, we only have a real problem when we have zero observations, but this still means that we need to return a Maybe Statistics value in order to avoid division by zero.
(There might be other designs that avoid that problem, or you might simply decide to tolerate that edge case and code around it in other ways. I've decided to design the extractStatistics function in this particular way in order to furnish an example. Work with me here.)
Let's say that as the next step, you'd like to compose these two functions into a single function that both adds a new observation, computes the statistics, but also returns the updated Aggregate.
You could write it like this:
addAndCompute :: Double -> Aggregate -> Maybe (Statistics, Aggregate) addAndCompute x agg = do let agg' = update agg x stats <- extractStatistics agg' return (stats, agg')
This implementation uses do notation to automate handling of Nothing values. Still, it's a bit inelegant with its two agg values only distinguishable by the prime sign after one of them, and the need to explicitly return a tuple of the value and the new state.
This is the kind of problem that the State monad addresses. You could instead write the function like this:
addAndCompute :: Double -> State Aggregate (Maybe Statistics) addAndCompute x = do modify $ flip update x gets extractStatistics
You could actually also write it as a one-liner, but that's already a bit too terse to my liking:
addAndCompute :: Double -> State Aggregate (Maybe Statistics) addAndCompute x = modify (`update` x) >> gets extractStatistics
And if you really hate your co-workers, you can always visit pointfree.io to entirely obscure that expression, but I digress.
The point is that the State monad amplifies the essential and eliminates the irrelevant.
Now you'd like to add a function that issues an alert if the variance is greater than 10. Again, you could write it like this:
monitor :: Double -> State Aggregate (Maybe String) monitor x = do stats <- addAndCompute x case stats of Just Statistics { variance } -> return $ if 10 < variance then Just "SLA violation" else Nothing Nothing -> return Nothing
But again, the code is graceless with its explicit handling of Maybe cases. Whenever you see code that matches Maybe cases and maps Nothing to Nothing, your spider sense should be tingling. Could you abstract that away with a functor or monad?
Yes you can! You can use the MaybeT monad transformer, which nests Maybe computations inside another monad. In this case State:
monitor :: Double -> State Aggregate (Maybe String) monitor x = runMaybeT $ do Statistics { variance } <- MaybeT $ addAndCompute x guard (10 < variance) return "SLA Violation"
The function type is the same, but the implementation is much simpler. First, the code lifts the Maybe-valued addAndCompute result into MaybeT and pattern-matches on the variance. Since the code is now 'running in' a Maybe-like context, this line of code only executes if there's a Statistics value to extract. If, on the other hand, addAndCompute returns Nothing, the function already short-circuits there.
The guard works just like imperative Guard Clauses. The third line of code only runs if the variance is greater than 10. In that case, it returns an alert message.
The entire do workflow gets unwrapped with runMaybeT so that we return back to a normal stateful computation that may fail.
Let's try it out:
ghci> (evalState $ monitor 1 >> monitor 7) emptyA Nothing ghci> (evalState $ monitor 1 >> monitor 8) emptyA Just "SLA Violation"
Good, rigorous testing suggests that it's working.
Conclusion #
You sometimes run into situations where monads are nested. This mostly happens in I/O-bound computations, where you may have a Maybe or Either value embedded inside Task or IO. This can sometimes make working with the 'inner' monad awkward, but in many cases there's a good solution at hand.
Some monads, like Maybe, Either, State, Reader, and Identity, nest nicely inside other monads. Thus, if your 'inner' monad is one of those, you can turn the nested arrangement into a monad in its own right. This may help simplify your code base.
In addition to the common monads listed here, there are few more exotic ones that also play well in a nested configuration. Additionally, if your 'inner' monad is a custom data structure of your own creation, it's up to you to investigate if it nests nicely in another monad. As far as I can tell, though, if you can make it nest in one monad (e.g Task, Async, or IO) you can probably make it nest in any monad.
Next: Software design isomorphisms.
