Monads (and Functors and Applicatives) explained (badly) in Rust


#1

I’ve been doing the Haskell track at exercism, and reading learn you haskell. It took me a while to understand the Functor -> Applicative -> Monad typeclass (think Trait) hierarchy, but I think I can give an exposition that would be easier to understand for a Rustacean!

There are probably loads of mistakes so if you spot any please point them out, that’s how I learn. :slight_smile:

So, firstly, some notation:

Notation

Currying

In Rust, function application looks like

fn funcName(arg1: T1, arg2 T2, ...) -> RetType

The equivalent in Haskell is

funcName :: T1 -> T2 -> ... -> RetType
funcName arg1 arg2 ... =

Although they look very different, they are semantically the same. It’s just that in Haskell you write the (optional, can be inferred) type signature separately from the function signature. Also, because of currying, instead of a function taking 2 arguments returning T you have a function taking an argument returning a function taking an argument returning a T. Equivalent in Rust would be

// Rust version
fn funcName(arg1: u8, arg2: u8) -> u8;

// Haskell version, in Rust (might not be valid syntax but you get the idea)
fn funcName(arg1: u8) -> (fn(u8) -> u8);

Generics

In Rust we need a specific syntax for generics fn name<Types...>(args...), whereas in Haskell any lowercase type is generic.

so the function

fn package<T>(t: T) -> Vec<T> {
   vec![t]
}

in Haskell would simply be

package :: a -> [a]
package val = [val]

Important thing is lowercase named types are generic in Haskell.

Of course, sometimes we want to constrain our generics so we know what we’re dealing with (you don’t want to try to multiply some strings!). Below are the two equivalent syntaxes in Rust and Haskell. Rust’s constraints are called Traits, and Haskell’s are called Typeclasses

// rust
fn funcName<T: Constraint>(t: T) -> u8 {..}
// or alternatively
fn funcName<T>(t: T)
    where T: Constraint
{..}

in Haskell

funcName :: (Constraint t) => t -> Int

Incomplete Types (and Kinds)

Both Rust and Haskell allow you to have an Incomplete Type, a partial type that requires some more type information to be a real thing you can use. For example, take Vec<T>. This type can’t be actually used, there isn’t enough information to know what we’re putting in it. However, some of the functionality doesn’t require knowing what type type of T is, for example we can iterate over elements. However someone can’t use this functionality without saying what the type of T is.

In fact, you can think of an incomplete type as a type function, so in made up similar to Haskell notation

vec :: * -> *

vec takes a type (*) and returns another type. In a very hand-wavey way, we’ve invented Kinds, a generalisation of types. All concrete types are the same kind (*), but the type constructor for Vec is of type * -> * (takes a type and produces another type). We’re going to see that some of these Kind Signatures are implemented in Rust, but not others.

Hopefully that’s enough syntax to be able to understand the stuff later. I want to be able to use Haskell notation for functions because it’s so succinct, but I’ll try to show the equivalent in Rust.

Important thing is Kinds are like function signatures, but over types not values. In the same way you can think of a value as a function that always returns the same value, you can think of a type as a kind that always returns the same type.

Of course our type constructor may have constraints like <T: Clone> in Rust. In our hand-wavey syntax we could write

(Clone t) => t -> *

to say that the type passed to the incomplete type must be Cloneable. Not sure if we’ll need this, but hey…)

Infix

I’d rather not have to explain infix operators as they complicate things, but they do appear in type signatures for Applicative and Monad, so I’ll briefly describe them.

