Idiomatic monads in Rust
A pragmatic new design for highlevel abstractions
Monads (and, more generally, constructs known as “higher kinded types”) are a tool for highlevel abstraction in programming languages^{1}. Historically, there has been a lot of debate inside (and outside) the Rust community about whether monads would be a useful abstraction to have in the language. I’m not concerned with that here. You see, there’s a problem with talking about whether monads would be useful or not, and it’s this: there are a large number of design challenges to overcome to have any hope of implementing them at all — to the best of my knowledge, there currently exists no realistic (that is, practical) design for monads in Rust. In fact, there are so many obstacles that some people express doubt that it’s even possible.
In general, I don’t think it’s worth talking about the virtue of a language feature if we think there’s no way we could actually implement it. However, I think there are arguments to be made in favour of higherlevel abstractions in Rust. Thus, to facilitate discussion, I want to demonstrate that monads are feasible in Rust.
Specifically, in this article, I’m going to describe a new approach to express monads in Rust. It is the most minimal design I have seen proposed and is, in my eyes, the first plausible design for such abstractions — those commonly known as “higherkinded types”. This approach depends on a very minimal extension to Rust’s type system. In particular, this approach avoids the need for either higherkinded types (e.g. as in this design) or full abstraction over traits (e.g. “traits for traits”). Most of the design challenges are tackled directly using existing features.
However, without explaining why these design choices have been made, the final design can seem opaque. In particular, the design is significantly influenced by several quirks found in the Rust type system that will be unobvious to those who have not already come across them. To make this design accessible and hopefully also to explain why monads are hard(er than you might think) in Rust, I’m going to build up the definition gradually, explaining the motivation behind the choices.
I am going to be assuming some familiarity with monads (and to a certain extent, do
notation). There are enough introductions to monads out there as it is.
The design here was influenced by conversations with @Centril. Thanks also to @Nemo157 for providing illuminating insights into subtleties with the behaviour of yield
.
Overview
There are several problems with a naïve design of monads (and similar abstractions) in Rust. The most prominent are the following.
 Monads are naturally structures at the level of type constructors, not types. Extending Rust to support full higherkinded types raises many significant design questions. There are arguments that such an extension is simply infeasible.
 Monads abstract over function types, but Rust has many types of function (notably any type that implements
Fn
,FnMut
orFnOnce
)^{2}.  As traits are the natural abstraction mechanism in Rust, many structures that appear monadic (such as iterators) are not, strictly speaking, monads at the type level. For instance, calling
map
on any iterator always produces aniter::Map
, rather than preserving the original type constructor^{3}.  Monadic structure appears at two levels in Rust: at the type level, such as with
Option
; and at the trait level, such as withIterator
. Abstracting over both elegantly is tricky.  A naïve implementation of
do
notation would be surprisingly limited in Rust, as controlflow is captured by closures and would thus be useless inbind
desugarings.
As such, any design that puports to facilitate monads must provide solutions for each of these problems.
Let’s see how we can do so.
Idea
We’ll see how this works in detail below, but here’s a summary of the idea behind this design, to set the scene. Traditionally higherkinded types cannot be defined naïvely, because we cannot abstract over type constructors in Rust. However, we can define their structure and properties pointwise on each type that is an instance (that is, instead of saying something like “Option
is a Monad
”, we instead say “Option<A>
is a Monad<A>
for all types A
”). This is still not straightforward, however, because by defining a higherkinded type in terms of each of its instantiations, we lose some higher level typing information. To remedy this, we employ generic associated types and generic associated traits (the one additional language feature) to restore the lost information. This way, Monad
may be defined as a normal trait.
This is all a bit handwavy without seeing it in action, though, so we’ll leave the theory there and get into the details.
Functors
Famously, monads are functors. That means that before we can give a full definition of a monad, we have to give a definition of a functor.
For illustrative purposes, a definition of a functor in Haskell is as follows. The meaning should hopefully be clear even if you’re not familiar with Haskell’s syntax (just read class
as trait
and lowercase letters as uppercase ones).
class Functor f where
map :: f a > (a > b) > f b
If we try to implement this in Rust, we immediately run into several problems.
(You may object to some, or all, of these definitions. That’s a perfectly reasonable reaction. There’s really no natural naïve definition.)
Note on syntax
I’m going to start by using impl Trait
in both argument and returnposition, because I think it indicates intent more clearly. Later, I’ll demonstrate why these are insufficient, but for now I want to prioritise readability.
Attempt 1: Naïve definition
The Functor
type classes in Haskell (what we’d expect to be the equivalent of a hypothetical Functor
trait in Rust) is parameterised by a single type variable. So a first attempt at an analogous definition in Rust might look something like this.
trait Functor<A> {
fn map<B>(Self, fn(A) > B) > /* ??? */;
}
There’s clearly a problem here. We can’t even define the return type of map
. The problem is that we have no way to get a handle on the type constructor that we’re implementing Functor
for. Self
is the type we’re implementing Functor
for, specifically when the type parameter is A
. For example, if we’re implementing Functor
for Option
, then Self
would be Option<A>
and we have no way to declare the type Option<B>
.
The key insight here is that what we’d really like is a higherkinded Self
. That is, we’d like to write something like the following.
trait Functor<A> {
fn map<B>(Self<A>, fn(A) > B) > Self<B>;
}
This just doesn’t work with Self
asis, but the idea is promising. What we’re going to do is create a “higherkinded” version of Self
ourselves, using generic associated types.
Attempt 2: Generic associated Self
trait Functor<A> {
type HigherSelf<T>: Functor<T>;
fn map<B>(Self, fn(A) > B) > Self::HigherSelf<B>;
}
With a generic associated type, we can actually define a signature for map
that looks like something we might expect. (Think of Self
as being the same as HigherSelf<A>
.) We might almost be able to convince ourselves that this is a reasonable definition. Unfortunately, functions aren’t all that simple in Rust (as you’ll know if you’ve been using Rust for a little time).
Aside on identity
Here, we see a generic type HigherSelf<T>
that we are pretending is the type we’re implementing a trait for. In the definition above, though, the type is completely generic; there’s no reason to believe that Self
and HigherSelf<T>
are related in any way. We can address this with type equality constraints, like in the following.
type HigherSelf<T> where Self = HigherSelf<A>;
This ensures our notion of “higherkinded Self
” is somewhat wellbehaved. This kind of condition gets more and more complex to declare as we progress through the design, so I’ve opted to leave them out here. In a real implementation, one may or may not want to enforce this property: having these equality relations is truer to the original concept, but in practice probably has little additional benefit.
A family of functions
Rust has several notions of “function”, which is another reason the definition of Functor
isn’t quite so straightforward as in Haskell^{2}. Namely, in Rust we have the following.
 Unique types for each function or closure. For example the function
