DEV Community

Giulio Canti
Giulio Canti

Posted on • Updated on

Functional design: tagless final

In the last article I wrote a time combinator which mimics the analogous Unix command: given an action IO<A>, we can derive an action IO<[A, number]> that returns the elapsed time along with the computed value

import { IO, io } from 'fp-ts/IO'
import { now } from 'fp-ts/Date'

export function time<A>(ma: IO<A>): IO<[A, number]> {
  return io.chain(now, start => io.chain(ma, a => io.map(now, end => [a, end - start])))
}
Enter fullscreen mode Exit fullscreen mode

There's still a problem though: time works with IO only.

What if we want a time combinator for Task? Or TaskEither? Or even ReaderTaskEither?

A small rewrite

Let's just rename io to a generic M (like M onad)

import { IO, io as M } from 'fp-ts/IO'
import { now } from 'fp-ts/Date'

export function time<A>(ma: IO<A>): IO<[A, number]> {
  return M.chain(now, start => M.chain(ma, a => M.map(now, end => [a, end - start])))
}
Enter fullscreen mode Exit fullscreen mode

The value io, exported by the fp-ts/IO module, contains the Monad instance of IO.

In fp-ts type-classes are encoded as interfacess and instances are encoded as static dictionaries containing the operations defined by the type-class.

So in the case of a Monad instance, we expect the following operations: map, of, ap and chain.

// fp-ts/IO.ts

export const io = {
  map: ...,
  of: ...,
  ap: ...,
  chain: ...
}
Enter fullscreen mode Exit fullscreen mode

Let's try to write a time combinator for Task using the same style

Lifting

In order to make the type-checker happy we must lift the now action, which has type IO<number>, to the Task monad.

Fortunately fp-ts provides a built-in fromIO function for that. fromIO transforms a IO<A> into a Task<A>, for all A.

import { Task, task as M, fromIO } from 'fp-ts/Task'
import * as D from 'fp-ts/Date'

export function time<A>(ma: Task<A>): Task<[A, number]> {
  const now = fromIO(D.now)
  return M.chain(now, start => M.chain(ma, a => M.map(now, end => [a, end - start])))
}
Enter fullscreen mode Exit fullscreen mode

That would work, but there's so much duplication.

If we ignore for a minute the first line of the body, the code is exactly the same as before, isn't it?

export function time<A>(ma: IO<A>): IO<[A, number]> {
  return M.chain(now, start => M.chain(ma, a => M.map(now, end => [a, end - start])))
}

export function time<A>(ma: Task<A>): Task<[A, number]> {
  return M.chain(now, start => M.chain(ma, a => M.map(now, end => [a, end - start])))
}
Enter fullscreen mode Exit fullscreen mode

That's the beauty of the monadic interface, we can handle synchronous and asynchronous computations with pretty much the same code.

Tagless final

So the idea is that the time combinator could support any monad M which is able to lift now.

Or, more generally, any monad M which is able to lift an action IO<A> to an action M<A>, for all A.

Let's encode such a capability into a type-class (i.e. an interface in TypeScript) named MonadIO

import { IO } from 'fp-ts/IO'
import { Monad1 } from 'fp-ts/Monad'
import { Kind, URIS } from 'fp-ts/HKT'

export interface MonadIO<M extends URIS> extends Monad1<M> {
  readonly fromIO: <A>(fa: IO<A>) => Kind<M, A>
}
Enter fullscreen mode Exit fullscreen mode

The type Kind<M, A> is how fp-ts encodes a generic type constructor M<A> of kind * -> * (TypeScript doesn't support Higher Kinded Types natively).

Let's rewrite the time combinator against the MonadIO interface (this style of programming is called "tagless final" or "MTL style"), passed in as an additional first parameter

export function time<M extends URIS>(
  M: MonadIO<M>
): <A>(ma: Kind<M, A>) => Kind<M, [A, number]> {
  const now = M.fromIO(D.now) // lifting
  return ma => M.chain(now, start => M.chain(ma, a => M.map(now, end => [a, end - start])))
}
Enter fullscreen mode Exit fullscreen mode

That's great, from now on we can use time with any monad which admits an instance of MonadIO!

Writing a MonadIO instance

In order to write a MonadIO instance for IO we must augment its Monad instance with the fromIO operation, which is just the identity function

import { URI, io } from 'fp-ts/IO'
import { identity } from 'fp-ts/function'

export const monadIOIO: MonadIO<URI> = {
  ...io,
  fromIO: identity
}
Enter fullscreen mode Exit fullscreen mode

Let's write a MonadIO instance for Task

import { URI, task, fromIO } from 'fp-ts/Task'

const monadIOTask: MonadIO<URI> = {
  ...task,
  fromIO: fromIO
}
Enter fullscreen mode Exit fullscreen mode

Now we can get a specialized version of time for a concrete type constructor by passing the corresponding MonadIO instance

// timeIO: <A>(ma: IO<A>) => IO<[A, number]>
const timeIO = time(monadIOIO)

// timeTask: <A>(ma: Task<A>) => Task<[A, number]>
const timeTask = time(monadIOTask)
Enter fullscreen mode Exit fullscreen mode

This approach has great benefits: when writing a function based on tagless final, the target monad of the function can be changed in the future, by the user.

Discussion (1)

Collapse
louy2 profile image
Yufan Lou

I was excited to see tagless final in TypeScript. Sadly this is not that. This is just one of the monad classes in mtl. Still cool, just the wrong title.

In Haskell the problem of this approach (mtl) is that the chain operator cannot be inlined and optimized away because of type class indirection. I wonder if the JIT compiler in V8 can do better.