Chapter 8: Functors, Applicatives and Monads

Where I will try to explain something really confusing, and you'll pretend you understand to avoid hurting my feelings.

OK. It's time to get serious.

The following topics are known to be troublesome to teach, so I can only promise you that I will try really, really hard not too say something confusing (or stupid).

Functors

Functors, applicatives and monads are all mathematical concepts that are prevalent in Category Theory. You may have heard of it before. It's a branch of abstract mathematics that many are drawing inspiration from when developing new tools and techniques for functional programming.

But I will not go down the route of explaining things to you from a mathematical perspective... as I'm not confident that's gonna work.

Imagine that you have some data (maybe an Int, or a Text). You can work with that data: you can pass it around, apply functions to it, print it to the console, or pattern-match against it.

Well, imagine a functor as some kind of wrapper on your data. You can still access what's inside, but the wrapper itself offers special superpowers, and each wrapper is different.

For instance, there's one wrapper that allows us to have (or not to have) our data.

Schrodinger's wrapper (although most people prefer to call it Maybe).

That wrapper happens to be a type. All functor wrappers are types.

But not just any type. You see, functors have requirements.

(sig: #export (Functor f)
  (: (All [a b]
       (-> (-> a b) (f a) (f b)))
     map))

This is the Functor signature, from lux/control/functor.

As you can see, it only has a single member: the map function.

The parameter type f is very special, because instead of being a simple type (like Int or Bool), it's actually a parameterized type (with a single parameter). That explains why it's being used the way it is in the type of map.

Not every parameterized type can be a functor, but if the type is something that you can open to work with its inner elements, then it becomes a good candidate.

And you would be surprised how many things fit that requirement.

Remember that Maybe type we talked about? Let's see how it plays with Functor.

