Static Land Specification

This specification describes a set of JavaScript interfaces and algebraic laws that are common in some other functional languages like Haskell.

Module

A module is a JavaScript object with some static functions and/or values, "static" meaning they don't use this.

Here is an example:

const FooModule = {
  foo: 1,            // a value
  bar: (x) => x + 1, // a function
}

Note that this has nothing to do with JavaScript module systems like ES6 modules, in this specification a module is just an object.

Module Signature

Module signature describes an interface that a module can match. The syntax is very similar to that of Flow or TypeScript. Here is an example of a signature that the FooModule above matches:

Foo {
  foo: number,
  bar: (number) => number
}

A signature can be parameterized by a type, which looks like this:

ParameterizedFoo<T> {
  foo: T,
  bar: (T) => T
}

A module matches a parameterized signature, if there is some concrete type such that if we substitute all occurrences of T in the signature with that type, the module will match resulting signature. For example if we substitute T in ParameterizedFoo with number we get a signature that FooModule matches, therefore FooModule matches ParameterizedFoo.

Also functions in a signature can have type variables. These variables are specified in <> at the beginning of a function type. For instance:

Bar<T> {
  baz: <a>(a) => T<a>
}

Notice that T can be parameterized as well. The number of type variables of T becomes unambiguous when T is used inside the signature.

Also notice that signature level type variables are fixed for a module, while a function level variable can be substituted with a different concrete type in each function application. In other words we must choose what T stands for when we create a module, and we must choose what a stands for only when we apply baz to some value.

A type signature may be a part of another type signature, which means that we should pass a module that matches that signature in that place. For example:

Baz {
  compute: <a>(a, ParameterizedFoo<a>) => a
}

The above means that when we apply compute to say number we must pass as the second argument a module that matches ParameterizedFoo with T=number, like so:

someBaz.compute(10, FooModule)

Equivalence

An appropriate definition of equivalence for the given value should ensure that the two values can be safely swapped out in a program that respects abstractions.

For example:

Two lists are equivalent if they are equivalent at all indices.
Two plain old JavaScript objects, interpreted as dictionaries, are equivalent when they are equivalent for all keys.
Two promises are equivalent when they yield equivalent values.
Two functions are equivalent if they yield equivalent outputs for equivalent inputs.

Note that these examples are not universal, in some cases different definitions of equivalence for those types might be more appropriate. It depends on which exact abstractions you choose to use in a program.

We use ≡ symbol in laws to denote equivalence.

Parametricity

All methods' implementations should only use type information about arguments that is known from the signatures. Inspecting arguments or values that they produce or contain to get more information about their types is not allowed. In other words methods
should be parametrically polymorphic.

Algebra

Algebra is a set of requirements for modules, like to match some signature and to obey some laws. If a module satisfies all requirements of an algebra it supports that algebra. An algebra may require to support other algebras.

An algebra may also state other algebra methods which can be derived from new methods. If a module provides a method which could be derived, its behaviour must be equivalent to that of the derivation (or derivations).

Setoid
Ord
Semigroup
Monoid
Group
Semigroupoid
Category
Filterable
Functor
Bifunctor
Contravariant
Profunctor
Apply
Applicative
Alt
Plus
Alternative
Chain
ChainRec
Monad
Foldable
Extend
Comonad
Traversable

Setoid

Setoid<T> {
  equals: (T, T) => boolean
}

Module must match the Setoid signature for some type T, and obey following laws:

Reflexivity: S.equals(a, a) === true
Symmetry: S.equals(a, b) === S.equals(b, a)
Transitivity: if S.equals(a, b) and S.equals(b, c), then S.equals(a, c)

Ord

Ord<T> {
  lte: (T, T) => boolean
}

Module must match the Ord signature for some type T, support Setoid algebra for the same T, and obey following laws:

Totality: S.lte(a, b) or S.lte(b, a)
Antisymmetry: if S.lte(a, b) and S.lte(b, a), then S.equals(a, b)
Transitivity: if S.lte(a, b) and S.lte(b, c), then S.lte(a, c)

Semigroup

Semigroup<T> {
  concat: (T, T) => T
}

Module must match the Semigroup signature for some type T, and obey following laws:

Associativity: S.concat(S.concat(a, b), c) ≡ S.concat(a, S.concat(b, c))

Monoid

Monoid<T> {
  empty: () => T
}

Module must match the Monoid signature for some type T, support Semigroup algebra for the same T, and obey following laws:

Right identity: M.concat(a, M.empty()) ≡ a
Left identity: M.concat(M.empty(), a) ≡ a

Group

Group<T> {
  invert: (T) => T
}

