Monad Interface: Rust Edition
Implementing Monads in Rust
I’ve done a lot of writing about functional programming. But mostly in JavaScript. I love the simplicity of declarations that are possible thanks to JavaScript’s dynamic typing system. It makes defining generic things very easy — a concept that is much more complicated in strongly typed languages. One generic concept that I love expressing in JS is the functional keystone known as the Monad. A Monad is an encapsulation of an associative binary operation. In other words, you can call map on it with an appropriate function parameter to change the inner value — even its type. It wraps some value and and allows us to adhere to a simple interface to act on that value. So how can I express this highly generic concept in Rust? Is it even possible?
I assume, reader, that you have some interest in functional programming. You may even already know what a Monad is, and simply want to know how to implement them in Rust. If this is you, read on! You’ve come to the right place.
Recently, I was looking for examples of good implementations of Monad in Rust and I came across this article. Its all about using generic associated types in traits. I was reading along, eagerly eating up the information. This is beautiful, I thought, this is amazing, this— isn’t currently possible in Rust. Unfortunately, at the time of writing this article using generics in associated types is unstable. Even enabling the experimental feature isn’t guaranteed to work (and largely, doesn’t). But that’s OK. I decided I’d just write my own implementation instead.
Pointy Structs
Firstly, Monads tend to adhere to an interface known as Pointed:
The Pointed interface says, ‘I am a wrapper type that can wrap and unwrap a value T.’ It has an associated type, Unit. This represents the type that get’s encapsulated by the implementer. of is the constructor of the wrapper. unwrap removes the wrapper, returning the encapsulated unit. Notice another thing about this trait definition — we make use of a where clause. where clauses are powerful in trait definitions. They can be used to ensure that certain methods and values are available to you within the trait definition. They can restrict the types that can implement this trait as well. In our clause, we declare Self as Sized. Declaring Self as Sized means that this trait can only be implemented by structures that can have a statically known size.
Now, let’s write a simple struct to implement this Trait:
Identity is one of the simplest Monads to understand. It takes any value and wraps it up with no special behavior. We can define our implementation generically using impl<T>. Now we’ve implemented Pointed for any T of Identity.
However Identity isn’t nearly a Monad yet, and we can’t even operate on it’s inner value. It’s still a few big steps behind being monadic.
Funky Functors
Additional to their adherence to the Pointed interface, Monads are also Functors. Functors extend what Pointed defines. Not only can a Functor hold a value, but it can operate on that value without removing it from the box. This is thanks to the concept of map. map allows us to apply a function to the value that is hiding within our box. How can we define it?
By using the sub-trait syntax (Trait : SubTrait), we can declare that everything we defined in the sub-trait needs to be implemented in this trait. So that means that Functor intrinsically has of and unwrap as part of its interface. The main part of Functor, however, is map. map takes a function F and returns a Functor B. What that means is that the function you give to map might transform the type that you’re working with. So you may start with an Identity<u32> and you might transform it somehow into an Identity<&str>.
Check out our where clause in this block. This one is local to the map function. I love how easy trait bounds are to read. B: Functor almost reads as the plain English, ‘B is a Functor’. In order to accommodate a default functionality without knowing the types, I rely on the things defined by my trait bounds like Pointed’s Self::Unit associated type and of function. Conveniently with this implementation, the type parameters can usually be elided (meaning you don’t have to declare them at the call site).
Let’s implement it for Identity:
Since our default implementation does nothing special with the values, we can reuse it for Identity without declaring any unique definition. How nice is that? Let’s give it a test run:
This should produce Identity(5) and Identity(15). Easy.
Full Blown Monads
Now that we have a Functor, let’s go ahead and make a full fledged Monad out of this. We’ll define another trait:
Monad compounds both Functor and Pointed. This means it can lift a value into context with of, and operate on that value without removing it from the box using map. And now we will be able to do something else — chain. chain lets us take a function that would normally return a Monad and map it into another Monad. Now, normally if we were to do this using map, we’d end up with an Identity<Identity<T>>. But we don’t ever really want that, we just want Identity<T>. This is where chain comes in handy. It does the lifting function, but discards the outer box. Our generic implementation applies the lift to the unwrapped value of the supplied self Monad. Since we have this nice default implementation we can alsofcb implement Monad as a one-liner for Identity:
Let’s test this to make sure everything is working alright:
That should spit out Identity(5), Identity(15), Identity(12) to the console. Woohoo, it works! Although I wish I didn’t have that pesky type declaration on id2. Try removing it. You’ll get a type annotation needed error from the compiler, unfortunately. I like type elision when I can get it.
Does It Work?
Let’s try to define a Monad that’s a bit more complicated than Identity. We’ll still stay pretty simple for this example. Although tuples are already supported by Rust, let’s make a dedicated Pair type.
And we will of course have to implement some traits, starting with Pointed:
Simple enough, that definition allows us to easily create Pairs and convert them back into native tuples. Unit controls what we get to play with in our map function — in this case the tuple type (A, B).
We can one-line our Functor and Monad implementations, as with Identity:
And now we can play some more. Let’s test out each of Pair’s Monad Interface functions:
When this program runs, it should spit out Pair(1, 2), Pair(2, 5), and Pair(5, 2). Our constructor gives us back just what we’ve lifted into the monadic context. Our map gives us a transformed Pair. And finally, our chain constructs a flipped version of our Pair. Look out, it’s Functional Rust in action!
Heres a link to the Playground.
Conclusion
I hope you’ve enjoyed another expedition into the wilderness that is Functional Rust. In the Rust world, where everything is statically typed and memory safe, the compiler makes a lot of demands from us as the developers at compile time. As a guy coming from JS, this makes it difficult for me to write what I feel is truly flexible and generic code at times. But the fact that any of this is possible in a systems language is very impressive. High level abstractions like these are generally reserved for productivity languages. Rust is a diamond in the rough in that it offers us free abstraction via Traits and generic parameters while preserving the surgical accuracy and performance expected from a systems language. If you’re not interested now, check on Rust again in a couple years. Rust will be everywhere.
