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)
/ / \ \
/ / \ \
/ / \ \
/ / \ \
/ / \ \
Plus Applicative Chain Comonad
(zero) (of) (chain) (extract)
\ / \ / \
\ / \ / \
\ / \ / \
\ / \ / \
\ / \ / \
Alternative Monad ChainRec
(chainRec)
//https://github.com/sanctuary-js/sanctuary-type-classes#type-class-hierarchy
ADT (Algebraic Data Type)
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.[1] 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 Polymorphism
https://en.wikipedia.org/wiki/Ad_hoc_polymorphism
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 URI: 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 URI: F
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