Skip to content

Instantly share code, notes, and snippets.

@NikitaIT
Forked from gcanti/fp-ts-technical-overview.md
Created September 13, 2020 13:16
Show Gist options
  • Save NikitaIT/da7767866398e3ad4443dd1fb197659d to your computer and use it in GitHub Desktop.
Save NikitaIT/da7767866398e3ad4443dd1fb197659d to your computer and use it in GitHub Desktop.
fp-ts technical overview

Technical overview

A basic Option type

// Option.ts

// definition
export class None {
  readonly tag: 'None' = 'None'
}

export class Some<A> {
  readonly tag: 'Some' = 'Some'
  constructor(readonly value: A) {}
}

export type Option<A> = None | Some<A>

// helpers
export const none: Option<never> = new None()

export const some = <A>(a: A): Option<A> => {
  return new Some(a)
}

// a specialised map for Option
const map = <A, B>(f: (a: A) => B, fa: Option<A>): Option<B> => {
  switch (fa.tag) {
    case 'None':
      return fa
    case 'Some':
      return some(f(fa.value))
  }
}

Usage

const double = (n: number): number => n * 2
const len = (s: string): number => s.length

console.log(map(double, some(1))) // { tag: 'Some', value: 2 }
console.log(map(double, none)) // { tag: 'None' }
console.log(map(len, some(2))) // <= static error: Type 'number' is not assignable to type 'string'

Adding static land support

TypeScript doesn't support higher kinded types

interface Functor {
  map: <A, B>(f: (a: A) => B, fa: ?) => ?
}

but we can fake them with an interface

// HKT.ts

export interface HKT<F, A> {
  _URI: F
  _A: A
}

where F is a unique identifier representing the type constructor and A its type parameter.

Now we can define a generic Functor interface

// Functor.ts

import { HKT } from './HKT'

export interface Functor<F> {
  map: <A, B>(f: (a: A) => B, fa: HKT<F, A>) => HKT<F, B>
}

and redefine the Option type

// Option.ts

// unique identifier
export const URI = 'Option'

export type URI = typeof URI

export class None {
  readonly _URI!: URI
  readonly _A!: never
  readonly tag: 'None' = 'None'
}

export class Some<A> {
  readonly _URI!: URI
  readonly _A!: A
  readonly tag: 'Some' = 'Some'
  constructor(readonly value: A) {}
}

export type Option<A> = None | Some<A>

export const none: Option<never> = new None()

export const some = <A>(a: A): Option<A> => {
  return new Some(a)
}

const map = <A, B>(f: (a: A) => B, fa: Option<A>): Option<B> => {
  switch (fa.tag) {
    case 'None':
      return fa
    case 'Some':
      return some(f(fa.value))
  }
}

Let's define an instance of Functor for Option

// static land Functor instance
export const option: Functor<URI> = {
  map
}

There's a problem though, this code doesn't type-check with the following error

Type 'HKT<"Option", A>' is not assignable to type 'Option<A>'

Every Option<A> is a HKT<"Option", A> but the converse is not true. In order to fix this (we know that Option<A> = HKT<"Option", A>) functions like map should accept the more general version HKT<"Option", A> and return the more specific version Option<A>

const map = <A, B>(f: (a: A) => B, hfa: HKT<URI, A>): Option<B> => {
  const fa = hfa as Option<A>
  switch (fa.tag) {
    case 'None':
      return fa
    case 'Some':
      return some(f(fa.value))
  }
}

export const option: Functor<URI> = {
  map // no error
}

There's another issue though: when trying to use the instance we don't get an Option as a result

// x: HKT<"Option", number>
const x = option.map(double, some(1))

we get an HKT<"Option", number>.

We must somehow teach TypeScript that HKT<"Option", number> is really Option<number>, or more generally that HKT<"Option", A> is Option<A> for all A.

We'll use a feature called Module Augmentation for that.

Let's move the HKT definition to its own file and add a type-level map named URI2HKT

// HKT.ts

export interface HKT<F, A> {
  _URI: F
  _A: A
}

// type-level map, maps a URI to its corresponding type
export interface URI2HKT<A> {}

Let's add some helpers types

// all URIs
export type URIS = keyof URI2HKT<any>

// given a URI and a type, extracts the corresponding type
export type Type<URI extends URIS, A> = URI2HKT<A>[URI]

Adding an entry to the type-level map URI2HKT means to leverage the module augmentation feature

// Option.ts

declare module './HKT' {
  interface URI2HKT<A> {
    Option: Option<A> // maps the type literal "Option" to the type `Option`
  }
}

Now we can redefine Functor in order to leverage this type-level machinery

// Functor.ts

import { URIS, Type } from './HKT'

export interface Functor1<F extends URIS> {
  map: <A, B>(f: (a: A) => B, fa: Type<F, A>) => Type<F, B>
}

and fix the instance definition

// Option.ts

import { Functor1 } from './Functor'

const map = <A, B>(f: (a: A) => B, fa: Option<A>): Option<B> => {
  switch (fa.tag) {
    case 'None':
      return fa
    case 'Some':
      return some(f(fa.value))
  }
}

export const option: Functor1<URI> = {
  map
}

// x: Option<number>
const x = option.map(double, some(1))

Adding fantasy land support

Let's add a map method to None and Some

// Option.ts

export class None<A> {
  readonly _URI!: URI
  readonly _A!: never
  readonly tag: 'None' = 'None'
  map<B>(f: (a: A) => B): Option<B> {
    return none
  }
}

export class Some<A> {
  readonly _URI!: URI
  readonly _A!: A
  readonly tag: 'Some' = 'Some'
  constructor(readonly value: A) {}
  map<B>(f: (a: A) => B): Option<B> {
    return some(f(this.value))
  }
}

export type Option<A> = None<A> | Some<A>

Note that None has a type parameter now, because the signature of map (the method) must be the same for both None and Some otherwise TypeScript will complain.

The implementation of map (the static function) is now trivial.

const map = <A, B>(f: (a: A) => B, fa: Option<A>) => {
  return fa.map(f)
}

We can now use a nice chainable API (a kind of do notation)

// x: Option<number>
const x = some('foo')
  .map(len)
  .map(double)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment