Everything is a Monad
Uniting various programming concepts by tracking down the pattern behind the mess
Have you ever written expressions like (await t).Select(x => x?.Foo())? Fun fact: await (async. programming), Select (list processing) and ?. (null-conditional) are really the same thing. Language designers could make this expression look like t???.Foo() or (await each nullable t).Foo(). Read on to find out why and how. Your feedback is highly appreciated!
Motivation
Consider the following, seemingly independent, programming concepts:
- rich list processing, e.g. LINQ in C#, list comprehension, etc.
- side-effects/impurity, e.g. explicit in Haskell, implicit in imperative PLs
- error handling, e.g. exceptions in Java vs C#, returning errors in Go
- async programming, e.g.
async/awaitin JS/C#, or via callbacks - nullable lifting, e.g. null-conditional operators in C#,
Maybein Haskell - probability distributions as 1st-class citizens, e.g. in WebPPL or HackPPL
Some concepts require dedicated syntax and heavy lifting, others are supported seamlessly and implicitly. I will show that all those concepts have the same underlying pattern. So why the inconsistent implementation strategies? User expectation, tough language design considerations and PL history may of course justify the inconsistency we’re in, but I believe there is still an important lesson to learn. While the above concepts are all intuitive to experienced programmers, things can get obscure and cluttered as soon as many of those concepts are combined (as we’ll do soon). My goal is to:
- illustrate the beautiful underlying consistency of all the above concepts
- provoke some thoughts about programming language design
- propose more concise ways to write code
Meet the running example: A function returning some temperatures
I’ll use C# as the running example’s language since it implements the above concepts in interesting and syntactically different ways, which makes it a great language to analyze. However, you should be able to follow along easily with background in other programming languages, I’ll explain stuff as I go.
Consider a function GetTemperatureStats that returns a list of temperature distributions throughout a day, for the past 100 days. There isn’t data for all days, so some list entries might be null:
Say, this function is also asynchronous since it pulls the data from some server. Given some suitable type Distribution<T>, you could declare the return type as Task<List<Nullable<Distribution<float>>>>. What a beauty.
Why did you squeeze only 4 of the 6 example “concepts” in here!?
Look again! The operation is impure since tomorrow the returned list will look different. It also involves network, so it can certainly fail. However, the C# language — and many many others — do not force you to express impurity or potential failure as part of the return type (Java makes you annotate potential exceptions). If we assume for a second that C# made you express all that stuff explicitly, the return type may look like this:
Impure<Task<CouldFail<List<Nullable<Distribution<float>>>>>>How very readable: The function is not pure and executes asynchronously, either failing or returning a list of distributions over floats, but those distributions could also be null.
The fact that these two concepts are not explicitly expressed in C# is the first inconsistency since, as we’ll see later, they fit the exact same pattern as the other concepts. To be clear, I’m not saying this inconsistency is unreasonable: impurity and exceptions are commonplace in an imperative language like C#, so assuming their presence rather than expecting programmers to write boilerplate code makes life easier!
But could there be value in nudging programmers towards writing pure and safe functions by making it very easy to be explicit about impurity and exception safety? Anyways, let’s move on without those two concepts for now.
Working with that return value: Lifting operations
Imagine you are writing your own function Foo, in which you have called GetTemperatureStats and stored the result in variable x. You want to sample every distribution in the list and return the resulting list. For the visualized example list above, we could end up with lists like [18,null,16,15,... or [17,null,18,18,... after sampling. As a return type of Foo we expect Task<List<Nullable<float>>>, since we map each Distribution<float> to a float (by calling some function Sample). Note that we can’t just say x.Sample() since x is not a distribution. Instead, we have to lift that operation into the realm of Task, List and Nullable. In C#, that would look as follows:
GetTemperatureStats fails, so does Foo, likewise impurity is inherited; ignore the fact that “Select” in C# really returns an “IEnumerable” instead of a “List”… “List” is just a more intuitive nameNote how all the colored code serves no other purpose than unwrapping and rewrapping the objects we are interested in.
Let’s do something even harder: How about converting the unit of temperature from Celsius to Kelvin, so we have to offset all values (floats) in x by 273.15. For that, we’ll have to additionally unwrap and rewrap distributions. We assume that there is a way to create a Distribution object from a function that provides samples of the distribution:
Now, another quick look at the hypothetical CouldFail type annotation: In languages like (idiomatic) Go this annotation is very real, you are expected to return errors. Lifting has to happen manually — likely making if err != nil the most common line of code in Go. In contrast, in languages like C#, C++, Java, JavaScript and many more one can think of exceptional behavior as being lifted across expressions, statements and even call boundaries automatically. Hard work is done by language teams to maintain that behavior everywhere, e.g. in async functions or iterators. However, note that one can still very much influence the hypothetical presence of CouldFail: We can use try/catch to get rid of CouldFail in our function Foo. throw is the logical counterpart, introducing CouldFail.
Consistent lifting
We’ve seen that there is a way to lift operations by unwrapping, applying the operation and rewrapping the types. Unfortunately, the syntax for doing so was insanely inconsistent. So let’s make it more consistent:
Mathematics (category theory) calls types with this lifting capability “functors”. Functors have a “map” function which has to obey certain laws. I’ll not go into detail about those laws, but they make sure “map” is capable of lifting arbitrary operations! Let’s define “map” in C# for the functors we’ve encountered and then see how they’re used:
We can now rewrite the previous example in a super consistent way!
If we implemented a LINQ provider for each functor, we could also write:
What would we do if we could extend C#? How about new syntactic sugar?
Maybe that was a little extreme and rather obscure. But how about this:
These are just some examples, let me know what syntax you would like!
Implicit lifting?
Why even do anything in order to perform the lifting? It’s implicit for impurity and failure, so why not for everything? Some of the above proposals would be unthinkable without static type information (which Map overload to call), so why does the compiler not use the static type of x to fully derive the necessary lifting? Specifically: Given a function from T to U and an object of type A<B<C<D<T>>>>, see that the function can only be applied after lifting across A, B, C and D. In this case, all we have to write is x + 273.15f.
This is extreme. Overload resolution will become significantly more complicated (if any other type in the chain defines the + operator, hell breaks loose). More importantly, for programmers it may become obscure what an expression does behind the scenes. Still, maybe there is potential for new editing experiences, e.g. one could implement “semantic zooming”: zooming in shows more and more implementation details (like lifting), zooming out abstracts more and more. In a sense, we are currently trapped in a zoom level at which exceptions and impurity are hidden, but everything else is not.
Anyways, my goal is to raise awareness of the potential of combining static type information with a consistent theory of lifting stuff.
That’s it for the main part of this post. I hope you enjoyed it and maybe saw something new. Should you ever encounter a tower of generic types in the wild, remember: There’s great beauty behind the beast!
Appendix: Going one step further with monads
One can actually generalize the concepts we formalized as functors one more step, namely to monads (don’t fear the monad). Instead of having to define a map :: (T --> U) --> (Foo<T> --> Foo<U>) that follows some laws we didn’t discuss, we can define a bind :: (T --> Foo<U>) --> (Foo<T> --> Foo<U>) and a return :: T --> M<T> (which also follow some important laws) to get a monad.
At the end of the day, map f x == bind (return . f) x, i.e. all monads are also functors, but also a little more powerful. Specifically, under some circumstances bind can be used instead of map to prevent types to become duplicated, e.g. like in Task<Distribution<Distribution<float>>> when really Task<Distribution<float>> was intended. Note that I’m not saying that those two types are semantically identical — there can be a valid scenario for a “distribution of distributions” just like there are lists of lists. However, there’s a meaningful way to prevent such duplicates if they are not intended, which is exactly what bind does:
Imagine that you have a function f mapping a float to a Distribution<float>. Say, it returns the probability distribution of the lifetime of a blender that is operated under given humidity. Maybe we have a probability distribution d for the humidity of some day. Calculating map f d would result in a Distribution<Distribution<float>>. However, note how f matches exactly the parameter bind expects. Calculating bind f d results in a Distribution<float> that, as one would expect, simply represents the probability distribution of the lifetime of a blender considering d.
Just for completeness, here is how return and bind for Distribution could look like in C#:
// Distribution<U> Map<T, U>(Func<T, U> f, Distribution<T> x) {
// return Distribution<U>.FromSampler(() => f(x.Sample()));
// }Distribution<T> Return<T>(T x) {
return Distribution<T>.FromSampler(() => x);
}Distribution<U> Bind<T, U>(Func<T, Distribution<U>> f,
Distribution<T> x) {
return Distribution<U>.FromSampler(() => f(x.Sample()).Sample());
}
// so it's just about "unwrapping" one more time right here ^
Appendix: Functional programming languages
…like Haskell tend to be more consistent about all these things to begin with. If properly defined (as monads), you get do notation for all concepts discussed here. Maybe it is time to once again import some consistency from the functional world! So what about implicitness? I think what makes imperative languages so popular is the implicitness of impurity, since — it turns out — the real world is quite stateful. Sure, Haskell has the IO monad which is super easy to use (once you know how), but at the end of the day, a part of your brainpower is spent on deciding which parts of your program could be expressed without state and which can’t. Time well spent? In practice, languages that let you hack carelessly win.
