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.

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 `Clone`

able. 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!

## 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 `Option`

s 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!