Fantasy Land Specification

(aka "Algebraic JavaScript Specification")

This project specifies interoperability of common algebraic structures:

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

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

1. "value" is any JavaScript value, including any which have the structures defined below.
2. "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 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 the Integer and Number types".
• 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 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'] ].
• 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 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.
  • 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 type a which take a type a as an argument and return a value of type a.
• => (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 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:

fantasy-land/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

1. See the Types section in Sanctuary's docs for more info. ↩

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

1. a['fantasy-land/equals'](a) === true (reflexivity)
2. a['fantasy-land/equals'](b) === b['fantasy-land/equals'](a) (symmetry)
3. If a['fantasy-land/equals'](b) and b['fantasy-land/equals'](c), then a['fantasy-land/equals'](c) (transitivity)

fantasy-land/equals method

fantasy-land/equals :: Setoid a => a ~> a -> Boolean

A value which has a Setoid must provide a fantasy-land/equals method. The fantasy-land/equals method takes one argument:

a['fantasy-land/equals'](b)

1. b must be a value of the same Setoid

   1. If b is not the same Setoid, behaviour of fantasy-land/equals is unspecified (returning false is recommended).

2. fantasy-land/equals must return a boolean (true or false).

Ord

A value that implements the Ord specification must also implement the Setoid specification.

1. a['fantasy-land/lte'](b) or b['fantasy-land/lte'](a) (totality)
2. If a['fantasy-land/lte'](b) and b['fantasy-land/lte'](a), then a['fantasy-land/equals'](b) (antisymmetry)
3. If a['fantasy-land/lte'](b) and b['fantasy-land/lte'](c), then a['fantasy-land/lte'](c) (transitivity)

fantasy-land/lte method

fantasy-land/lte :: Ord a => a ~> a -> Boolean

A value which has an Ord must provide a fantasy-land/lte method. The fantasy-land/lte method takes one argument:

 a['fantasy-land/lte'](b)

1. b must be a value of the same Ord

   1. If b is not the same Ord, behaviour of fantasy-land/lte is unspecified (returning false is recommended).

2. fantasy-land/lte must return a boolean (true or false).

Semigroupoid

1. a['fantasy-land/compose'](b)['fantasy-land/compose'](c) === a['fantasy-land/compose'](b['fantasy-land/compose'](c)) (associativity)

fantasy-land/compose method

fantasy-land/compose :: Semigroupoid c => c i j ~> c j k -> c i k

A value which has a Semigroupoid must provide a fantasy-land/compose method. The fantasy-land/compose method takes one argument:

a['fantasy-land/compose'](b)

1. b must be a value of the same Semigroupoid

   1. If b is not the same semigroupoid, behaviour of fantasy-land/compose is unspecified.

2. fantasy-land/compose must return a value of the same Semigroupoid.

Category

A value that implements the Category specification must also implement the Semigroupoid specification.

1. a['fantasy-land/compose'](C['fantasy-land/id']()) is equivalent to a (right identity)
2. C['fantasy-land/id']()['fantasy-land/compose'](a) is equivalent to a (left identity)

fantasy-land/id method

fantasy-land/id :: Category c => () -> c a a

A value which has a Category must provide a fantasy-land/id function on its type representative:

C['fantasy-land/id']()

Given a value c, one can access its type representative via the constructor property:

c.constructor['fantasy-land/id']()

1. fantasy-land/id must return a value of the same Category

Semigroup

1. a['fantasy-land/concat'](b)['fantasy-land/concat'](c) is equivalent to a['fantasy-land/concat'](b['fantasy-land/concat'](c)) (associativity)

fantasy-land/concat method

fantasy-land/concat :: Semigroup a => a ~> a -> a

A value which has a Semigroup must provide a fantasy-land/concat method. The fantasy-land/concat method takes one argument:

s['fantasy-land/concat'](b)

1. b must be a value of the same Semigroup

   1. If b is not the same semigroup, behaviour of fantasy-land/concat is unspecified.

2. fantasy-land/concat must return a value of the same Semigroup.

Monoid

A value that implements the Monoid specification must also implement the Semigroup specification.

1. m['fantasy-land/concat'](M['fantasy-land/empty']()) is equivalent to m (right identity)
2. M['fantasy-land/empty']()['fantasy-land/concat'](m) is equivalent to m (left identity)

fantasy-land/empty method

fantasy-land/empty :: Monoid m => () -> m

A value which has a Monoid must provide a fantasy-land/empty function on its type representative:

M['fantasy-land/empty']()

Given a value m, one can access its type representative via the constructor property:

m.constructor['fantasy-land/empty']()

1. fantasy-land/empty must return a value of the same Monoid

Group

A value that implements the Group specification must also implement the Monoid specification.

1. g['fantasy-land/concat'](g['fantasy-land/invert']()) is equivalent to g.constructor['fantasy-land/empty']() (right inverse)
2. g['fantasy-land/invert']()['fantasy-land/concat'](g) is equivalent to g.constructor['fantasy-land/empty']() (left inverse)

fantasy-land/invert method

fantasy-land/invert :: Group g => g ~> () -> g

A value which has a Group must provide a fantasy-land/invert method. The fantasy-land/invert method takes no arguments:

g['fantasy-land/invert']()

1. fantasy-land/invert must return a value of the same Group.

Filterable

1. v['fantasy-land/filter'](x => p(x) && q(x)) is equivalent to v['fantasy-land/filter'](p)['fantasy-land/filter'](q) (distributivity)
2. v['fantasy-land/filter'](x => true) is equivalent to v (identity)
3. v['fantasy-land/filter'](x => false) is equivalent to w['fantasy-land/filter'](x => false) if v and w are values of the same Filterable (annihilation)

fantasy-land/filter method

fantasy-land/filter :: Filterable f => f a ~> (a -> Boolean) -> f a

A value which has a Filterable must provide a fantasy-land/filter method. The fantasy-land/filter method takes one argument:

v['fantasy-land/filter'](p)

1. p must be a function.

   1. If p is not a function, the behaviour of fantasy-land/filter is unspecified.
   2. p must return either true or false. If it returns any other value, the behaviour of fantasy-land/filter is unspecified.

2. fantasy-land/filter must return a value of the same Filterable.

Functor

1. u['fantasy-land/map'](a => a) is equivalent to u (identity)
2. u['fantasy-land/map'](x => f(g(x))) is equivalent to u['fantasy-land/map'](g)['fantasy-land/map'](f) (composition)

fantasy-land/map method

fantasy-land/map :: Functor f => f a ~> (a -> b) -> f b

A value which has a Functor must provide a fantasy-land/map method. The fantasy-land/map method takes one argument:

u['fantasy-land/map'](f)

1. f must be a function,

   1. If f is not a function, the behaviour of fantasy-land/map is unspecified.
   2. f can return any value.
   3. No parts of f's return value should be checked.

2. fantasy-land/map must return a value of the same Functor

Contravariant

1. u['fantasy-land/contramap'](a => a) is equivalent to u (identity)
2. u['fantasy-land/contramap'](x => f(g(x))) is equivalent to u['fantasy-land/contramap'](f)['fantasy-land/contramap'](g) (composition)

fantasy-land/contramap method

fantasy-land/contramap :: Contravariant f => f a ~> (b -> a) -> f b

A value which has a Contravariant must provide a fantasy-land/contramap method. The fantasy-land/contramap method takes one argument:

u['fantasy-land/contramap'](f)

1. f must be a function,

   1. If f is not a function, the behaviour of