In Rust there are built-in infix operators, but you cannot create your own. They are things like +-*/%. A function is infix if one of the parameters comes before the function name (in 2+3 the 2 comes before the operator (+). In Haskell you can make them yourself, and they are heavily used in the standard library (see the >>> function below for an example). You can also use any function in infix style by surrouding it in back-ticks (`) and make an infix function into a normal function by surrounding it with parentheses ((+) 2 3 is the same as 2 + 3. Infix operators complicate precedence, for example you can write arithmetic without brackets if you use Reverse-Polish notation.

Digression (skip if you like)

Currying can be really useful for writing processing pipelines. For example, with Haskell’s reverse composition operator (>>>), let’s solve the following problem: sum the squares of all even numbers in a given range.

sumSquareOfEven :: [Int] -> Int
sumSquareOfEven = filter even >>> map (^2) >>> sum

which I think is really easy to read! We just write each step out and connect them together with >>>. Even if you don’t know exactly what’s going on (which is totally fine BTW), you could guess what this function does.

The cleaver bit is that if we looked at the type signature for filter we would see it actually takes 2 values

filter :: (a -> Bool) -> [a] -> [a]

We’re gonna take a function (a -> Bool) and a list and produce a list. If you look above, filter only has 1 parameter (even). This means that we’ve still got a function, not a value. We’re gonna chain a load of functions together, and say we want the output of the previous function to be the input of the next. That’s what >>> does. You couldn’t do this without partial application.

Functor

Now we’re into the fancy stuff. There is a natural hierarchy of types: any Monad is an Applicative, and any Applicative is a Functor. We’re gonna tackle them in reverse order because they increase in complexity, and so the humble Functor is the place to start!

Let’s dump out the functor definition from Haskell and inspect it

class Functor f where  
    fmap :: (a -> b) -> f a -> f b

class Functor f where basically means trait Functor. The interesting bit is the function fmap. This is what we have to implement if we want our type to be a functor.

From the definition, we see that our type f (the thing we are implementing the trait for) must take 1 type argument, and so it must be of kind

* -> *

If it was just a type, we couldn’t pass a or b to it.

In fact, this Functor trait makes sense for lots of types in rust. For example, take Box<T>. If we had some function fn(u8) -> u16 and a Box<u8> we should be able to get a Box<u16> by unboxing, applying the function, and boxing it up again. So in some made up Rust-y syntax, this would be

trait Functor<T> {
    fn fmap<F, U>(Self<T>, f: F) -> Self<U>
         where F: Fn(T) -> U;
}

So we can pass some function that maps the inner value, and our type constructor can map the constructed value. The difficulty of defining this in Rust is that we want to

TODO I don’t know if this is possible with Rust right now, and if it is what the correct syntax is. Please advise! :slight_smile:

Rust applications

In Rust we use functor-like functionality often, but it generally has a name specific to the type we’re working on, rather than some general Trait.

Some examples:

  • for slice, slice::Iter::map, e.g. [1u8; 10].iter().map(|x| x * x)
  • for Vec, vec::Iter::map e.g. vec![1u8, 2, 3, 4].iter().map(|x| x*x)
  • for Option, Option::map (seeing a pattern yet…?) e.g. Some(2).map(|x| x+1)

Applicative

As we’ll see, Applicative is a more general trait than Functor. From Haskell, its type signature is

class (Functor f) => Applicative f where  
    pure :: a -> f a  
    (<*>) :: f (a -> b) -> f a -> f b  

pure is a function that takes the inner value and wraps it, creating an untainted or pure representation of a, like Box::new for example. (Aside: these type constructors are not boxes, but it can be helpful to think in that way to begin with. A box certainly can be an Applicative).

The other function <*> (it’s infix, but this is irrelevant) takes a wrapped function and a wrapped value and produces a new wrapped value. If we compare type signatures to Functor we can see that the difference between <*> and fmap is that in <*>, the function is wrapped in f. It turns out that this is more general, because it’s up to the implementation of <*> to decide how to unwrap the function.

If we do some heuristic logic, we have our Applicative f (a -> b) -> f a -> f b and a function a -> b -> c and an f a and we use the function above, we end up with f (b -> c), then we can repeat the trick by passing in an f b to get an f c. So this Applicative function allows us to do fmap but with more than 1 argument! This wouldn’t be possible without <*>.

In rust the Applicative trait might look like

trait Applicative<T> : Functor<T> {
    fn pure(t: T) -> Self<T>;
    // we'll call (<*>) chain because we can't use symbols
    fn chain<F, U>(Self<T>, f: F) -> Self<U>
        where F: Self<Fn(T) -> U>;

This pattern isn’t really used in rust very often because wrapping functions in other types is not possible (TODO is it?) and this pattern is not considered idiomatic rust. In rust, if we wanted to add two Options where the inner types are numeric, we would write a function like

fn add_options<T: Addable>(o1: Option<T>, o2: Option<T>) -> Option<T> {
    match (o1, o2) {
        (Some(t1), Some(t2)) => Some(t1 + t2)
        _ => None
    }
}

In Haskell you don’t need to write a new function to do this, you just wrap it in Maybe (Haskell’s Option) and use the Applicative operations, so you’d do

addOptions o1 o2 = (+) <$> o1 <*> o2

where <$> shorthand for pure (+). The above example nicely illustrates the use case for this structure, and how its absence is managed in Rust.

Monad

A monad is a generalisation of an Applicative. as always, lets check out its Haskell typeclass

class Monad m where  
    return :: a -> m a  
  
    (>>=) :: m a -> (a -> m b) -> m b  

(I’ve left out some of the definition because we can understand the principles without it).

First thing we notice is that return works like pure in the Applicative typeclass. Note that this is NOT the same as return in imperative languages, although it can end up being used at the end of a sequence of functions to wrap up the last value.

The way I think of the >>= operator is that it takes a wrapped value and then knows how to double-wrap it and then make that into only a single wrap. Does that make sense? Perhaps not, I’ll try again.

Let’s look at some Rust examples

Option as a Monad

The return operation is easy, just wrap the value in a Some, so when we pass 3 we get Some(3). Then how would the >>= operation work?

Let’s say we have a Some(3) and a fn(u8) -> Option` we need to combine these to get an Option. We would do something like

impl<T> Option<T> {
    // again I've invented a name because infix operators don't exist in rust
    fn chain<F, U>(self, f: F) where <F: fn(T) -> Option<U>> {
        match self {
            Some(t) => f(t),
            None => None
        }
    }
}

This exists in the standard library as Option::and_then.

Jerry’s final thought

Personally, I’m not sure we need these kinds of constructs in Rust. They are complicated for new users who didn’t study category theory at college, and because of the focus on performance you often don’t want to write things at such a high level in rust.

If you got this far you’ve given up a few minutes of your life to read this. Hope it was worth it!