Getting started with fp-ts: Functor

In the last post about categories I presented the TS category (the TypeScript category) and the central problem with function composition

How can we compose two generic functions f: (a: A) => B and g: (c: C) => D?

Why finding solutions to this problem is so important?

Because if categories can be used to model programmming languages, morphisms (i.e. functions in TS) can be used to model programs.

Therefore solving the problem also means to find how to compose programs in a general way. And this is pretty interesting for a developer, isn't it?

Functions as programs

We call pure program a function with the following signature

(a: A) => B

Such a signature models a program which accepts an input of type A and yields a result of type B, without any effect.

We call effectful program a function with the following signature

(a: A) => F<B>

Such a signature models a program which accepts an input of type A and yields a result of type B, along with an effect F, where F is some type constructor.

Recall that a type constructor is an n-ary type operator taking as argument zero or more types, and returning another type.

Example

Given the concrete type string, the Array type constructor returns the concrete type Array<string>

Here we are interested in n-ary type constructors with n >= 1, for example

Type constructor	Effect (interpretation)
Array<A>	a non deterministic computation
Option<A>	a computation that may fail
Task<A>	an asynchronous computation

Now back to our main problem

How can we compose two generic functions f: (a: A) => B and g: (c: C) => D?

Since the general problem is intractable, we need to put some constraint on B and C.

We already know that if B = C then the solution is the usual function composition

function compose<A, B, C>(g: (b: B) => C, f: (a: A) => B): (a: A) => C {
  return a => g(f(a))
}

What about the other cases?

In which the constraint B = F<C> leads to functors

Let's consider the following constraint: B = F<C> for some type constructor F, or in other words (and after some renaming)

• f: (a: A) => F<B> is an effectful program
• g: (b: B) => C is a pure program

In order to compose f with g we could find a way to lift g from a function (b: B) => C to a function (fb: F<B>) => F<C> so that we can use the usual function composition (the output type of f would be the same as the input type of the lifted function)

So we turned the original problem into another one: can we find such a lift function?

Let's see some examples

Example (F = Array)

function lift<B, C>(g: (b: B) => C): (fb: Array<B>) => Array<C> {
  return fb => fb.map(g)
}

Example (F = Option)

import { Option, isNone, none, some } from 'fp-ts/Option'

function lift<B, C>(g: (b: B) => C): (fb: Option<B>) => Option<C> {
  return fb => (isNone(fb) ? none : some(g(fb.value)))
}

Example (F = Task)

import { Task } from 'fp-ts/Task'

function lift<B, C>(g: (b: B) => C): (fb: Task<B>) => Task<C> {
  return fb => () => fb().then(g)
}

All those lift functions almost look the same. It's not a coincidence, there's a functional pattern under the hood.

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

Functors

Functors are mappings between categories that preserve the categorical structure, i.e. that preserve identity morphisms and composition.

Since categories are constituted of two things (objects and morphisms) a functor is constituted of two things as well:

• a mapping between objects that associates to each object X in C an object in D
• a mapping between morphisms that associates to each morphism in C a morphism in D

where C and D are two categories (aka two programming languages).

(source: functor on ncatlab.org)

Even if a mapping between two different programming languages is an intriguing idea, we are more interested in a mapping where C and D coincide (with TS). In this case we talk about endofunctors ("endo" means "within", "inside").

From now on when I write "functor" I actually mean an endofunctor in TS.

Definition

A functor is a pair (F, lift) where

• F is a n-ary type constructor (n >= 1) which maps each type X to the type F<X> (mapping between objects)
• lift is a function with the following signature

lift: <A, B>(f: (a: A) => B) => ((fa: F<A>) => F<B>)

which maps each function f: (a: A) => B to a function lift(f): (fa: F<A>) => F<B> (mapping between morphisms).

The following properties must hold

• lift(identity_X) = identity_F(X) (identities map to identities)
• lift(g ∘ f) = lift(g) ∘ lift(f) (mapping a composition is the composition of the mappings)

The lift function is also known through a variant called map, which is basically lift with the arguments rearranged

lift: <A, B>(f: (a: A) => B) => ((fa: F<A>) => F<B>)
map:  <A, B>(fa: F<A>, f: (a: A) => B) => F<B>

