Getting Started with fp-ts Part I: Introduction

December, 2021
An fp-ts tutorial for kids who can't fp-ts good and want to learn how to do other stuff good too.

fp-ts is a library (and growing ecosystem) for functional programming in TypeScript. It leverages a type system hack to provide Higher Kinded Types, a language feature that TypeScript doesn’t naively support. The goal is to facilitate the creation of well structured type safe applications using the same constructs as those found in purely functional languages like Haskell and PureScript. However, assembly instructions are not included:

Disclaimer. Teaching functional programming is out of scope of this project, so the documentation assumes you already know what FP is.

And thus, the motivation for this series. This first article with briefly cover some terms and concepts. However, understanding these concepts is not required to effectively use fp-ts.

Algebraic Structures

https://en.wikipedia.org/wiki/Algebraic_structure

An algebraic structure is a structure with a set of operations that may be performed on it. The operations must satisfy specific lawful constraints. Wikipedia lists Magama and Semigroup as examples of algebraic structures. For now just consider the meaning of “algebraic structure” to be an abstract concept that is used to describe or categorize a thing based on it’s behavior using math.

Type Classes

https://en.wikipedia.org/wiki/Type_class

Functor, Semigroup, Monad, etc., are all examples of type classes. Type classes may inherit from other type classes as the chart below illustrates. Type classes must implement specific lawful operations and are in fact algebraic structures if you want to think about them from a mathematical perspective.

Setoid   Semigroupoid  Semigroup   Foldable        Functor      Contravariant
Filterable
(equals)    (compose)    (concat)   (reduce)         (map)        (contramap)    (filter)
|           |           |           \         / | | | | \
|           |           |            \       /  | | | |  \
|           |           |             \     /   | | | |   \
|           |           |              \   /    | | | |    \
|           |           |               \ /     | | | |     \
Ord      Category     Monoid         Traversable | | | |      \
(lte)       (id)       (empty)        (traverse)  / | | \       \
|                      /  | |  \       \
|                     /   / \   \       \
|             Profunctor /   \ Bifunctor \
|              (promap) /     \ (bimap)   \
|                      /       \           \
Group                   /         \           \
(invert)               Alt        Apply      Extend
(alt)        (ap)     (extend)
/           / \           \
/           /   \           \
/           /     \           \
/           /       \           \
/           /         \           \
(zero)       (of)      (chain)    (extract)
\         / \         / \
\       /   \       /   \
\     /     \     /     \
\   /       \   /       \
\ /         \ /         \
(chainRec)
//https://github.com/sanctuary-js/sanctuary-type-classes#type-class-hierarchy

https://en.wikipedia.org/wiki/Algebraic_data_type

A simple example of an algebraic data type:

type Foo = 'Bar' | 'Baz'

In TypeScript a union is a “sum” type. In this example the algebraic operation ‘sum’ is used to define the type Foo which is either Bar or Baz. A more relevant example is Option which represents a value that may be null or undefined.

type Option<T> = Some<T> | None

fp-ts provides many useful ADTs like Option, Either, Array, Record, etc. These ADTs satisfy the laws of various type classes. For example Option, Either, Array and Record are all Functor instances.

Parametric Polymorphism

https://en.wikipedia.org/wiki/Parametric_polymorphism

In programming languages and type theory, parametric polymorphism is a way to make a language more expressive, while still maintaining full static type-safety. Using parametric polymorphism, a function or a data type can be written generically so that it can handle values identically without depending on their type. Such functions and data types are called generic functions and generic datatypes respectively and form the basis of generic programming. Parametric polymorphism

In TypeScript parametric polymophism is accomplished using generics.

const identity<T>(x: T): T => x

Ad hoc polymophism refers to a functions that operates differently on different types of parameters. In TypeScript ad hoc polymophism is implemented using function overloading.

const cat = {
type: 'cat' as const,
name: 'Tom',
getCatName() {
console.log(this.name)
}
}

type Cat = typeof cat

const mouse = {
type: 'mouse' as const,
name: 'Jerry',
getMouseName() {
console.log(this.name)
}
}

type Mouse = typeof mouse

function logName(mouse: Mouse, alias: string): void
function logName(cat: Cat): void
function logName(x: Mouse | Cat, alias?: string) {
if(x.type === 'mouse') {
if(alias) {
console.log(alias)
} else {
x.getMouseName()
}
} else {
x.getCatName()
}
}

logName(mouse, 'Cheese Fiend')
logName(cat)

Higher Kinded Types

https://en.wikipedia.org/wiki/Kind_(type_theory)

If TypeScript supported higher kinded types it wold be possible to write generic types, that receive generic type parameters like this.

interface Functor<H<T>> {
map<U>(func: (value: T) => U): H<U>;
}

Programming With Types 11.1.3

However, this is not possible in TypeScript, so fp-ts uses a bit of a hack to achieve similar results. This is why the type signatures can be very large and difficult to understand.

/**
* @category type classes
* @since 2.0.0
*/
export interface Functor<F> {
readonly map: <A, B>(fa: HKT<F, A>, f: (a: A) => B) => HKT<F, B>
}
/**
* @category type classes
* @since 2.0.0
*/
export interface Functor1<F extends URIS> {
readonly map: <A, B>(fa: Kind<F, A>, f: (a: A) => B) => Kind<F, B>
}
// and more for Functor2, Functor3, ...

This technique is how type classes are implemented in fp-ts. See the documentation for more information. https://gcanti.github.io/fp-ts/guides/HKT.html

In the area of mathematical logic and computer science known as type theory, a kind is the type of a type constructor… Kind (type theory)

Think of a higher kinded type as a generic type that receives a generic type parameter.

Higher Kinded Polymorphism

Polymorphism abstracts types, just as functions abstract values. Higher-kinded polymorphism takes things a step further, abstracting both types and type constructors https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-kinded-polymorphism.pdf

Suppose that you wanted to write a generic lift function for both Identity and Either. In fp-ts you have to supply an instance to the constructor for proper type inference. In this example lift supports constructors with up to two kinds by the use of Functor2 and Kind2. This is how higher-kinded polymorphism is defined using fp-ts. It’s the reason why the type signatures are so complex.

export function lift<F extends URIS2>(
F: Functor2<F>
): <A, B>(f: (a: A) => B) => <E>(fa: Kind2<F, E, A>) => Kind2<F, E, B>
export function lift<F extends URIS>(F: Functor1<F>): <A, B>(f: (a: A) => B) => (fa: Kind<F, A>) => Kind<F, B>
export function lift<F>(F: Functor<F>): <A, B>(f: (a: A) => B) => (fa: HKT<F, A>) => HKT<F, B>
export function lift<F>(F: Functor<F>): <A, B>(f: (a: A) => B) => (fa: HKT<F, A>) => HKT<F, B> {
return (f) => (fa) => F.map(fa, f)
}

// https://gcanti.github.io/fp-ts/guides/HKT.html

Here is an example of creating a specific lift instance by providing a constructor.

const double = (n: number): number => n * 2

const liftIdentity = lift(identity)
liftIdentity(double)

const liftEither = lift(either)
liftEither(double)

// https://gcanti.github.io/fp-ts/guides/HKT.html