Getting started with fp-ts: Monad

In the last post we saw that we can compose an effectful program f: (a: A) => M<B> with a pure n-ary program g by lifting g, provided that M admits an applicative functor instance

Program f	Program g	Composition
pure	pure	g ∘ f
effectful	pure, n-ary	liftAn(g) ∘ f

where liftA1 = lift

However we must solve one last case: what if both programs are effectful?

f: (a: A) => M<B>
g: (b: B) => M<C>

What's the "composition" of such f and g?

In order to handle this last case we need something more powerful than Functor since it's quite easy to end up with nested contexts.

The problem: nested contexts

To better explain why we need something more, let's see some examples.

Example (M = Array)

Say we want to retrive the followers of the followers of a Twitter user:

interface User {
  followers: Array<User>
}

const getFollowers = (user: User): Array<User> => user.followers

declare const user: User

const followersOfFollowers: Array<Array<User>> = getFollowers(user).map(getFollowers)

There's something wrong here, followersOfFollowers has the type Array<Array<User>> but we want Array<User>.

We need to flatten the nested arrays.

The flatten: <A>(mma: Array<Array<A>>) => Array<A> function exported by fp-ts comes in handy

import { flatten } from 'fp-ts/Array'

const followersOfFollowers: Array<User> = flatten(getFollowers(user).map(getFollowers))

Nice! What about other data structures?

Example (M = Option)

Say we want to calculate the inverse of the head of a numeric list

import { Option, some, none, option } from 'fp-ts/Option'
import { head } from 'fp-ts/Array'

const inverse = (n: number): Option<number> => (n === 0 ? none : some(1 / n))

const inverseHead: Option<Option<number>> = option.map(head([1, 2, 3]), inverse)

Opss, I did it again, inverseHead has the type Option<Option<number>> but we want Option<number>.

We need to flatten the nested Options.

import { isNone } from 'fp-ts/Option'

const flatten = <A>(mma: Option<Option<A>>): Option<A> => (isNone(mma) ? none : mma.value)

const inverseHead: Option<number> = flatten(option.map(head([1, 2, 3]), inverse))

All those flatten functions... It's not a coincidence, there's a functional pattern under the hood.

Indeed all those type constructors (and many others) admit a monad instance and

flatten is the most peculiar operation of monads

So what's a monad?

This is how monads are often presented...

Definition

A monad is defined by three things:

(1) a type constructor M which admits a Functor instance

(2) a function of with the following signature

of: <A>(a: A) => HKT<M, A>

(3) a function flatMap with the following signature

flatMap: <A, B>(f: (a: A) => HKT<M, B>) => ((ma: HKT<M, A>) => HKT<M, B>)

Note: recall that the HKT type is the fp-ts way to represent a generic type constructor, so when you see HKT<M, X> you can think to the type constructor M applied to the type X (i.e. M<X>).

The functions of and flatMap are required to obey three laws:

• flatMap(of) ∘ f = f (Left identity)
• flatMap(f) ∘ of = f (Right identity)
• flatMap(h) ∘ (flatMap(g) ∘ f) = flatMap((flatMap(h) ∘ g)) ∘ f (Associativity)

where f, g, h are all effectful functions and ∘ is the usual function composition.

Ok but... why?

Back in the day when I first saw such a definition my first reaction was bewilderment.

All these questions were spinning around in my head:

• why those two particular operations and why they have those types?
• why the name "flatMap"?
• why the laws? What do they mean?
• but above all, where's my flatten?

This post will try to answer each question.

Let's get back to our problem: what's the composition of two effectful functions (also called Kleisli arrows)?

(two Kleisli arrows, what's their composition?)

I don't even know what its type is.

Wait... we already encountered an abstraction that is all about composition. Do you remember what I said about categories?

Categories capture the essence of composition

We can turn our problem into a category problem: can we find a category that models the composition of Kleisli arrows?

The Kleisli category

Let's try to build a category K (named Kleisli category) which only contains effectful functions:

• the objects are the same objects of the TS category, that is all the TypeScript types.
• the morphisms are built like this: whenever there's a Kleisli arrow f: A ⟼ M<B> in TS we draw an arrow f': A ⟼ B in K

(above the TS category, below the K construction)

So what would be the composition of f' and g' in K? That's the dashed arrow labeled h' in the image below

(above the composition in the TS category, below the composition in the K construction)

Since h' is an arrow that goes from A to C, there should be a corresponding function h from A to M<C> in TS.

So a good candidate for the composition of f and g in TS is still an effectful function with the following signature: (a: A) => M<C>.

How can we build such a function? Well, let's try!

In which we build the composition step by step

The point (1) of the monad defintion says the M admits a functor instance, so we can lift the function g: (b: B) => M<C> to a function lift(g): (mb: M<B>) => M<M<C>> (here I'm using its synonym map)

(where flatMap comes from)

And now we are stuck: there's no legal operation on the functor instance which is able to flatten a value of type M<M<C>> to a value of type M<C>, we need an additional flatten operation.

If we can define such operation then we can obtain the composition we are looking for

h = flatten ∘ map(g) ∘ f

But wait, flatten ∘ map(g) is flatMap, that's where the name comes from!

h = flatMap(g) ∘ f

We can now update our "composition table"

Program f	Program g	Composition
pure	pure	g ∘ f
effectful	pure, n-ary	liftAn(g) ∘ f
effectful	effectful	flatMap(g) ∘ f

where liftA1 = lift

What about of? Well, of comes from the identity morphisms in K: for each identity morphism 1_A in K there should be a corresponding function from A to M<A> (i.e. of: <A>(a: A) => M<A>).

(where of comes from)

The laws

Last question: where do the laws come from? They are just the category laws in K translated into TS:

Law	K	TS
Left identity	1B ∘ f' = f'	flatMap(of) ∘ f = f
Right identity	f' ∘ 1A = f'	flatMap(f) ∘ of = f
Associativity	h' ∘ (g' ∘ f') = (h' ∘ g') ∘ f'	flatMap(h) ∘ (flatMap(g) ∘ f) = flatMap((flatMap(h) ∘ g)) ∘ f

Monads in fp-ts

In fp-ts the flatMap function is modeled by a variant called chain, which is basically flatMap with the arguments rearranged

flatMap: <A, B>(f: (a: A) => HKT<M, B>) => ((ma: HKT<M, A>) => HKT<M, B>)
chain:   <A, B>(ma: HKT<M, A>, f: (a: A) => HKT<M, B>) => HKT<M, B>

Note that chain can be derived from flatMap (and viceversa).

Now if we get back to the examples showing the problem with nested contexts we can fix them by using chain

import { array, head } from 'fp-ts/Array'
import { Option, option } from 'fp-ts/Option'

const followersOfFollowers: Array<User> = array.chain(getFollowers(user), getFollowers)

const headInverse: Option<number> = option.chain(head([1, 2, 3]), inverse)

Conclusion

Functional programming provides universal ways to compose functions with effects: functors, applicative functors and monads are all abstractions that offer principled tools for composing different kind of programs.

TLDR: functional programming is really all about composition

Comments

[JEROME MARTIN]

So many thanks for your work that is both precise and pedagogic. I have read several articles about functional programming and never could understand how everythings fits together. Your articles have enlightened me.

[Oleksandr Mizov]

Hellow Giulio Canti!
Thank you for the article series. They are really descriptive and informative.
Have a question/ suggestion about current article. At the definition section we have following ponit:
(1) a type constructor M which admits a Functor instance
I am curious if it should be:
(1) a type constructor M which admits an Applicative instance

[jinlong]

So how to compose effectful program f and effectful, n-ary program g?

[markamccann]

Thank you so much! After working through your series of blogs, I feel like I understand Monads, Functors and all of the related concepts for the first time. Even though doing this in TypeScript rather than JavaScript seems more complicated at first glance, it actually helped me understand what is really going on due to the natural mapping of Category theory to TS's type system.

[Matt Grande]

Hi there, near the start of the article you have "bad" examples, showing why Monads/flatMap/chain is needed.

It'd be nice if, at the end, you showed how they're better with a chain in there.

Great series, thank you!

[Giulio Canti]

Good idea, thanks

[Matt Grande]

You work fast! Thank you :)

[Aaron Elligsen]

I am enjoying these articles. However, I think it doesn't quite motivate why I would want to use a monad.

Clearly, it gives me composition, but how often is a javascript program solely made up of transformations like map? Moreover if I have multiple steps of transformation, why would I run it as multiple steps rather than composing the steps into one function and running that? Clearly, some steps can't be combined if they're dependent on async data. Promise is a bit of an anemic monad but for the purposes of typescript it is typesafe, has convenient syntax, and is nearly a no cost abstraction.

Let say I rewrite an arbitrary program in this style, if I had a non-monadic type safe program before refactoring and a type safe program after, what do I really gain for bringing in this abstraction? The two programs should be isomorphic in essence.

I feel like it replaces a sequences of statements with a sequence of expressions. The type signature of chain and flatMap result in examples which are very linear, this item is processed after that, but often I need to deal with branching. One effect kicks off many effects which may have unrelated concerns, how does composition improve this situation?

Another article does a really good job of motivating the effect applicative. jrsinclair.com/articles/2018/how-t... It helps me see why I would want to use the effect applicative in JS/TS. It adds a useful feature to a program, i.e. laziness, but what does or what could a monadic interface bring to a program? I know half the answer here is composition, but what can composition bring to a program that it didn't have before? Another way to put it is that the only usefulness of monads seems proportional to the how much you use composition.

[Daniel Steigerwald]

I recommend this talk youtube.com/watch?v=Nrp_LZ-XGsY

[Aaron Elligsen]

It was a bit meandering but this was a question asking if is it worth it to refactor an imperative style program into a functional monadic style program.

I would appreciate feedback. I'm on the fence regarding this. Has anyone done so? What was the experience like and how was the outcome?

[Aaron Elligsen]

Since no one has answered, I guess I'll answer my own question. Monads, the concept, don't really add anything to a program per se. It is the particular instances of monads themselves which add value. The monadic pattern allows you to compose many instances of monads which add features. Thus the only value in the monadic pattern is acting as the glue with which to compose all the separate features.

Monads are the plumbing which deliver value from the things they are connecting.

[Christian Gill]

I'm really enjoying your series, super helpful!

Small request, could you add a series field to the posts so they would be linked. 🙏

[Giulio Canti]

Thanks for the tip