fn foo() {}
has the unique typefn() {foo}
. (This type is unnameable in Rust, but may be printed in diagnostic messages.) Two functions that have the same signatures will have different types. There are historical reasons for this.  Function pointers, such as
fn(bool) > (u8, u8)
. Unique function types can be coerced to function pointers. So can unique closure types, as long as they do not capture variables from their environment.  Three traits for abstracting over functions:
Fn
,FnMut
andFnOnce
. These are automatically implemented by unique function types and unique closure types (the specific traits the closure type will implement depends on how it captures from the environment).
The Fn*
traits are the correct way to abstract over functions in Rust: there’s no single function type constructor (>)
. Thus, we need to generalise our definition a little further.
Attempt 3. Generalised mapping function
This is where we need a new language feature. The only facility we require for this design that is not currently an accepted language feature in Rust is the concept of (generic) associated traits. If you’re familiar with associated types and associated consts, the idea will be obvious. The reason we need associated traits is to abstract over the three Fn*
traits. Instead of hardcoding a specific kind of function in our functor definition, we’ll allow it to be specified in the implementation of Functor
.
trait Functor<A> {
type HigherSelf<T>: Functor<T>;
trait MapFn<T, U>;
fn map<B>(Self, impl Self::MapFn<A, B>) > Self::HigherSelf<B>;
}
In practice, we would expect MapFn<A, B>
to be instantiated to one of Fn(A) > B
, FnMut(A) > B
or FnOnce(A) > B
, and we could enforce this, but there’s no real need to do so. By leaving it generic, we create a more general abstraction^{4} (that’s no less useful).
So, now we’re done, right? This seems like a perfectly good definition of a functor.
Well… actually, not quite yet. We can see this isn’t quite general enough if we look at a trait that we expect to be functorial. The map
method on Iterator<Item = A>
has the following signature.
fn map<B, F: FnMut(A) > B>(Self, F) > iter::Map<Self, F>;
Notice how the return type has an extra parameter in it: the (unique) type of the mapping function F
. (The reasons for this are to facilitate a design pattern called external iteration, but the motivation is really tangential here. The fact that we want Iterator
to be functorial means we need to abstract over this design pattern.)
In general, a function’s return type could capture all of the input type parameters that are passed to the function. While it may not look like it in our signature, impl Trait
in argumentposition corresponds to a generic type argument. We need to take account of this detail: namely, we need to add this additional type parameter to the generic return type (that is, HigherSelf
).
Attempt 4. Capturing generic arguments
Now that the return type also needs to capture the mapping function, it doesn’t make so much sense to call it HigherSelf
: it still corresponds in some sense to Self
, but at the same time, it’s been specialised to the map
function signature. In general, if our traits have multiple methods, we’ll need different generic associated traits for each, so it makes sense to use a different name. I’ll call it Map
for simplicity (not to be confused with the identicallynamed iter::Map
… sorry).
trait Functor<A> {
type Map<T, F>: Functor<T>;
trait MapFn<T, U>;
fn map<B, F: Self::MapFn<A, B>>(Self, F) > Self::Map<B, F>;
}
With this last definition, we really are done. It’s taken several iterations, but this definition of Functor
is general enough to capture the examples of functors that we’re interested in.
Implementing Functor
We’ve defined the trait; the next thing to do is to implement it. After deriving a correct definition, making use of it presents no problems.
I’m just going to give two definitions^{5}: for a functorial type and a functorial trait, to demonstrate the flexibility of our definition. More examples can be found at the end of this post.
// Implementing `Functor` for a type.
impl<A> Functor<A> for Option<A> {
type Map<T, F> = Option<T>;
trait MapFn<T, U> = FnOnce(T) > U;
fn map<B, F: FnOnce(A) > B>(self, f: F) > Option<B> {
self.map(f)
}
}
// Implementing `Functor` for a trait.
impl<A, I: Iterator<Item = A>> Functor<A> for I {
type Map<T, F> = iter::Map<T, F>;
trait MapFn<T, U> = FnMut(T) > U;
fn map<B, F: FnMut(A) > B>(self, f: F) > iter::Map<B, F> {
self.map(f)
}
}
Monads
Many of the difficulties in defining Monad
are those we already encountered when figuring out how to implement Functor
: the hardest parts are behind us. However, there is one subtlety in particular in how we define bind
, which is a slightly more complex situation than map
.
Let’s look at the definition in Haskell again first, which I think clearly presents the signature we expect. (What I call unit
and bind
here are usually called return
and >>=
in Haskell.)
class Monad m where
unit :: a > m a
bind :: m a > (a > m b) > m b
This time, I’m going to start with the complete definition in Rust, as it should be mostly familiar, and explain the parts that are new.
trait Monad<A>: Functor<A> {
trait SelfTrait<T>;
// Unit
type Unit<T>: Monad<T> + SelfTrait<T>;
fn unit(A) > Unit<A>;
// Bind
type Bind<T, F>: Monad<T> + SelfTrait<T>;
trait BindFn<T, U>;
fn bind<B, MB: Self::SelfTrait<B>, F: Self::BindFn<A, MB>>(Self, F) > Self::Bind<B, F>;
}
The first thing that you’ll notice is that we have a new associated trait, SelfTrait
. I’m going to come back to what role this plays shortly: you can ignore it for now.
The unit
function is straightforwardly defined using the same reasoning as Functor::map
. In the same way, we need to define a generic associated type that functions as its return type. (Here, there’s an additional SelfTrait
bound on Unit
, but that’s not important to understand yet^{6}.)
In general, though, for each function we define that uses Self
in a higherkinded fashion, we need to use a generic associated type just like for map
. Such as is the case with bind
. Here also, we want to permit the binding function type to vary, so we use an associated trait, BindFn
, representing the kind of binding function, just like before. We could have reused the MapFn
trait: often map
and bind
will take the same kind of functions, but this isn’t always true, so for maximum generality we need another trait.
However, the definition of bind
is a little different than map
. Recall that the binding function has a signature of A > M<B>
(contrast to the mapping function’s signature A > B
). This means we have to take a function that returns a monad (specifically, the current one) parameterised over B
. However, the specific type of this monad may not be fixed. For example, consider the monad Iterator
. The bind
operation for the Iterator
trait corresponds to the flat_map
method. We should be able to return any type that implements Iterator
from the flatmapping function we pass to flat_map
. It’s probably easiest to demonstrate this with an example.
let xs = [1, 2, 3];
// Here, the flatmapping function returns `iter::Take`.
let ys: Vec<_> = xs.iter().flat_map(x iter::repeat(x).take(2)).collect();
// `ys` contains `[1, 1, 2, 2, 3, 3]`.
// Here, the flatmapping function returns `option::IntoIter<_>`.
let zs: Vec<_> = xs.iter().flat_map(x Some(x).into_iter()).collect();
// `zs` contains `[1, 2, 3]`.
Clearly, the return type of the function we pass to flat_map
(and, correspondingly, to bind
) can vary from call to call. Therefore, we want to simply ensure it returns some type that implements our monad. This is the role SelfTrait
plays. Just like Map
and Bind
act like “higherkinded Self
types”, SelfTrait
acts like a “higherkinded Self
trait”. (If this still doesn’t click just yet, wait till you see the examples, which should make things clearer.)
It’s worth noting that we only need to define one SelfTrait
, even if we make use of it in multiple functions (unlike associated types like Map
and Bind
, which had to be defined on a perfunction basis). This is essentially because generic arguments can vary, but the return type is fixed (up to their generic parameters). (This also effectively falls out of the difference between argumentposition and returnposition impl Trait
, albeit in a slightly disguised form.
Note on returnposition impl Trait
in traits
If we had returnposition impl Trait
in trait definitions, we could eliminate the need for our specialised Map
and Bind
types entirely using our associated SelfTrait
. This makes for a much cleaner definition. Here’s Functor
.
trait Functor<A> {
trait SelfTrait<T>;
trait MapFn<T, U>;
fn map<B, F: Self::MapFn<A, B>>(Self, F) > impl Self::SelfTrait<B>;
}
This is technically just syntactic sugar, and it’s not necessary for any of the definitions here, as we’ve seen. It does simplify things though (and is arguably closer to the higherkinded viewpoint, as we’re defining everything from a higher level of abstraction^{7}).
Identities
If you were following the previous definition closely, you may have spotted an apparent oversight. In particular, the associated SelfTrait
only makes sense for monadic traits. If we want to implement Monad
for a type, then there’s no such trait! In the case of a monadic type, the binding function should return something of the (parameterised) type precisely, not just something that implements some trait.
As we saw, though, we do need this level of abstraction for monadic traits. Fortunately, there’s a tidy way we can make Monad
work just as nicely for monadic types. The key is a generic “identity trait”. The identity trait on T
will be implemented solely for T
. No other type will be permitted to implement the identity trait (this is often known as a sealed trait). It’s straightforward to define.
trait Id<T> {}
impl<T> Id<T> for T {}
Now, for example, Option<bool>
(and no other type) implements Id<Option<bool>>
. For monadic types, we can now simply use Id
for SelfTrait
and everything works as expected.
Implementing Monad
// Implementing `Monad` for a type.
impl<A> Monad<A> for Option<A> {
trait SelfTrait<T> = Id<Option<T>>;
// Unit
type Unit<T> = Option<T>;
fn unit(a: A) > Option<A> {
Some(a)
}
// Bind
type Bind<T, F> = Option<T>;
trait BindFn<T, U> = FnOnce(T) > U;
fn bind<B, MB: Id<Option<B>>, F: FnOnce(A) > MB>(self, f: F) > Option<B> {
self.and_then(f)
}
}
// Implementing `Monad` for a trait.
impl<A, I: Iterator<Item = A>> Monad<A> for I {
trait SelfTrait<T> = Iterator<Item = T>;
// Unit
type Unit<T> = iter::Once<T>;
fn unit(a: A) > iter::Once<A> {
iter::once(a)
}
// Bind
type Bind<T, F> = iter::FlatMap<T, F>;
trait BindFn<T, U> = FnMut(T) > U;
fn bind<B, MB: Iterator<Item = B>, F: FnMut(A) > B>(self, f: F) > iter::FlatMap<B, F> {
self.flat_map(f)
}
}
Easy!
Deriving functors and monads
In the examples above, though the implementations of Functor
and Monad
for types and iterators are straightforward, they do contain a lot of boilerplate. This is an unfortunate consequence of the lack of full higherkinded types: we generally have to be much more explicit about the various types. This is likely to be true for any similar representation of higherkinded types in Rust.
However, in practice, we could avoid this boilerplate in the majority of instances. This is made clear by observing how the entirety of the implementation definitions are determined by the map
, unit
and bind
functions for Functor
and Monad
respectively. Often types and traits implementing these higherkinded traits already define these functions (albeit with different names): we’ve already seen this with Option
and Iterator
, where we simply delegate to existing functions, and it’s certainly the case for many of the functors and monads in the Rust standard library.
In these cases, we could use a custom #[derive]
attribute to generate the boilerplate automatically for us in the background. With this feature, implementing Functor
and Monad
could be as simple as the following.
#[derive(Functor(map), Monad(Some, and_then))]
enum Option { ... }
#[derive(Functor(map), Monad(once, flat_map))]
trait Iterator { ... }
The message to take away here is that, though the definitions might seem intimidating at first, in all likelihood they would rarely need to be implemented directly by the user.
Do notation
It would be remiss of me to talk about the feasibility of monads without even mentioning do
notation. For those of you who are unfamiliar with do
notation, it provides a convenient synactic sugar for working with monads without having to make do with deeplynested bind
s and unit
s in Haskell. Monads are useful abstractions even without do
notation, but there is definitely something to be said for a design that also encompasses a similar synactic sugar for monads in Rust.
The main argument against the feasibility of do
notation in Rust is the difficulty with composing control flow expressions (such as return
or break
) with closures. This is because closures capture controlflow: we can’t break out of a loop enclosing a closure within the closure itself, for instance.
loop {
 break; // This isn't going to work.
}
This is a problem, because do
notation is desugared in terms of nested bind
s, which take closures as arguments. What we might expect to work intuitively in a naïve implementation of do
would fail unexpectedly.
Let’s look at a concrete example to see exactly where this fails.
// This is a useless loop, but it's illustrative.
loop {
do {
let x < a;
println!("x is {}.", x);
break; // We've done what we came for: let's leave the loop.
}
}
Desugaring do
from a naïve perspective, we might expect this to be equivalent to the following.
loop {
a.bind(x {
println!("x is {}.", x);
break; // Uh oh...
});
}
Obviously, this doesn’t work, because we’re trying to break the outer loop from inside the bind
closure. However, from the perspective of the do
notation, it seems entirely reasonable.
There’s a happy conclusion to this story. I wrote a separate post on the topic a while ago, describing how we can resolve this dichotomy. In essence, control flow and do
notation are not mutually exclusive: you just need to be a little cleverer in your desugaring. We might desugar something like the following^{8}:
let expr0 = do {
expr1;
let a < expr2;
expr3;
let b < expr4;
expr5;
expr6(a, b);
expr7
};
into, intuitively, something of the form:
let expr0 = surface! {
expr1;
bubble! expr2.bind(move a {
expr3;
bubble! expr4.bind(move b {
expr5;
expr6(a, b);
Monad::unit(expr7)
})
})
}
where, for the sake of illustration, surface!
and bubble!
are macros that perform propogation of control flow.
use ControlFlow::*;
// `bubble!(expr)` desugars to...
match expr {
Return(_) => return expr,
Break(Some(_)) => break expr,
Break(None) => break,
Continue => continue,
Yield(Some(_)) => yield expr,
Yield(None) => yield,
Value(_) => expr,
}
// `surface!(expr)` desugars to...
match ( expr)() {
Return(t) => return t,
Break(Some(t)) => break t,
Break(None) => break,
Continue => continue,
Yield(Some(t)) => yield t,
Yield(None) => yield,
Value(t) => t,
}
In practice, this exact desugaring has some rough edges. For example, any variables referenced inside a do {}
block are moved inside the bind
ing closures, and are then unusable after the scope of the do {}
block.
This is a flaw that could be addressed with builtin support from the compiler for do
notation (for example, it could move those variables live at the end of the do {}
block’s scope to the enclosing scope). In practice, if we decided we wanted do
notation in the language, we’d want to experiment with exactly how do
should work, especially in its interaction with lifetimes. The main takeaway here is that do
notation in Rust could make sense: even though by necessity we’re working with closures behind the scenes, we can still recover the expressivity of the notation with some sleight of hand. (Whether do
notation would be useful in practice is another question, which would be a question for a full feature proposal, rather than the exploration here.)
Abstracting over monads
We’re almost done. The last topic I want to cover is the question of further abstraction. There are really two questions that are natural to ask at this point.
 How can we write abstractions involving monads?
 How can we abstract over monads?
The first question is easily answered. As Monad
is simply a trait, we can use it like any other. As a user of Monad
, we don’t need to worry about whether an implementer is a monadic type or a monadic trait: whatever form it takes, we know it conforms to the trait interface specified by Monad
.
// A simple function making use of a monad.
fn double_inner<M: Monad<u64>>(m: M) > M {
m.bind(x M::unit(x * 2))
}
Practically, monads are now no more imposing than any other trait. All the complexity is hidden away in the definition (and to some extent, the trait implementation).
The second question requires a little more thought to answer. Functors and monads are, in one respect, simply the first rung on the ladder of higherkinded types. Just as monads (as type constructors) abstract over types, we can also abstract over monads themselves. To give an example, one such abstraction is a monad transformer.
Frankly, at this point, I’m not sure whether even higherkinded types are possible to express in Rust. When I spent a little time playing around with potential definitions of monad transformers, I kept running into design problems: exactly the same tricks as for monads don’t quite carry across, because we end up wanting to quantify over all traits in an implementation, rather than one trait per implementation. That said, I didn’t try all that hard and it’s possible there’s a way to resolve the difficulties.
The main takeaway here is that, even though the designs here may not (obviously) generalise to all higherkinded types, they generalise to a wide class of examples^{9} that could reasonably be considered sufficient for most of the abstraction users generally want to express in Rust. Even without full higherkinded types, perhaps this is enough.
Summary
Let’s take a step back and appreciate what we’ve achieved.
 We’ve defined an abstraction for functors and monads in Rust, two common higherkinded types, using only one (conservative) hypothetical language feature: associated traits.
 We’ve demonstrated how it elegantly abstracts over both monadic types and monadic traits.
 We’ve shown how implementational boilerplate can be close to eliminated using
#[derive]
macros.  We’ve illustrated how control flow is compatible with a natural
do
notation in Rust.
Many have expressed reservations about the feasibility of providing abstractions over higherkinded types like monads in Rust (perhaps the most notable being this thread, which I address directly in the appendix for completeness). The past proposals for monads in Rust that make use of advanced type system features such as full higherkinded types do nothing to palliate these suspicions.
However, I think in this design, there is at last a plausible and reserved model for these abstractions. In particular, I think monads fall naturally out of a conservative extension of the language that is beneficial even without considering the potential for higherkinded types.
At the very least, I hope that I have given some food for thought. We never needed higherkinded types. My conclusion wherefore is this: monads are feasible in Rust.
Appendix
Accepting the challenge
IN CONCLUSION: a design that works in a pure FP which lazily evaluates and boxes everything by default doesn’t necessarily work in an eager imperative language with no runtime.
I haven’t explicitly addressed each of the points in the aforementioned “Monads and Rust” thread in the main post, because I think it is selfevident that the design here is sufficient to capture Monad
in Rust. However, I shall do so briefly here, to satisfy any suspicions of avoiding difficulties by omission.
 Borrowing across
yield
indo
notation: there is a problem with pretendingyield
is simply thebind
of theFuture
monad (despite both having similar effects), namely when borrowing is involved. (The only examples I’ve seen so far are rather involved, so I’m not going to reproduce them here.) That is: we can’t replace theyield
keyword with<Future as Monad>::bind
. However, we can useyield
just fine withindo
notation (using the same propagation of control flow from closures asbreak
orreturn
). Soyield
per se isn’t a problem withdo
notation: we just can’t abstract it away entirely.  Control flow in
do
notation: as illustrated above, using a straightforward desugaring, we can recover full control flow withindo
notation (arguably solving an open research question).  External iterator patterns induces unmonadic signatures: by abstracting over traits, rather than types, we can describe monadic signatures entirely idiomatically.
 There are three kinds of function type constructor: using associated traits, we can capture all three notions of function (and more).
 Higherkinded polymorphism is hard: in this design, we completely avoid higherkinded polymorphism (and full higherkinded types in general).
 Abstracting over monads would be unergonomic in Rust: using
#[derive]
, implementing higherkinded types can be made very minimal and ergonomic.
To conclude, there’s no guarantee that a feature designed with a pure, lazy language in mind will work in an eager^{10}, imperative language. But sometimes it does; it just requires a little more care.
Additional examples
In this post I’ve focused on functors and monads for Option
and Iterator
in particular. The techniques here extend naturally to other popular examples of higherkinded types and other monadic types and traits. For completeness, I’m going to give some additional examples, to demonstrate that the framework here really is general enough to encompass the traditional and desirable use cases. This appendix can be viewed as a reference more than a section worth reading in its own right.
join
Monads have another operation, known as join
, or simply “multiplication”, with the signature m (m a) > ma
. It’s interderivable with bind
, so I haven’t included it in the definition above, but we could provide it as a default implementation^{11} on the Monad
trait.
trait Monad<A>: Functor<A> {
// ...
// Join
type Join = Self::Bind<A, impl Self::BindFn<impl Self::SelfTrait<Self>, impl Self::SelfTrait<Self>>>;
fn join<MA: Self::SelfTrait<Self>>(ma: MA) > Self::Join {
ma.bind(a a)
}
}
In the case of Iterator
, for instance, an explicit definition would look like this.
impl<A, I: Iterator<Item = A>> Monad<A> for I {
// ...
// Join
type Join = iter::Flatten<Self>;
fn join<MA: Iterator<Item = I>>(ma: MA) > Self::Join {
ma.flatten()
}
}
Further Monad
implementations
Future
impl<A, E, R: Future<Item = A, E>> Functor<A> for R {
type Map<_, F> = future::Map<Self, F>;
trait MapFn<T, U> = FnOnce(T) > U;
fn map<B, F: FnOnce(A) > B>(self, f: F) > future::Map<Self, F> {
self.map(f)
}
}
impl<A, E, R: Future<Item = A, E>> Monad<A> for R {
trait SelfTrait<T> = Future<Item = T, E>;
// Unit
type Unit<T> = Ready<T>;
fn unit(a: A) > Ready<A> {
future::ready(a)
}
// Bind
type Bind<T, F> = AndThen<Self, T, F>;
trait BindFn<T, U> = FnOnce(T) > U;
fn bind<B, MB: Future<Item = B, E>, F: FnOnce(A) > B>(self, f: F) > AndThen<B, F> {
self.and_then(f)
}
}
More higherkinded types
(Some of the initial types are not higherkinded, but are necessary for later definitions.)
Magma
trait Magma {
fn mul(Self, Self) > Self;
}
Semigroup
trait Semigroup: Magma {}
Monoid
trait Monoid: Semigroup {
fn unit() > Self;
}
Foldable
trait Foldable<A> {
trait FoldMapFn<T, U>;
fn fold_map<M: Monad, F: FoldMapFn<A, M>>(Self, F) > M;
}
Applicative
trait Applicative<A>: Functor<A> {
trait SelfTrait<T>;
// Unit
fn unit(A) > Self;
// Apply
type Apply<T, F>: Applicative<T>;
trait BindFn<T, U>;
fn apply<B, F: BindFn<A, B>, T: SelfTrait<F>>(T, Self) > Apply<B, T>;
}
Other higherkinded types
There are some higherkinded types I suspect we need additional type system additions to support. For example, I think definining Traversable
requires trait generics: i.e. traits as generic parameters. This is a similar, but distinct, feature from (generic) associated traits.
As another example, the similarlynamed Traversal
probably requires higherranked types in trait bounds.
These are both plausible language extensions that also do not introduce the full complexity required by general higherranked types. However, I do not dwell on them here: I think associated traits provide the most immediate benefit of these type system extensions (it’s better to focus on one feature at a time).

Strictly speaking, they’re a lot more than that, but we’re only interested in the programming angle here. ↩

A similar problem arises in Haskell when linear function types are introduced. ↩ ↩^{2}

This is known as the external iterator pattern and is done for performance reasons. ↩

From the perspective of category theory, this corresponds to defining a functor from an enriched category. ↩

Technically, these two implementations are going to conflict, because the
Iterator
implementation will also apply toOption
. For the sake of the examples, consider these implementations as living in isolation. In practice, we’d need to carefully decide which traits or types to implement these for. ↩ 
We could have added a
SelfTrait
toFunctor
too, and imposed a similar bound onFunctor::Map
, which would have made the definition stronger. However, I thought it clearer to leave it out until it was strictly necessary. That is, the weaker definition ofFunctor
defined above is sufficient to implement the types we expect to be functors, albeit while allowing us to implementFunctor
for some types we probably don’t expect to be functors. ↩ 
Technically, using
impl Trait
is actually a little more restrictive than we intend, becauseimpl Trait
is opaque: the underlying type is not observable. What we’d really like here is some kind of transparent analogue. ↩ 
To those of you who recognise the
<
sigil as being experimental syntax for “placement new”, just note that I’m using<
here for monadic bindings, reminiscent of thedo
notation from Haskell, not placement new. ↩ 
See the appendix for a large range of examples of useful higherkinded types that are expressible with the techniques advocated here. ↩

As we’ve seen, eagerness and laziness don’t actually factor into the design problem at all. ↩

Okay, I’m taking some liberties here. We should be able to define it automatically, but
impl Trait
in associated types is too limited at the moment. There’s an RFC (in the final stages at the time of writing) that should address this, though. You’re still able to definejoin
manually for each implementer ofMonad
, though: it’s just a little less convenient. ↩