(type: (Maybe a)
  #;None
  (#;Some a))

We've seen Maybe before, but now we can check out how it's implemented.

By the way, it lives in the lux module, so you don't need to import anything.

Here is it's Functor implementation.

(struct: #export Functor<Maybe> (Functor Maybe)
  (def: (map f ma)
    (case ma
      #;None     #;None
      (#;Some a) (#;Some (f a)))))

This one lives in the lux/data/maybe module, though.

We'll know how everything fits if we fill in the blanks for map's type:

(All [a b]
  (-> (-> a b) (Maybe a) (Maybe b))

So, the job of map here is to take a Maybe containing some a value, and somehow transform it into a b, without escaping the Maybe.

By looking at the Functor implementation, we can see how this works out.

We can actually pattern-match against the entire input and handle the different cases, using the given function to transform our a into a b.

Not that hard.

Oh, and remember our iterate-list function from chapter 5?

Turns out, that's just the Functor<List> implementation from lux/data/struct/list:

(struct: #export _ (Functor List)
  (def: (map f ma)
    (case ma
      #;Nil          #;Nil
      (#;Cons a ma') (#;Cons (f a) (map f ma')))))

Not bad.

Did you notice that underscore?

If the name of a structure can be trivially derived from it's type-signature, you can just use an underscore, and have the struct: macro fill in the blanks for you.

Of course, that only works if you're fine using the conventional name.

In the case of List, the wrapper superpower it provides is the capacity to handle multiple values as a group. This can be used for some really cool techniques; like implementing non-deterministic computations by treating every list element as a branching value (but let's not go down that rabbit-hole for now).

The power of functors is that they allow you to decorate your types with extra functionality. You can still access the inner data and the map function will take advantage of the wrapper's properties to give you that extra power you want.

You can implement things like stateful computations, error-handling, logging, I/O, asynchronous concurrency and many other crazy things with the help of functors.

However, to make them really easy to use, you might want to add some extra layers of functionality.

Applicatives

One thing you may have noticed about the Functor signature is that you have a way to operate on functor values, but you don't have any (standardized) means of creating them.

I mean, you can use the list and list& macros to create lists and the #;Some and #;None tags for Maybe, but there is no unified way for creating any functor value.

Well, let me introduce you to Applicative:

(sig: #export (Applicative f)
  (: (F;Functor f)
     functor)
  (: (All [a]
       (-> a (f a)))
     wrap)
  (: (All [a b]
       (-> (f (-> a b)) (f a) (f b)))
     apply))

This signature extends Functor with both the capacity to wrap a normal value inside the functor, and to apply a function wrapped in the functor, on a value that's also wrapped in it.

Sweet!

Wrapping makes working with functors so much easier because you don't need to memorize a bunch of tags, macros or functions in order to create the structures that you need.

And being able to apply wrapped functions to wrapped values simplifies a lot of computations where you may want to work with multiple values, all within the functor.

To get a taste for it, let's check out another functor type.

Remember what I said about error-handling?

(type: #export (Error a)
  (#Error Text)
  (#Success a))

This type expresses errors as Text messages (and it lives in the lux/data/error module).

Here are the relevant Functor and Applicative implementations:

(struct: #export _ (Functor Error)
  (def: (map f ma)
    (case ma
      (#;Error msg)     (#;Error msg)
      (#;Success datum) (#;Success (f datum)))))

(struct: #export _ (Applicative Error)
  (def: functor Functor<Error>)

  (def: (wrap a)
    (#;Success a))

  (def: (apply ff fa)
    (case ff
      (#;Success f)
      (case fa
        (#;Success a)
        (#;Success (f a))

        (#;Error msg)
        (#;Error msg))

      (#;Error msg)
      (#;Error msg))
    ))

The apply function is a bit more complicated than map, but it still (roughly) follows the same pattern:

1. Unwrap the data.
2. Handle all the cases.
3. Generate a wrapped output.

Applicatives are really nice and all, but we can still take things further with these functors.

Monads

If you listen to functional programmers, you'll likely get the impression that the invention of monads rivals the invention of the wheel. It is this incredibly powerful and fundamental abstraction for a lot of functional programs.

Monads extend applicatives by adding one key operation that allows you to concatenate or compound monadic values.

Why is that important?

Because, until now, we have only been able to use pure functions on our functorial values. That is, functions which don't cause (or require) any kind of side-effect during their computation.

Think about it: we can compute on the elements of lists, but if our function generates lists by itself, you can't just merge all the output lists together. You're just going to end up with a lousy list of lists.

Oh, and the functions you apply on your Error values better not fail, cause neither the Functor<Error> nor the Applicative<Error> are going to do anything about it.

Enter the Monad:

(sig: #export (Monad m)
  (: (A;Applicative m)
     applicative)
  (: (All [a]
       (-> (m (m a)) (m a)))
     join))

The thing about Monad is that with it, you can give map functions that also generate wrapped values (and take advantage of their special properties), and then you can collapse/merge/combine those values into a "joined" value by using (you guessed it) the join function.

Let's see that in action:

(;module:
  lux
  (lux/data/struct [list]))

(open list;Monad<List>)

(def foo (|> (list 1 2 3 4)
             (map (list;repeat 3))
             join
             ))

## The value of 'foo' is:
(list 1 1 1 2 2 2 3 3 3 4 4 4)

It's magic!

Not really. It's just the Monad<List>:

(def: unit (All [a] (List a)) #;Nil)

(def: (append xs ys)
  (All [a] (-> (List a) (List a) (List a)))
  (case xs
    #;Nil          ys
    (#;Cons x xs') (#;Cons x (append xs' ys))))

(struct: #export _ (Monad List)
  (def: applicative Applicative<List>)

  (def: (join list-of-lists) (|> list-of-lists reverse (fold append unit))))

The fold function is for doing incremental iterative computations.

Here, we're using it to build the total output list by concatenating all the input lists in our list-of-lists.

Monads are incredibly powerful, since being able to use the special power of our functor inside our mapping functions allows us to layer that power in complex ways.

But... you're probably thinking that writing a bunch of maps followed by joins is a very tedious process. And, you're right!

If functional programmers had to subject themselves to that kind of tedium all the time, they'd probably not be so excited about monads.

Time for the VIP treatment.

The do Macro

These macros always show up at the right time to saves us from our hurdles!

## Macro for easy concatenation of monadic operations.
(do Monad<Maybe>
  [x (f1 123)
   #let [y (f2 x)] ## #let enables you to use full-featured let-expressions
   z (f3 y)]
  (wrap (f4 z)))

The do macro allows us to write monadic code with great ease (it's almost as if we're just making let bindings).

Just tell it which Monad implementation you want, and it will write all the steps in your computation piece by piece using map and join without you having to waste your time with all the boilerplate.

Finally, whatever you write as the body of the do, it must result in a functorial/monadic value (in this case, a Maybe value).

Remember: join may collapse/merge/combine layers of the functor, but it never escapes it, and neither can you.

Also, I can't forget to tell you that the do macro binds the monad instance you're using to the local variable @, so you may refer to the monad using that short name anywhere within the do expression.

This can come in handy when calling some of the functions in the lux/control/monad module, which take monad structures as parameters.

Functors, applicatives and monads have a bad reputation for being difficult to understand, but hopefully I didn't botch this explanation too much.

Personally, I think the best way to understand functors and monads is to read different implementations of them for various types (and maybe write a few of your own).

For that, feel free to peruse the Lux Standard Library at your leisure.

This is the sort of think that you need to learn by intuition and kind of get the feel for.

Hopefully, you'll be able to get a feel for them in the next chapters, because we're going to be exploring a lot of monads from here on.

So, buckle-up, cowboy. This ride is about to get bumpy.

See you in the next chapter!