(aka "Algebraic JavaScript Specification")
This project specifies interoperability of common algebraic structures:
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.
The type signature notation used in this document is described below:^{1}
::
"is a member of".
e :: t
can be read as: "the expression e
is a member of type t
".true :: Boolean
- "true
is a member of type Boolean
".42 :: Integer, Number
- "42
is a member of type Integer and Number
".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 type Array String
: []
, ['foo', 'bar', 'baz']
.Array (Array String)
is the type of all arrays of arrays of strings.
Each of the following has type Array (Array String)
: []
, [ [], [] ]
, [ [], ['foo'], ['bar', 'baz'] ]
.->
(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 a
String
and return an Array String
.String -> Array String -> Array String
is a type satisfied by functions
which take a String
and return a function which takes an Array String
and returns an Array String
.(String, Array String) -> Array String
is a type satisfied by functions
which take a String
and an Array String
as arguments and return an
Array String
.() -> Number
is a type satisfied by functions
which do not take arguments and return a Number
.~>
(squiggly arrow) Method type constructor.
a ~> a -> a
is a type satisfied by methods on Objects of type a
which
take a type a
as an argument and return a value of type a
.=>
(fat arrow) Expresses constraints on type variables.
a ~> a -> a
(see squiggly arrow above), a
can be of any type.
Semigroup a => a ~> a -> a
adds a constraint such that the type a
must now satisfy the Semigroup
typeclass. To satisfy a typeclass means
to lawfully implement all functions/methods specified by that typeclass.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 bMyTypeprototype'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 = // ... MyTypeprototypeflmap = ... // ... var foo = barflmap 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)a.equals(b)
and b.equals(c)
, then a.equals(c)
(transitivity)equals
methodequals :: 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
b
is not the same Setoid, behaviour of equals
is
unspecified (returning false
is recommended).equals
must return a boolean (true
or false
).
A value that implements the Ord specification must also implement the Setoid specification.
a.lte(b)
or b.lte(a)
(totality)a.lte(b)
and b.lte(a)
, then a.equals(b)
(antisymmetry)a.lte(b)
and b.lte(c)
, then a.lte(c)
(transitivity)lte
methodlte :: 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
b
is not the same Ord, behaviour of lte
is
unspecified (returning false
is recommended).lte
must return a boolean (true
or false
).
a.compose(b).compose(c) === a.compose(b.compose(c))
(associativity)compose
methodcompose :: 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
b
is not the same semigroupoid, behaviour of compose
is
unspecified.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 to a
(right identity)C.id().compose(a)
is equivalent to a
(left identity)id
methodid :: 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 Categorya.concat(b).concat(c)
is equivalent to a.concat(b.concat(c))
(associativity)concat
methodconcat :: 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
b
is not the same semigroup, behaviour of concat
is
unspecified.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 to m
(right identity)M.empty().concat(m)
is equivalent to m
(left identity)empty
methodempty :: 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 MonoidA value that implements the Group specification must also implement the Monoid specification.
g.concat(g.invert())
is equivalent to g.constructor.empty()
(right inverse)g.invert().concat(g)
is equivalent to g.constructor.empty()
(left inverse)invert
methodinvert :: 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.v.filter(x => p(x) && q(x))
is equivalent to v.filter(p).filter(q)
(distributivity)v.filter(x => true)
is equivalent to v
(identity)v.filter(x => false)
is equivalent to w.filter(x => false)
if v
and w
are values of the same Filterable (annihilation)filter
methodfilter :: Filterable f => f a ~> (a -> Boolean) -> f a
A value which has a Filterable must provide a filter
method. The filter
method takes one argument:
v.filter(p)
p
must be a function.
p
is not a function, the behaviour of filter
is unspecified.p
must return either true
or false
. If it returns any other value,
the behaviour of filter
is unspecified.filter
must return a value of the same Filterable.
u.map(a => a)
is equivalent to u
(identity)u.map(x => f(g(x)))
is equivalent to u.map(g).map(f)
(composition)map
methodmap :: 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,
f
is not a function, the behaviour of map
is
unspecified.f
can return any value.f
's return value should be checked.map
must return a value of the same Functor
u.contramap(a => a)
is equivalent to u
(identity)u.contramap(x => f(g(x)))
is equivalent to u.contramap(f).contramap(g)
(composition)contramap
methodcontramap :: 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,
f
is not a function, the behaviour of contramap
is
unspecified.f
can return any value.f
's return value should be checked.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 to v.ap(u).ap(a)
(composition)ap
methodap :: 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
b
does not represent a function, the behaviour of ap
is
unspecified.b
must be same Apply as a
.a
must be an Apply of any value
ap
must apply the function in Apply b
to the value in
Apply a
The Apply
returned by ap
must be the same as a
and b
A value that implements the Applicative specification must also implement the Apply specification.
v.ap(A.of(x => x))
is equivalent to v
(identity)A.of(x).ap(A.of(f))
is equivalent to A.of(f(x))
(homomorphism)A.of(y).ap(u)
is equivalent to u.ap(A.of(f => f(y)))
(interchange)of
methodof :: 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
a
should be checkedA value that implements the Alt specification must also implement the Functor specification.
a.alt(b).alt(c)
is equivalent to a.alt(b.alt(c))
(associativity)a.alt(b).map(f)
is equivalent to a.map(f).alt(b.map(f))
(distributivity)alt
methodalt :: 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
b
is not the same Alt, behaviour of alt
is
unspecified.a
and b
can contain any value of same type.a
's and b
's containing value should be checked.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 to x
(right identity)A.zero().alt(x)
is equivalent to x
(left identity)A.zero().map(f)
is equivalent to A.zero()
(annihilation)zero
methodzero :: 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 PlusA value that implements the Alternative specification must also implement the Applicative and Plus specifications.
x.ap(f.alt(g))
is equivalent to x.ap(f).alt(x.ap(g))
(distributivity)x.ap(A.zero())
is equivalent to A.zero()
(annihilation)u.reduce
is equivalent to u.reduce((acc, x) => acc.concat([x]), []).reduce
reduce
methodreduce :: 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
f
is not a function, the behaviour of reduce
is unspecified.f
must be the same type as x
.f
must return a value of the same type as x
.f
's return value should be checked.x
is the initial accumulator value for the reduction
x
should be checked.A value that implements the Traversable specification must also implement the Functor and Foldable specifications.
t(u.traverse(F, x => x))
is equivalent to u.traverse(G, t)
for any
t
such that t(a).map(f)
is equivalent to t(a.map(f))
(naturality)
u.traverse(F, F.of)
is equivalent to F.of(u)
for any Applicative F
(identity)
u.traverse(Compose, x => new Compose(x))
is equivalent to
new Compose(u.traverse(F, x => x).map(x => x.traverse(G, x => x)))
for
Compose
defined below and any Applicatives F
and G
(composition)
var { thisc = c;}; Compose { return F;}; Composeprototype { return thisc;}; Composeprototype { return thisc;};
traverse
methodtraverse :: 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
f
is not a function, the behaviour of traverse
is
unspecified.f
must return a value of the type represented by A
.traverse
must return a value of the type represented by A
.
A value that implements the Chain specification must also implement the Apply specification.
m.chain(f).chain(g)
is equivalent to m.chain(x => f(x).chain(g))
(associativity)chain
methodchain :: 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
f
is not a function, the behaviour of chain
is
unspecified.f
must return a value of the same Chainchain
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)M.chainRec(f, i)
must be at most a constant multiple of the stack usage of f
itself.chainRec
methodchainRec :: 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
f
is not a function, the behaviour of chainRec
is unspecified.f
takes three arguments next
, done
, value
next
is a function which takes one argument of same type as i
and can return any valuedone
is a function which takes one argument and returns the same type as the return value of next
value
is some value of the same type as i
f
must return a value of the same ChainRec which contains a value returned from either done
or next
chainRec
must return a value of the same ChainRec which contains a value of same type as argument of done
A value that implements the Monad specification must also implement the Applicative and Chain specifications.
M.of(a).chain(f)
is equivalent to f(a)
(left identity)m.chain(M.of)
is equivalent to m
(right identity)A value that implements the Extend specification must also implement the Functor specification.
w.extend(g).extend(f)
is equivalent to w.extend(_w => f(_w.extend(g)))
extend
methodextend :: 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
f
is not a function, the behaviour of extend
is
unspecified.f
must return a value of type v
, for some variable v
contained in w
.f
's return value should be checked.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 to w
(left identity)w.extend(f).extract()
is equivalent to f(w)
(right identity)extract
methodextract :: 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 type v
, for some variable v
contained in w
.
v
must have the same type that f
returns in extend
.A value that implements the Bifunctor specification must also implement the Functor specification.
p.bimap(a => a, b => b)
is equivalent to p
(identity)p.bimap(a => f(g(a)), b => h(i(b))
is equivalent to p.bimap(g, i).bimap(f, h)
(composition)bimap
methodbimap :: 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
f
is not a function, the behaviour of bimap
is unspecified.f
can return any value.f
's return value should be checked.g
must be a function which returns a value
g
is not a function, the behaviour of bimap
is unspecified.g
can return any value.g
's return value should be checked.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 to p
(identity)p.promap(a => f(g(a)), b => h(i(b)))
is equivalent to p.promap(f, i).promap(g, h)
(composition)promap
methodpromap :: 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
f
is not a function, the behaviour of promap
is unspecified.f
can return any value.f
's return value should be checked.g
must be a function which returns a value
g
is not a function, the behaviour of promap
is unspecified.g
can return any value.g
's return value should be checked.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 from lte
:
{ return this && other; }
map
may be derived from ap
and of
:
{ return this; }
map
may be derived from chain
and of
:
{ return this; }
map
may be derived from bimap
:
{ return this; }
map
may be derived from promap
:
{ return this; }
{ return m; }
reduce
may be derived as follows:
{ { thisvalue = value; } Const { return acc; }; Constprototype { return this; }; Constprototype { return ; }; return thisvalue;}
map
may be derived as follows:
{ { thisvalue = value; } Id { return x; }; Idprototype { return ; }; Idprototype { return thisvaluebvalue; }; return thisvalue;}
filter
may be derived from of
, chain
, and zero
:
{ var F = thisconstructor; return this;}
filter
may be derived from concat
, of
, zero
, and
reduce
:
{ var F = thisconstructor; return this;}
If a data type provides a method which could be derived, its behaviour must be equivalent to that of the derivation (or derivations).
Id
container which implements many of the methods is provided in
internal/id.js
.There also exists Static Land Specification with exactly the same ideas as Fantasy Land but based on static methods instead of instance methods.