fantasyland/fantasy-land: Specification for interoperability of common algebraic...
source link: https://www.tuicool.com/articles/hit/faA3a2z
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Fantasy Land Specification
(aka "Algebraic JavaScript Specification")
This project specifies interoperability of common algebraic structures:
General
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.
Terminology
- "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.
Type signature notation
The type signature notation used in this document is described below:
-
::
"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
- See the Types section in Sanctuary's docs for more info.
Prefixed method names
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)
Type representatives
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.
Algebras
Setoid
-
a.equals(a) === true
(reflexivity) -
a.equals(b) === b.equals(a)
(symmetry) - If
a.equals(b)
andb.equals(c)
, thena.equals(c)
(transitivity)
equals
method
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
).
Ord
A value that implements the Ord specification must also implement thespecification.
-
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
method
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
).
Semigroupoid
-
a.compose(b).compose(c) === a.compose(b.compose(c))
(associativity)
compose
method
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.
Category
A value that implements the Category specification must also implement thespecification.
-
a.compose(C.id())
is equivalent toa
(right identity) -
C.id().compose(a)
is equivalent toa
(left identity)
id
method
id :: Category c => () -> c a a
A value which has a Category must provide an id
function on its:
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
Semigroup
-
a.concat(b).concat(c)
is equivalent toa.concat(b.concat(c))
(associativity)
concat
method
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.
Monoid
A value that implements the Monoid specification must also implement thespecification.
-
m.concat(M.empty())
is equivalent tom
(right identity) -
M.empty().concat(m)
is equivalent tom
(left identity)
empty
method
empty :: Monoid m => () -> m
A value which has a Monoid must provide an empty
function on its:
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
Group
A value that implements the Group specification must also implement thespecification.
-
g.concat(g.invert())
is equivalent tog.constructor.empty()
(right inverse) -
g.invert().concat(g)
is equivalent tog.constructor.empty()
(left inverse)
invert
method
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.
Filterable
-
v.filter(x => p(x) && q(x))
is equivalent tov.filter(p).filter(q)
(distributivity) -
v.filter(x => true)
is equivalent tov
(identity) -
v.filter(x => false)
is equivalent tow.filter(x => false)
ifv
andw
are values of the same Filterable (annihilation)
filter
method
filter :: 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.- If
p
is not a function, the behaviour offilter
is unspecified. -
p
must return eithertrue
orfalse
. If it returns any other value, the behaviour offilter
is unspecified.
- If
-
filter
must return a value of the same Filterable.
Functor
-
u.map(a => a)
is equivalent tou
(identity) -
u.map(x => f(g(x)))
is equivalent tou.map(g).map(f)
(composition)
map
method
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
Contravariant
-
u.contramap(a => a)
is equivalent tou
(identity) -
u.contramap(x => f(g(x)))
is equivalent tou.contramap(f).contramap(g)
(composition)
contramap
method
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
Apply
A value that implements the Apply specification must also implement thespecification.
-
v.ap(u.ap(a.map(f => g => x => f(g(x)))))
is equivalent tov.ap(u).ap(a)
(composition)
ap
method
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
Applicative
A value that implements the Applicative specification must also implement thespecification.
-
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
method
of :: Applicative f => a -> f a
A value which has an Applicative must provide an of
function on its. 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
Alt
A value that implements the Alt specification must also implement thespecification.
-
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
method
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.
Plus
A value that implements the Plus specification must also implement thespecification.
-
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
method
zero :: Plus f => () -> f a
A value which has a Plus must provide an zero
function on its:
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
Alternative
A value that implements the Alternative specification must also implement theandspecifications.
-
x.ap(f.alt(g))
is equivalent tox.ap(f).alt(x.ap(g))
(distributivity) -
x.ap(A.zero())
is equivalent toA.zero()
(annihilation)
Foldable
-
u.reduce
is equivalent tou.reduce((acc, x) => acc.concat([x]), []).reduce
reduce
method
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
Traversable
A value that implements the Traversable specification must also implement theandspecifications.
-
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
method
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 theof 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
.
Chain
A value that implements the Chain specification must also implement thespecification.
-
m.chain(f).chain(g)
is equivalent tom.chain(x => f(x).chain(g))
(associativity)
chain
method
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
ChainRec
A value that implements the ChainRec specification must also implement thespecification.
-
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
method
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. 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 value -
done
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
Monad
A value that implements the Monad specification must also implement theandspecifications.
-
M.of(a).chain(f)
is equivalent tof(a)
(left identity) -
m.chain(M.of)
is equivalent tom
(right identity)
Extend
A value that implements the Extend specification must also implement thespecification.
-
w.extend(g).extend(f)
is equivalent tow.extend(_w => f(_w.extend(g)))
extend
method
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.
Comonad
A value that implements the Comonad specification must also implement thespecification.
-
w.extend(_w => _w.extract())
is equivalent tow
(left identity) -
w.extend(f).extract()
is equivalent tof(w)
(right identity)
extract
method
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
.
-
Bifunctor
A value that implements the Bifunctor specification must also implement thespecification.
-
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
method
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.
Profunctor
A value that implements the Profunctor specification must also implement thespecification.
-
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
method
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
Derivations
When creating data types which satisfy multiple algebras, authors may choose to implement certain methods then derive the remaining methods. Derivations:
-
may be derived from:
function(other) { return this.lte(other) && other.lte(this); }
-
may be derived fromand:
function(f) { return this.ap(this.of(f)); }
-
may be derived fromand:
function(f) { return this.chain(a => this.of(f(a))); }
-
may be derived from:
function(f) { return this.bimap(a => a, f); }
-
may be derived from:
function(f) { return this.promap(a => a, f); }
-
may be derived from:
function(m) { return m.chain(f => this.map(f)); }
-
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; }
-
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; }
-
may be derived from,, and:
function(pred) { var F = this.constructor; return this.chain(x => pred(x) ? F.of(x) : F.zero()); }
-
may be derived from,,, and:
function(pred) { var F = this.constructor; return this.reduce((f, x) => pred(x) ? f.concat(F.of(x)) : f, F.zero()); }
If a data type provides a method which could be derived, its behaviour must be equivalent to that of the derivation (or derivations).
Notes
- 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
Identity
container which implements many of the methods is provided by sanctuary-identity .
Alternatives
There also exists Static Land Specification with exactly the same ideas as Fantasy Land but based on static methods instead of instance methods.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK