(aka "Algebraic JavaScript Specification")
This project specifies interoperability of common algebraic structures:
- Setoid
- Ord
- Semigroupoid
- Category
- Semigroup
- Monoid
- Group
- Functor
- Contravariant
- Apply
- Applicative
- Alt
- Plus
- Alternative
- Foldable
- Traversable
- Chain
- ChainRec
- Monad
- Extend
- Comonad
- Bifunctor
- Profunctor
An algebra is a set of values, a set of operators that it is closed under and some laws it must obey.
Each Fantasy Land algebra is a separate specification. An algebra may have dependencies on other algebras which must be implemented.
- "value" is any JavaScript value, including any which have the structures defined below.
- "equivalent" is an appropriate definition of equivalence for the given value.
The definition 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.
The type signature notation used in this document is described below:1
::
"is a member of".e :: t
can be read as: "the expressione
is a member of typet
".true :: Boolean
- "true
is a member of typeBoolean
".42 :: Integer, Number
- "42
is a member of typeInteger and Number
".
- New types can be created via type constructors.
- Type constructors can take zero or more type arguments.
Array
is a type constructor which takes one type argument.Array String
is the type of all arrays of strings. Each of the following has typeArray String
:[]
,['foo', 'bar', 'baz']
.Array (Array String)
is the type of all arrays of arrays of strings. Each of the following has typeArray (Array String)
:[]
,[ [], [] ]
,[ [], ['foo'], ['bar', 'baz'] ]
.
- Lowercase letters stand for type variables.
- Type variables can take any type unless they have been restricted by means of type constraints (see fat arrow below).
->
(arrow) Function type constructor.->
is an infix type constructor that takes two type arguments where left argument is the input type and the right argument is the output type.->
's input type can be a grouping of types to create the type of a function which accepts zero or more arguments. The syntax is:(<input-types>) -> <output-type>
, where<input-types>
comprises zero or more comma–space (,
)-separated type representations and parens may be omitted for unary functions.String -> Array String
is a type satisfied by functions which take aString
and return anArray String
.String -> Array String -> Array String
is a type satisfied by functions which take aString
and return a function which takes anArray String
and returns anArray String
.(String, Array String) -> Array String
is a type satisfied by functions which take aString
and anArray String
as arguments and return anArray String
.() -> Number
is a type satisfied by functions which do not take arguments and return aNumber
.
~>
(squiggly arrow) Method type constructor.- When a function is a property of an Object, it is called a method. All methods have an implicit parameter type - the type of which they are a property.
a ~> a -> a
is a type satisfied by methods on Objects of typea
which take a typea
as an argument and return a value of typea
.
=>
(fat arrow) Expresses constraints on type variables.- In
a ~> a -> a
(see squiggly arrow above),a
can be of any type.Semigroup a => a ~> a -> a
adds a constraint such that the typea
must now satisfy theSemigroup
typeclass. To satisfy a typeclass means to lawfully implement all functions/methods specified by that typeclass.
- In
For example:
traverse :: Applicative f, Traversable t => t a ~> (TypeRep f, a -> f b) -> f (t b)
'------' '--------------------------' '-' '-------------------' '-----'
' ' ' ' '
' ' - type constraints ' ' - argument types ' - return type
' '
'- method name ' - method target type
In order for a data type to be compatible with Fantasy Land, its values must
have certain properties. These properties are all prefixed by fantasy-land/
.
For example:
// MyType#fantasy-land/map :: MyType a ~> (a -> b) -> MyType b
MyType.prototype['fantasy-land/map'] = ...
Further in this document unprefixed names are used just to reduce noise.
For convenience you can use fantasy-land
package:
var fl = require('fantasy-land')
// ...
MyType.prototype[fl.map] = ...
// ...
var foo = bar[fl.map](x => x + 1)
Certain behaviours are defined from the perspective of a member of a type.
Other behaviours do not require a member. Thus certain algebras require a
type to provide a value-level representative (with certain properties). The
Identity type, for example, could provide Id
as its type representative:
Id :: TypeRep Identity
.
If a type provides a type representative, each member of the type must have
a constructor
property which is a reference to the type representative.
a.equals(a) === true
(reflexivity)a.equals(b) === b.equals(a)
(symmetry)- If
a.equals(b)
andb.equals(c)
, thena.equals(c)
(transitivity)
equals :: Setoid a => a ~> a -> Boolean
A value which has a Setoid must provide an equals
method. The
equals
method takes one argument:
a.equals(b)
-
b
must be a value of the same Setoid- If
b
is not the same Setoid, behaviour ofequals
is unspecified (returningfalse
is recommended).
- If
-
equals
must return a boolean (true
orfalse
).
A value that implements the Ord specification must also implement the Setoid specification.
a.lte(b)
orb.lte(a)
(totality)- If
a.lte(b)
andb.lte(a)
, thena.equals(b)
(antisymmetry) - If
a.lte(b)
andb.lte(c)
, thena.lte(c)
(transitivity)
lte :: Ord a => a ~> a -> Boolean
A value which has an Ord must provide a lte
method. The
lte
method takes one argument:
a.lte(b)
-
b
must be a value of the same Ord- If
b
is not the same Ord, behaviour oflte
is unspecified (returningfalse
is recommended).
- If
-
lte
must return a boolean (true
orfalse
).
a.compose(b).compose(c) === a.compose(b.compose(c))
(associativity)
compose :: Semigroupoid c => c i j ~> c j k -> c i k
A value which has a Semigroupoid must provide a compose
method. The
compose
method takes one argument:
a.compose(b)
-
b
must be a value of the same Semigroupoid- If
b
is not the same semigroupoid, behaviour ofcompose
is unspecified.
- If
-
compose
must return a value of the same Semigroupoid.
A value that implements the Category specification must also implement the Semigroupoid specification.
a.compose(C.id())
is equivalent toa
(right identity)C.id().compose(a)
is equivalent toa
(left identity)
id :: Category c => () -> c a a
A value which has a Category must provide an id
function on its
type representative:
C.id()
Given a value c
, one can access its type representative via the
constructor
property:
c.constructor.id()
id
must return a value of the same Category
a.concat(b).concat(c)
is equivalent toa.concat(b.concat(c))
(associativity)
concat :: Semigroup a => a ~> a -> a
A value which has a Semigroup must provide a concat
method. The
concat
method takes one argument:
s.concat(b)
-
b
must be a value of the same Semigroup- If
b
is not the same semigroup, behaviour ofconcat
is unspecified.
- If
-
concat
must return a value of the same Semigroup.
A value that implements the Monoid specification must also implement the Semigroup specification.
m.concat(M.empty())
is equivalent tom
(right identity)M.empty().concat(m)
is equivalent tom
(left identity)
empty :: Monoid m => () -> m
A value which has a Monoid must provide an empty
function on its
type representative:
M.empty()
Given a value m
, one can access its type representative via the
constructor
property:
m.constructor.empty()
empty
must return a value of the same Monoid
A value that implements the Group specification must also implement the Monoid specification.
g.concat(g.invert())
is equivalent tog.constructor.empty()
(right inverse)g.invert().concat(g)
is equivalent tog.constructor.empty()
(left inverse)
invert :: Group g => g ~> () -> g
A value which has a Group must provide an invert
method. The
invert
method takes no arguments:
g.invert()
invert
must return a value of the same Group.
u.map(a => a)
is equivalent tou
(identity)u.map(x => f(g(x)))
is equivalent tou.map(g).map(f)
(composition)
map :: Functor f => f a ~> (a -> b) -> f b
A value which has a Functor must provide a map
method. The map
method takes one argument:
u.map(f)
-
f
must be a function,- If
f
is not a function, the behaviour ofmap
is unspecified. f
can return any value.- No parts of
f
's return value should be checked.
- If
-
map
must return a value of the same Functor
u.contramap(a => a)
is equivalent tou
(identity)u.contramap(x => f(g(x)))
is equivalent tou.contramap(f).contramap(g)
(composition)
contramap :: Contravariant f => f a ~> (b -> a) -> f b
A value which has a Contravariant must provide a contramap
method. The
contramap
method takes one argument:
u.contramap(f)
-
f
must be a function,- If
f
is not a function, the behaviour ofcontramap
is unspecified. f
can return any value.- No parts of
f
's return value should be checked.
- If
-
contramap
must return a value of the same Contravariant
A value that implements the Apply specification must also implement the Functor specification.
v.ap(u.ap(a.map(f => g => x => f(g(x)))))
is equivalent tov.ap(u).ap(a)
(composition)
ap :: Apply f => f a ~> f (a -> b) -> f b
A value which has an Apply must provide an ap
method. The ap
method takes one argument:
a.ap(b)
-
b
must be an Apply of a function- If
b
does not represent a function, the behaviour ofap
is unspecified. b
must be same Apply asa
.
- If
-
a
must be an Apply of any value -
ap
must apply the function in Applyb
to the value in Applya
- No parts of return value of that function should be checked.
-
The
Apply
returned byap
must be the same asa
andb
A value that implements the Applicative specification must also implement the Apply specification.
v.ap(A.of(x => x))
is equivalent tov
(identity)A.of(x).ap(A.of(f))
is equivalent toA.of(f(x))
(homomorphism)A.of(y).ap(u)
is equivalent tou.ap(A.of(f => f(y)))
(interchange)
of :: Applicative f => a -> f a
A value which has an Applicative must provide an of
function on its
type representative. The of
function takes
one argument:
F.of(a)
Given a value f
, one can access its type representative via the
constructor
property:
f.constructor.of(a)
-
of
must provide a value of the same Applicative- No parts of
a
should be checked
- No parts of
A value that implements the Alt specification must also implement the Functor specification.
a.alt(b).alt(c)
is equivalent toa.alt(b.alt(c))
(associativity)a.alt(b).map(f)
is equivalent toa.map(f).alt(b.map(f))
(distributivity)
alt :: Alt f => f a ~> f a -> f a
A value which has a Alt must provide a alt
method. The
alt
method takes one argument:
a.alt(b)
-
b
must be a value of the same Alt- If
b
is not the same Alt, behaviour ofalt
is unspecified. a
andb
can contain any value of same type.- No parts of
a
's andb
's containing value should be checked.
- If
-
alt
must return a value of the same Alt.
A value that implements the Plus specification must also implement the Alt specification.
x.alt(A.zero())
is equivalent tox
(right identity)A.zero().alt(x)
is equivalent tox
(left identity)A.zero().map(f)
is equivalent toA.zero()
(annihilation)
zero :: Plus f => () -> f a
A value which has a Plus must provide an zero
function on its
type representative:
A.zero()
Given a value x
, one can access its type representative via the
constructor
property:
x.constructor.zero()
zero
must return a value of the same Plus
A value that implements the Alternative specification must also implement the Applicative and Plus specifications.
x.ap(f.alt(g))
is equivalent tox.ap(f).alt(x.ap(g))
(distributivity)x.ap(A.zero())
is equivalent toA.zero()
(annihilation)
u.reduce
is equivalent tou.reduce((acc, x) => acc.concat([x]), []).reduce
reduce :: Foldable f => f a ~> ((b, a) -> b, b) -> b
A value which has a Foldable must provide a reduce
method. The reduce
method takes two arguments:
u.reduce(f, x)
-
f
must be a binary function- if
f
is not a function, the behaviour ofreduce
is unspecified. - The first argument to
f
must be the same type asx
. f
must return a value of the same type asx
.- No parts of
f
's return value should be checked.
- if
-
x
is the initial accumulator value for the reduction- No parts of
x
should be checked.
- No parts of
A value that implements the Traversable specification must also implement the Functor and Foldable specifications.
-
t(u.traverse(F, x => x))
is equivalent tou.traverse(G, t)
for anyt
such thatt(a).map(f)
is equivalent tot(a.map(f))
(naturality) -
u.traverse(F, F.of)
is equivalent toF.of(u)
for any ApplicativeF
(identity) -
u.traverse(Compose, x => new Compose(x))
is equivalent tonew Compose(u.traverse(F, x => x).map(x => x.traverse(G, x => x)))
forCompose
defined below and any ApplicativesF
andG
(composition)
var Compose = function(c) {
this.c = c;
};
Compose.of = function(x) {
return new Compose(F.of(G.of(x)));
};
Compose.prototype.ap = function(f) {
return new Compose(this.c.ap(f.c.map(u => y => y.ap(u))));
};
Compose.prototype.map = function(f) {
return new Compose(this.c.map(y => y.map(f)));
};
traverse :: Applicative f, Traversable t => t a ~> (TypeRep f, a -> f b) -> f (t b)
A value which has a Traversable must provide a traverse
method. The traverse
method takes two arguments:
u.traverse(A, f)
-
A
must be the type representative of an Applicative. -
f
must be a function which returns a value- If
f
is not a function, the behaviour oftraverse
is unspecified. f
must return a value of the type represented byA
.
- If
-
traverse
must return a value of the type represented byA
.
A value that implements the Chain specification must also implement the Apply specification.
m.chain(f).chain(g)
is equivalent tom.chain(x => f(x).chain(g))
(associativity)
chain :: Chain m => m a ~> (a -> m b) -> m b
A value which has a Chain must provide a chain
method. The chain
method takes one argument:
m.chain(f)
-
f
must be a function which returns a value- If
f
is not a function, the behaviour ofchain
is unspecified. f
must return a value of the same Chain
- If
-
chain
must return a value of the same Chain
A value that implements the ChainRec specification must also implement the Chain specification.
M.chainRec((next, done, v) => p(v) ? d(v).map(done) : n(v).map(next), i)
is equivalent to(function step(v) { return p(v) ? d(v) : n(v).chain(step); }(i))
(equivalence)- Stack usage of
M.chainRec(f, i)
must be at most a constant multiple of the stack usage off
itself.
chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b
A Type which has a ChainRec must provide a chainRec
function on its
type representative. The chainRec
function
takes two arguments:
M.chainRec(f, i)
Given a value m
, one can access its type representative via the
constructor
property:
m.constructor.chainRec(f, i)
f
must be a function which returns a value- If
f
is not a function, the behaviour ofchainRec
is unspecified. f
takes three argumentsnext
,done
,value
next
is a function which takes one argument of same type asi
and can return any valuedone
is a function which takes one argument and returns the same type as the return value ofnext
value
is some value of the same type asi
f
must return a value of the same ChainRec which contains a value returned from eitherdone
ornext
- If
chainRec
must return a value of the same ChainRec which contains a value of same type as argument ofdone
A value that implements the Monad specification must also implement the Applicative and Chain specifications.
M.of(a).chain(f)
is equivalent tof(a)
(left identity)m.chain(M.of)
is equivalent tom
(right identity)
A value that implements the Extend specification must also implement the Functor specification.
w.extend(g).extend(f)
is equivalent tow.extend(_w => f(_w.extend(g)))
extend :: Extend w => w a ~> (w a -> b) -> w b
An Extend must provide an extend
method. The extend
method takes one argument:
w.extend(f)
-
f
must be a function which returns a value- If
f
is not a function, the behaviour ofextend
is unspecified. f
must return a value of typev
, for some variablev
contained inw
.- No parts of
f
's return value should be checked.
- If
-
extend
must return a value of the same Extend.
A value that implements the Comonad specification must also implement the Extend specification.
w.extend(_w => _w.extract())
is equivalent tow
(left identity)w.extend(f).extract()
is equivalent tof(w)
(right identity)
extract :: Comonad w => w a ~> () -> a
A value which has a Comonad must provide an extract
method on itself.
The extract
method takes no arguments:
w.extract()
extract
must return a value of typev
, for some variablev
contained inw
.v
must have the same type thatf
returns inextend
.
A value that implements the Bifunctor specification must also implement the Functor specification.
p.bimap(a => a, b => b)
is equivalent top
(identity)p.bimap(a => f(g(a)), b => h(i(b))
is equivalent top.bimap(g, i).bimap(f, h)
(composition)
bimap :: Bifunctor f => f a c ~> (a -> b, c -> d) -> f b d
A value which has a Bifunctor must provide a bimap
method. The bimap
method takes two arguments:
c.bimap(f, g)
-
f
must be a function which returns a value- If
f
is not a function, the behaviour ofbimap
is unspecified. f
can return any value.- No parts of
f
's return value should be checked.
- If
-
g
must be a function which returns a value- If
g
is not a function, the behaviour ofbimap
is unspecified. g
can return any value.- No parts of
g
's return value should be checked.
- If
-
bimap
must return a value of the same Bifunctor.
A value that implements the Profunctor specification must also implement the Functor specification.
p.promap(a => a, b => b)
is equivalent top
(identity)p.promap(a => f(g(a)), b => h(i(b)))
is equivalent top.promap(f, i).promap(g, h)
(composition)
promap :: Profunctor p => p b c ~> (a -> b, c -> d) -> p a d
A value which has a Profunctor must provide a promap
method.
The profunctor
method takes two arguments:
c.promap(f, g)
-
f
must be a function which returns a value- If
f
is not a function, the behaviour ofpromap
is unspecified. f
can return any value.- No parts of
f
's return value should be checked.
- If
-
g
must be a function which returns a value- If
g
is not a function, the behaviour ofpromap
is unspecified. g
can return any value.- No parts of
g
's return value should be checked.
- If
-
promap
must return a value of the same Profunctor
When creating data types which satisfy multiple algebras, authors may choose to implement certain methods then derive the remaining methods. Derivations:
-
equals
may be derived fromlte
:function(other) { return this.lte(other) && other.lte(this); }
-
map
may be derived fromap
andof
:function(f) { return this.ap(this.of(f)); }
-
map
may be derived fromchain
andof
:function(f) { return this.chain(a => this.of(f(a))); }
-
map
may be derived frombimap
:function(f) { return this.bimap(a => a, f); }
-
map
may be derived frompromap
:function(f) { return this.promap(a => a, f); }
-
function(m) { return m.chain(f => this.map(f)); }
-
reduce
may be derived as follows:function(f, acc) { function Const(value) { this.value = value; } Const.of = function(_) { return new Const(acc); }; Const.prototype.map = function(_) { return this; }; Const.prototype.ap = function(b) { return new Const(f(b.value, this.value)); }; return this.traverse(x => new Const(x), Const.of).value; }
-
map
may be derived as follows:function(f) { function Id(value) { this.value = value; }; Id.of = function(x) { return new Id(x); }; Id.prototype.map = function(f) { return new Id(f(this.value)); }; Id.prototype.ap = function(b) { return new Id(this.value(b.value)); }; return this.traverse(x => Id.of(f(x)), Id.of).value; }
If a data type provides a method which could be derived, its behaviour must be equivalent to that of the derivation (or derivations).
- If there's more than a single way to implement the methods and laws, the implementation should choose one and provide wrappers for other uses.
- It's discouraged to overload the specified methods. It can easily result in broken and buggy behaviour.
- It is recommended to throw an exception on unspecified behaviour.
- An
Id
container which implements many of the methods is provided ininternal/id.js
.
There also exists Static Land Specification with the exactly same ideas as Fantasy Land but based on static methods instead of instance methods.