Module must match the Group signature for some type T, support Monoid algebra for the same T, and obey following laws:

Right inverse: G.concat(a, G.invert(a)) ≡ G.empty()
Left inverse: G.concat(G.invert(a), a) ≡ G.empty()

Semigroupoid

Semigroupoid<T> {
  compose: <i, j, k>(T<i, j>, T<j, k>) => T<i, k>
}

Module must match the Semigroupoid signature for some type T, and obey following laws:

Associativity: S.compose(S.compose(a, b), c) ≡ S.compose(a, S.compose(b, c))

Filterable

Filterable<T> {
  filter: <a>(a => boolean, T<a>) => T<a>
}

Module must match the Filterable signature for some type T, and obey following laws:

Distributivity: F.filter(x => f(x) && g(x), a) ≡ F.filter(g, F.filter(f, a))
Identity: F.filter(x => true, a) ≡ a
Annihilation: F.filter(x => false, a) ≡ F.filter(x => false, b)

Functor

Functor<T> {
  map: <a, b>(a => b, T<a>) => T<b>
}

Module must match the Functor signature for some type T, and obey following laws:

Identity: F.map(x => x, a) ≡ a
Composition: F.map(x => f(g(x)), a) ≡ F.map(f, F.map(g, a))

Bifunctor

Bifunctor<T> {
  bimap: <a, b, c, d>(a => b, c => d, T<a, c>) => T<b, d>
}

Module must match the Bifunctor signature for some type T, support Functor algebra for all types U created by setting the first parameter of T to an arbitrary concrete type (for example type U<a> = T<number, a>), and obey following laws:

Identity: B.bimap(x => x, x => x, a) ≡ a
Composition: B.bimap(x => f(g(x)), x => h(i(x)), a) ≡ B.bimap(f, h, B.bimap(g, i, a))

Can be derived

Functor's map: A.map = (f, u) => A.bimap(x => x, f, u)

Contravariant

Contravariant<T> {
  contramap: <a, b>(a => b, T<b>) => T<a>
}

Module must match the Contravariant signature for some type T, and obey following laws:

Identity: F.contramap(x => x, a) ≡ a
Composition: F.contramap(x => f(g(x)), a) ≡ F.contramap(g, F.contramap(f, a))

Profunctor

Profunctor<T> {
  promap: <a, b, c, d>(a => b, c => d, T<b, c>) => T<a, d>
}

Module must match the Profunctor signature for some type T, support Functor algebra for all types U created by setting the first parameter of T to an arbitrary concrete type (for example type U<a> = T<number, a>), and obey following laws:

Identity: P.promap(x => x, x => x, a) ≡ a
Composition: P.promap(x => f(g(x)), x => h(i(x)), a) ≡ P.promap(g, h, P.promap(f, i, a))

Can be derived

Functor's map: A.map = (f, u) => A.promap(x => x, f, u)

Apply

Apply<T> {
  ap: <a, b>(T<a => b>, T<a>) => T<b>
}

Module must match the Apply signature for some type T, support Functor algebra for the same T, and obey following laws:

Composition: A.ap(A.ap(A.map(f => g => x => f(g(x)), a), u), v) ≡ A.ap(a, A.ap(u, v))

Applicative

Applicative<T> {
  of: <a>(a) => T<a>
}

Module must match the Applicative signature for some type T, support Apply algebra for the same T, and obey following laws:

Identity: A.ap(A.of(x => x), v) ≡ v
Homomorphism: A.ap(A.of(f), A.of(x)) ≡ A.of(f(x))
Interchange: A.ap(u, A.of(y)) ≡ A.ap(A.of(f => f(y)), u)

Can be derived

Functor's map: A.map = (f, u) => A.ap(A.of(f), u)

Alt

Alt<T> {
  alt: <a>(T<a>, T<a>) => T<a>
}

Module must match the Alt signature for some type T, support Functor algebra for the same T, and obey following laws:

Associativity: A.alt(A.alt(a, b), c) ≡ A.alt(a, A.alt(b, c))
Distributivity: A.map(f, A.alt(a, b)) ≡ A.alt(A.map(f, a), A.map(f, b))

Plus

Plus<T> {
  zero: <a>() => T<a>
}

Module must match the Plus signature for some type T, support Alt algebra for the same T, and obey following laws:

Right identity: P.alt(a, P.zero()) ≡ a
Left identity: P.alt(P.zero(), a) ≡ a
Annihilation: P.map(f, P.zero()) ≡ P.zero()

Alternative

Module must support Applicative and Plus algebras for a same T, and obey following laws:

