Functional Programming from the perspective of a JavaScript Programmer.

Real World Specification.md

Real World Specification

(aka "Algebraic JavaScript Specification")

This project specifies the behavior of a number of methods that may optionally be added to any object. The motivation behind this is to encourage greater code reuse. You can create functions that just rely on objects having implementations of the methods below, and in doing so you can make them work with a wide variety of different, but related data structures.

Definitions

For the purposes of this, spec, an "entity" is an object that has an [[equivalent]] operation (see bellow) and may implement some or all of the other methods.

A "value" is any JavaScript value, this includes entities.

[[equivalent]]

[[equivalent]] is an imaginary function that takes two arguments and returns true or false. It should return true iff the two objects could be swapped and no program would be able to tell the difference other than by checking the exact object references.

Examples:

• Two numbers are equivalent if they are equal
• Two strings are equivalent if they are equal
• Two arrays are equivalent if they contain equivalent items in the same order
• Two functions (that have no side effects) are equivalent if they return equivalent outputs for equivalent inputs.

Methods

A.concat(B)

If an entity (call it A) implements a method concat then when it is passed one argument that is of the same class as A it must:

1. return a value with the same type as A (the object on which the method was called).
2. It must be associative. That is to say a.concat(b).concat(c) must be equivalent to a.concat(b.concat(c)) ( associativity )

( an entity that implements concat is also known as a 'semigroup' in functional programming )

A.constructor.empty()

Any entity that implements empty must also implement concat. A.constructor.empty() must return an entity of the same class as A which obeys the following two rules.

1. A is equivalent to A.concat(A.constructor.empty()) ( right identity )
2. A is equivalent to A.constructor.empty().concat(A) ( left identity )

( an entity that implements empty is also known as a 'monoid' in functional programming )

A.map(fn)

If an entity (call it A) implements a method map then when it is passed one argument that is a function, map must return an entity of the same class as A.

map must also obey the following two rules:

1. A.map(function (a) { return a; }) is equivalent to A ( identity )
2. A.map(function (x) { return f(g(x)); }) is equivalent to A.map(g).map(f) ( composition )

A practical example of how map might be implemented is the array, which calls map for each element in the array and returns a new array that is an array of the results of the function, e.g.:

var arr = [1, 2, 3, 4];
function square(a) {
  return a * a;
}
var res = arr.map(square);

res would then be [1, 4, 9, 16]

( an entity that implements map is also known as a 'functor' in functional programming )

A.chain(fn)

If an entity (call it A) implements a method chain then when it is passed one argument that is a function and that function returns an entity of the same class as A, chain must return an entity of the same class as A.

It must also obey the rule:

1. A.chain(f).chain(g) is equivalent to A.chain(function (x) { return f(x).chain(g); }) ( associativity )

A.constructor.of(B)

Any entity that implements of must also implement chain. A.constructor.of(B) must return an entity of the same class as A which obeys the following three rules.

1. If f is a function that returns an entity of class A, then A.of(b).chain(f) is equivalent to f(b) ( left identity )
2. A.chain(A.constructor.of) is equivalent to A ( right identity )
3. Nothing about the contents of A may be checked, it is to be treated as an opaque value

( an entity that implements of is also known as a 'monad' in functional programming )

A monad must actually implement both of and chain. of is quite useful in the absence of chain (see the Applicative type in functional programming, where it's called pure), so they're pretty much separate concepts.

Same goes for zero and concat for Monoid: they're separate, and zero can be useful in the absence of concat. See this table on Wikipedia for a birds-eye overview of a number of algebraic structures and their properties. The column you want to look at for zero is Identity.

That table takes for granted that concat exists; that Wikipedia figure is a taxonomy of named sets w/ binary operations. In fact zero has no meaning without concat, and the same set may have multiple interesting zero values for different operations.

Indeed, the reason I added the statement that of requires chain and that zero requires concat was that without that they don't have meaningful definitions. In fact without that both could just return any instance of the given class.

At least as far as of goes, of is definitely useful in the absence of chain (after all, Applicative is defined in terms of pure and ap, where pure is our of and ap is not the same thing as chain). Whether or not of makes sense without ap is another issue.

The point about zero makes sense. Thanks for correcting me!

A.map(function (x) { return f(g(x)); }) is equivalent to u.map(g).map(f) ( composition )

should read

A.map(function (x) { return f(g(x)); }) is equivalent to A.map(g).map(f) ( composition )

@Twisol the exact same principle applies, of is defined in terms of chain. There may be functions that use of but not chain, this doesn't mean that of actually means anything without chain.