loading...

Getting started with fp-ts: Applicative

gcanti profile image Giulio Canti Updated on ・4 min read

In the last post we saw that we can compose an effectful program f: (a: A) => F<B> with a pure program g: (b: B) => C by lifting g to a function lift(g): (fb: F<B>) => F<C> provided that F admits a functor instance

Program f Program g Composition
pure pure g ∘ f
effectful pure (unary) lift(g) ∘ f

However g must be unary, that is it must accept only one argument as input. What if g accepts two arguments? Can we still lift g by using only the functor instance? Well, let's try!

Currying

First of all we must model a function that accepts two arguments, let's say of type B and C (we can use a tuple) and returns a value of type D

g: (args: [B, C]) => D

We can rewrite g using a technique called currying.

Currying is the technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument. For example, a function that takes two arguments, one from B and one from C, and produces outputs in D, by currying is translated into a function that takes a single argument from C and produces as outputs functions from B to C.

(source: currying on wikipedia.org)

So we can rewrite g to

g: (b: B) => (c: C) => D

What we want is a lifting operation, let't call it liftA2 in order to distinguish it from our old lift, that outputs a function with the following signature

liftA2(g): (fb: F<B>) => (fc: F<C>) => F<D>

How can we get there? Since g is now unary, we can use the functor instance and our old lift

lift(g): (fb: F<B>) => F<(c: C) => D>

But now we are stuck: there's no legal operation on the functor instance which is able to unpack the value F<(c: C) => D> to a function (fc: F<C>) => F<D>.

Apply

So let's introduce a new abstraction Apply that owns such a unpacking operation (named ap)

interface Apply<F> extends Functor<F> {
  ap: <C, D>(fcd: HKT<F, (c: C) => D>, fc: HKT<F, C>) => HKT<F, D>
}

The ap function is basically unpack with the arguments rearranged

unpack: <C, D>(fcd: HKT<F, (c: C) => D>) => ((fc: HKT<F, C>) => HKT<F, D>)
ap:     <C, D>(fcd: HKT<F, (c: C) => D>, fc: HKT<F, C>) => HKT<F, D>

so ap can be derived from unpack (and viceversa).

Note: the HKT type is the fp-ts way to represent a generic type constructor (a technique proposed in the Lightweight higher-kinded polymorphism paper) so when you see HKT<F, X> you can think to the type constructor F applied to the type X (i.e. F<X>).

Applicative

Moreover it would be handy if there exists an operation which is able to lift a value of type A to a value of type F<A>. This way we could call the liftA2(g) function either by providing arguments of type F<B> and F<C> or by lifting values of type B and C.

So let's introduce the Applicative abstraction which builds upon Apply and owns such operation (named of)

interface Applicative<F> extends Apply<F> {
  of: <A>(a: A) => HKT<F, A>
}

Let's see the Applicative instances for some common data types

Example (F = Array)

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

const applicativeArray = {
  map: <A, B>(fa: Array<A>, f: (a: A) => B): Array<B> => fa.map(f),
  of: <A>(a: A): Array<A> => [a],
  ap: <A, B>(fab: Array<(a: A) => B>, fa: Array<A>): Array<B> =>
    flatten(fab.map(f => fa.map(f)))
}

Example (F = Option)

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

const applicativeOption = {
  map: <A, B>(fa: Option<A>, f: (a: A) => B): Option<B> =>
    isNone(fa) ? none : some(f(fa.value)),
  of: <A>(a: A): Option<A> => some(a),
  ap: <A, B>(fab: Option<(a: A) => B>, fa: Option<A>): Option<B> =>
    isNone(fab) ? none : applicativeOption.map(fa, fab.value)
}

Example (F = Task)

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

const applicativeTask = {
  map: <A, B>(fa: Task<A>, f: (a: A) => B): Task<B> => () => fa().then(f),
  of: <A>(a: A): Task<A> => () => Promise.resolve(a),
  ap: <A, B>(fab: Task<(a: A) => B>, fa: Task<A>): Task<B> => () =>
    Promise.all([fab(), fa()]).then(([f, a]) => f(a))
}

Lifting

So given an instance of Apply for F can we now write liftA2?

import { HKT } from 'fp-ts/lib/HKT'
import { Apply } from 'fp-ts/lib/Apply'

type Curried2<B, C, D> = (b: B) => (c: C) => D

function liftA2<F>(
  F: Apply<F>
): <B, C, D>(g: Curried2<B, C, D>) => Curried2<HKT<F, B>, HKT<F, C>, HKT<F, D>> {
  return g => fb => fc => F.ap(F.map(fb, g), fc)
}

Nice! But what about functions with three arguments? Do we need yet another abstraction?

The good news is that the answer is no, Apply is enough

type Curried3<B, C, D, E> = (b: B) => (c: C) => (d: D) => E

function liftA3<F>(
  F: Apply<F>
): <B, C, D, E>(
  g: Curried3<B, C, D, E>
) => Curried3<HKT<F, B>, HKT<F, C>, HKT<F, D>, HKT<F, E>> {
  return g => fb => fc => fd => F.ap(F.ap(F.map(fb, g), fc), fd)
}

Actually given an instance of Apply we can write a liftAn function, for each n.

Note. liftA1 is just lift, the Functor operation.

We can now update our "composition table"

Program f Program g Composition
pure pure g ∘ f
effectful pure, n-ary liftAn(g) ∘ f
where liftA1 = lift

Is the general problem solved?

Not yet. There's still an important case which is missing: what if both programs are effectful?

Again we need something more: in the next post I'll talk about one of the most important abstractions of functional programming: monads.

TLDR: functional programming is all about composition

Posted on by:

Discussion

markdown guide
 

Last year I read a 700-pages book about Haskell - and I never got the feeling of actually understanding what is going on (like even the basic concepts).

And reading these articles for real kicked me in - I don't know if I just needed another try to align the knowledge in my head or you are just that good at explaining things - either way, my eternal gratitude.