Distributivity: A.ap(A.alt(a, b), c) ≡ A.alt(A.ap(a, c), A.ap(b, c))
Annihilation: A.ap(A.zero(), a) ≡ A.zero()

Chain

Chain<T> {
  chain: <a, b>(a => T<b>, T<a>) => T<b>
}

Module must match the Chain signature for some type T, support Apply algebra for the same T, and obey following laws:

Associativity: M.chain(g, M.chain(f, u)) ≡ M.chain(x => M.chain(g, f(x)), u)

Can be derived

Apply's ap: A.ap = (uf, ux) => A.chain(f => A.map(f, ux), uf)

ChainRec

ChainRec<T> {
  chainRec: <a, b>((a => Next<a>, b => Done<b>, a) => T<Next<a> | Done<b>>, a) => T<b>
}

Module must match the ChainRec signature for some type T, support Chain algebra for the same T, and obey following laws:

Equivalence: C.chainRec((next, done, v) => p(v) ? C.map(done, d(v)) : C.map(next, n(v)), i) ≡ (function step(v) { return p(v) ? d(v) : C.chain(step, n(v)) }(i))
Stack usage of C.chainRec(f, i) must be at most a constant multiple of the stack usage of f itself.

Monad

Module must support Applicative and Chain algebras for a same T, and obey following laws:

Left identity: M.chain(f, M.of(a)) ≡ f(a)
Right identity: M.chain(M.of, u) ≡ u

Can be derived

Functor's map: A.map = (f, u) => A.chain(x => A.of(f(x)), u)

Foldable

Foldable<T> {
  reduce: <a, b>((a, b) => a, a, T<b>) => a
}

Module must match the Foldable signature for some type T, and obey following laws:

F.reduce ≡ (f, x, u) => F.reduce((acc, y) => acc.concat([y]), [], u).reduce(f, x)

Extend

Extend<T> {
  extend: <a, b>(T<a> => b, T<a>) => T<b>
}

Module must match the Extend signature for some type T, support Functor algebra for the same T, and obey following laws:

Associativity: E.extend(f, E.extend(g, w)) ≡ E.extend(_w => f(E.extend(g, _w)), w)

Comonad

Comonad<T> {
  extract: <a>(T<a>) => a
}

Module must match the Comonad signature for some type T, support Extend algebra for the same T, and obey following laws:

Laws

Left identity: C.extend(C.extract, w) ≡ w
Right identity: C.extract(C.extend(f, w)) ≡ f(w)

Traversable

In the following signature Applicative<U> stands for a module that must support Applicative algebra for some type U that a => U<b> returns. For example, if the second argument of traverse() is a function that returns Array, then the first argument must be a module that supports Applicative for Array.

Traversable<T> {
  traverse: <U, a, b>(Applicative<U>, a => U<b>, T<a>) => U<T<b>>
}

Module must match the Traversable signature for some type T, support Functor and Foldable algebras for the same T, and obey following laws:

Naturality: f(T.traverse(A, x => x, u)) ≡ T.traverse(B, f, u) for any f such that B.map(g, f(a)) ≡ f(A.map(g, a))
Identity: T.traverse(F, F.of, u) ≡ F.of(u) for any Applicative F
Composition: T.traverse(Compose(A, B), x => x, u) ≡ A.map(v => T.traverse(B, x => x, v), T.traverse(A, x => x, u)) for Compose defined bellow and for any Applicatives A and B

function Compose(A, B) {
  return {

    of(x) {
      return A.of(B.of(x))
    },

    ap(a1, a2) {
      return A.ap(A.map(b1 => b2 => B.ap(b1, b2), a1), a2)
    },

    map(f, a) {
      return A.map(b => B.map(f, b), a)
    },

  }
}

Can be derived

Foldable's reduce:

F.reduce = (f, acc, u) => {
  const of = () => acc
  const map = (_, x) => x
  const ap = f
  return F.traverse({of, map, ap}, x => x, u)
}

Functor's map:

F.map = (f, u) => {
  const of = (x) => x
  const map = (f, a) => f(a)
  const ap = (f, a) => f(a)
  return F.traverse({of, map, ap}, f, u)
}

Files

spec.md

Latest commit

History

spec.md

File metadata and controls

Static Land Specification

Module

Module Signature

Equivalence

Parametricity

Algebra

Setoid

Ord

Semigroup

Monoid

Group

Semigroupoid

Category

Filterable

Functor

Bifunctor

Can be derived

Contravariant

Profunctor

Can be derived

Apply

Applicative

Can be derived

Alt

Plus

Alternative

Chain

Can be derived

ChainRec

Monad

Can be derived

Foldable

Extend

Comonad

Laws

Traversable

Can be derived