Note that map can be derived from lift (and viceversa).

Functors in fp-ts

How can we define a functor instance in fp-ts? Let's see a practical example.

The following declaration defines a model for the response of an API call

interface Response<A> {
  url: string
  status: number
  headers: Record<string, string>
  body: A
}

Note that the body field is parametrized, this makes Response a good candidate for a functor instance since Response is a n-ary type constructors with n >= 1 (a necessary precondition).

In order to define a functor instance for Response we must define a map function (along with some technicalities required by fp-ts)

// `Response.ts` module

import { Functor1 } from 'fp-ts/Functor'

export const URI = 'Response'

export type URI = typeof URI

declare module 'fp-ts/HKT' {
  interface URItoKind<A> {
    Response: Response<A>
  }
}

export interface Response<A> {
  url: string
  status: number
  headers: Record<string, string>
  body: A
}

function map<A, B>(fa: Response<A>, f: (a: A) => B): Response<B> {
  return { ...fa, body: f(fa.body) }
}

// functor instance for `Response`
export const functorResponse: Functor1<URI> = {
  URI,
  map
}

Is the general problem solved?

Not at all. Functors allow us to compose an effectful program f with a pure program g, but g must be unary, that is it must accept only one argument as input. What if g accepts two arguments? Or three?

Program f	Program g	Composition
pure	pure	g ∘ f
effectful	pure (unary)	lift(g) ∘ f
effectful	pure (n-ary, n > 1)	?

In order to handle such circumstances we need something more: in the next post I'll talk about another remarkable abstraction of functional programming: applicative functors.

TLDR: functional programming is all about composition

Comments

[Kamil Szot]

What's functorResponse good for? You defined it while dropping a ton of boilerplate from HKT without explaining it and without providing any use case. That's the point in your series when I felt like hand-waving started and wasn't able to say 'Yes. I understand fully what you mean.'

However otherwise it's really great write up about category theory concepts. It got me way closer to understanding who it works and what might be the value of it than any other thing I read earlier. I especially like the parallels you drew between increasingly complex contexts (like how lift relates to map, and ap relates to unpack) and examples with Arrays, Options, Promises (I'm not sure why but Arrays seem to be hardest for me to understand, especially when talking about applicative functors, others are just specific boxes over single value, arrays are weird because they have multiple values). I also very much liked the drawing in last parts that can give intuition why a thing is called 'lift'. You might want to add some of those in this part where you first introduce 'lift'.

Great job! Thank you for that!

[thekemlin]

I spent four years learning functional programming, but, I
I really understand it after reading your blog. Thank you!

[Christian Takle]

Small typo:

Since categories are constituted of two things (objects and morphisms) a funtor is constituted of two things as well

funtor -> functor

[Romain Deneau]

Great article. For typescripters, talking about generic types can be simpler than "n-ary type constructors with n >= 1", don't you think?

[Jens Ahlsten Herlevsen]

"How can we compose two generic functions f: (a: A) => B and g: (c: C) => D"

Don't you mean "g: (b: B) => C"?

And thank you for writing these articles, they are very helpful :-)

[Dmitry Mazurok]

Composing f: (a: A) => B and g: (b: B) => C is trivial by normal function composition.

What is challenging is composing f and g when output type of f isn't the same as input type of g. And that is impossible to do if these output-input types are completely arbitrary.

So what we do is we try to introduce some dependency between them ("what if output of f is F<input of g>?") and see if we can somehow compose them NOW, with that constraint in place.

Turns out we CAN - if F is a functor.

[pradeepdas]

Taking the concrete problem of two generic functions f: (a: A) => B and g: (c: C) => D

Can you show how a Response Functor solves the composition when B != C

[Marco Faustinelli]

First time I see a map :: (m a, a -> b) -> m b. How do you relate it to lift precisely?

I always saw map :: (a -> b) -> m a -> m b. Basically, the canonical map is "your" map curried.

What is the advantage of using map with your types? How does it help understand function composition?

[mohammadreza-esmailzadeh]

So we can interpret Map < A , B > as a computation that returns a mapping function on A and return B?