Спецификация Fantasy Land

(aka "Спецификация Алгебраический JavaScript")

Этот проект определяет взаимодействие общих алгебраических структур:

Setoid
Semigroup
Monoid
Functor
Contravariant
Apply
Applicative
Alt
Plus
Alternative
Foldable
Traversable
Chain
ChainRec
Monad
Extend
Comonad
Bifunctor
Profunctor

Общее

Алгебра представляет собой набор значений, набор операторов, которые зависимы и должны подчиняться некоторым законам.

Каждая алгебра Fantasy Land – это отдельная спецификация. Алгебра может иметь зависимости от реализаций других алгебр.

Терминология

"значение" любые JavaScript значения, включая структуры определенные ниже.
"эквивалент" - подходящее определение эквивалентности для заданного значения. Определение должно гарантировать, что эти два значения могут быть безопасно переставлены в программе, что подтверждает абстракцию. Например:

Два списка эквивалентны, если они эквивалентны по всем показателям.
Два обычных JavaScript объекта, представленные как словари, эквивалентны, если они эквивалентны по всем ключам.
Два промиса эквивалентны, когда они возвращают эквивалентные значения.
Две функции эквивалентны, если они дают эквивалентные результаты для эквивалентных входных данных.

Префиксы имен методов

Для тех типов данных, которые должны быть совместимы с Fantasy Land, значения должны иметь определенные свойства. Эти свойства имеют префикс fantasy-land/.

Например:

//  MyType#fantasy-land/map :: MyType a ~> (a -> b) -> MyType b
MyType.prototype['fantasy-land/map'] = ...

Далее в этом документе имена без префиксов используются только для уменьшения шума.

Для удобства вы можете использовать пакет fantasy-land:

var fl = require('fantasy-land')

// ...

MyType.prototype[fl.map] = ...

// ...

var foo = bar[fl.map](x => x + 1)

Представление типа

Определенные виды поведения определяются с точки зрения представления типа. Другие поведения не требуют представления. Таким образом, определенные алгебры требуют тип для предоставления значения-уровня представления (с определенными свойствами). Тип Identity, например, может обеспечить Id в качестве своего представителя типа: Id :: TypeRep Identity.

Если тип предоставляет представителя типа, каждый представитель типа должен иметь свойство constructor, которое является ссылкой на представителя типа.

Алгебры

Setoid

a.equals(a) === true (рефлексивность)
a.equals(b) === b.equals(a) (симметрия)
Если a.equals(b) и b.equals(c), то a.equals(c) (транзитивность)

Метод `equals`

equals :: Setoid a => a ~> a -> Boolean

Значение Setoid должно предоставить метод equals. Метод equals принимает один аргумент:

a.equals(b)

b должен быть значением того же Setoid
1. Если b не тот же Setoid, поведение equals не определено (рекомендуется возвращать false)
equals должен возвращать логическое значение (true или false)

Semigroup

a.concat(b).concat(c) эквивалентно a.concat(b.concat(c)) (ассоциативность)

Метод `concat`

concat :: Semigroup a => a ~> a -> a

Значение Semigroup должно предоставить метод concat. Метод concat принимает один аргумент:

s.concat(b)

b должен быть значением того же Semigroup
1. Если b не тот же Semigroup, поведение concat не определено
concat должен возвращать значение того же Semigroup

Monoid

Значение, которое реализует спецификацию Monoid, должно также реализовать спецификацию Semigroup.

m.concat(M.empty()) эквивалентно m (точный справа)
M.empty().concat(m) эквивалентно m (точный слева)

Метод `empty`

empty :: Monoid m => () -> m

Значение Monoid должно предоставить метод empty в её представлении типа:

M.empty()

Получив значение m, можно получить представление типа через свойство constructor:

m.constructor.empty()

empty должен возвращать значение того же Monoid

Functor

u.map(a => a) эквивалентно u (точный)
u.map(x => f(g(x))) эквивалентно u.map(g).map(f) (композиция)

Метод `map`

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

Значение Functor должно предоставить метод map. Метод map принимает один аргумент:

u.map(f)

f должен быть функцией
1. Если f не функция, поведение map не определено
2. f может вернуть любое значение
3. Значения возвращенные f проверять не надо
map должен возвращать значение того же Functor

Contravariant

u.contramap(a => a) эквивалентно u (точный)
u.contramap(x => f(g(x))) эквивалентно u.contramap(f).contramap(g) (композиция)

Метод `contramap`

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

Значение Contravariant должно предоставить метод contramap. Метод contramap принимает один аргумент:

u.contramap(f)

f должен быть функцией
1. Если f не функция, поведение contramap не определено
2. f может вернуть любое значение
3. Значения возвращенные f проверять не надо
contramap должен возвращать значение того же Contravariant

Apply

Значение, которое реализует спецификация Apply, должно также реализовывать спецификацию Functor.

v.ap(u.ap(a.map(f => g => x => f(g(x))))) эквивалентно v.ap(u).ap(a) (композиция)

Метод `ap`

ap :: Apply f => f a ~> f (a -> b) -> f b

Значение Apply должно предоставить метод ap. Метод ap принимает один аргумент:

a.ap(b)

b должен быть функцией
1. Если b не является функцией, поведение ap не определено
a должен быть любым значением Apply
ap должны применять функцию Apply b со значением Apply a
1. Значения возвращенные этой функцией проверять не надо

Applicative

Значение, которое реализует спецификация Applicative, должно также реализовывать спецификацию Apply.

v.ap(A.of(x => x)) эквивалентно v (точный)
A.of(x).ap(A.of(f)) эквивалентно А.(Ф(Х)) (гомоморфизм)
A.of(y).ap(u) эквивалентно u.ap(A.of(f => f(y))) (перестановка)

Метод `of`

of :: Applicative f => a -> f a

Значение Applicative должно предоставить метод of в её представлении типа. Функция of принимает один аргумент:

F.of(a)

Получив значение f, можно получить представление типа через свойство constructor:

f.constructor.of(a)

of должен вернуть значение того же Applicative
1. Значения возвращенные a проверять не надо

Alt

Значение, которое реализует спецификацию Alt, должно также реализовать спецификацию Functor.

a.alt(b).alt(c) эквивалентно a.alt(b.alt(c)) (ассоциативность)
a.alt(b).map(f) эквивалентно a.map(f).alt(b.map(f)) (распределённость)

Метод `alt`

alt :: Alt f => f a ~> f a -> f a

Значение Alt должно предоставить метод alt. Метод alt принимает один аргумент:

a.alt(b)

b должен быть значением того же Alt
1. Если b не тот же Alt, поведение alt не определено
2. a и b могут содержать любое значение того же типа
3. Значения содержащиеся в a и b проверять не надо
alt должен вернуть значение того же Alt

Plus

Значение, которое реализует спецификацию Plus, также должно реализовать спецификацию Alt.

x.alt(A.zero()) эквивалентно x (точный справа)
A.zero().alt(x) эквивалентно x (точный слева)
A.zero().map(f) эквивалентно A.zero() (упразднение)

Метод `zero`

zero :: Plus f => () -> f a

Значение Plus должно предоставить метод zero в её представлении типа:

A.zero()

Получив значение x, можно получить представление типа через свойство constructor:

x.constructor.zero()

zero должен возвращать значение того же Plus

Alternative

Значение, которое реализует спецификацию Alternative, должно также реализовать спецификации Applicative и Plus.

x.ap(f.alt(g)) эквивалентно x.ap(f).alt(x.ap(g)) (распределённость)
x.ap(A.zero()) эквивалентно A.zero() (упразднение)

Foldable

u.reduce эквивалентно u.reduce((acc, x) => acc.concat([x]), []).reduce

Метод `reduce`

reduce :: Foldable f => f a ~> ((b, a) -> b, b) -> b

Значение Foldable должно предоставить метод reduce. Метод reduce принимает два аргумента:

u.reduce(f, x)

f должен быть двоичной функцией
1. Если f не функция, поведение reduce не определено
2. Первый аргумент f должен быть такого же типа, как x
3. f должен возвращать значение такого же типа, как x
4. Значения возвращенные f проверять не надо
x - это первоначальное аккумулятивное значение для преобразования
1. x проверять не надо

Traversable

Значение, которое реализует спецификацию Traversable, должно также реализовывать спецификации Functor и Foldable.

t(u.traverse(F, x => x)) эквивалентно u.traverse(G, t) для любого t такого, что t(a).map(f) эквивалентно t(a.map(f)) (нормализованность)
u.traverse(F, F.of) эквивалентно F.of(u) для любой Applicative F (точный)
u.traverse(Compose, x => new Compose(x)) эквивалентно new Compose(u.traverse(F, x => x).map(x => x.traverse(G, x => x))) для Compose, определенных ниже, и любых Applicatives F и G (композиция)

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`

traverse :: Applicative f, Traversable t => t a ~> (TypeRep f, a -> f b) -> f (t b)

Значение Traversable должно предоставить метод traverse. Метод traverse принимает два аргумента:

u.traverse(A, f)

A должен быть представлением типа Applicative
f должен быть функцией, которая возвращает значение
1. Если f не функция, поведение traverse не определено
2. f должен возвращать значение типа, представленного A
traverse должен возвращать значение типа представленного A

Chain

Значение, которое реализует спецификацию Chain, должно также реализовывать спецификацию Apply.

m.chain(f).chain(g) эквивалентно m.chain(x => f(x).chain(g)) (ассоциативность)

Метод `chain`

chain :: Chain m => m a ~> (a -> m b) -> m b

Значение Chain должно предоставить метод chain. Метод chain принимает один аргумент:

m.chain(f)

f должен быть функцией, которая возвращает значение
1. Если f не функция, поведение chain не определено
2. f должен возвращать значение того же Chain
chain должен возвращать значение того же Chain

ChainRec

Значение, которое реализует спецификацию ChainRec, должно реализовать спецификацию Chain.

M.chainRec((next, done, v) => p(v) ? d(v).map(done) : n(v).map(next), i) эквивалентно (function step(v) { return p(v) ? d(v) : n(v).chain(step); }(i)) (эквивалентность)
Использование M.chainRec(f, i) должно быть максимально подобным самостоятельному вызову f

Метод `chainRec`

chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b

Значение ChainRec должно предоставить метод chainRec в его представлении типа. Метод chainRec принимает два аргумента:

M.chainRec(f, i)

Получив значение m, можно получить представление типа через свойство constructor:

m.constructor.chainRec(f, i)

f должен быть функцией, которая возвращает значение
1. Если f не функция, поведение chainRec не определено
2. f принимает три аргумента next, done, value
  1. next - это функция, которая принимает один аргумент того же типа, как i и может вернуть любое значение
  2. done - это функция, которая принимает один аргумент и возвращает тот же тип, возвращаемое значение next
  3. value - это значение такого же типа, как i
3. f должен возвращать значение того же ChainRec, который содержит значение, возвращаемое из done или next
chainRec должен возвращать значение того же ChainRec, который содержит то же значение, что и аргумент done

Monad

Значение, которое реализует спецификацию Monad, должно также реализовать спецификации Applicative and Chain.

M.of(a).chain(f) эквивалентно f(a) (точный слева)
m.chain(M.of) эквивалентно m (точный справа)

Extend

Значение, которое реализует спецификацию Extend, должно реализовать спецификацию Functor.

w.extend(g).extend(f) эквивалентно w.extend(_w => f(_w.extend(g)))

Метод `extend`

extend :: Extend w => w a ~> (w a -> b) -> w b

Значение Extend должно предоставить метод extend. Метод extend принимает один аргумент:

 w.extend(f)

f должен быть функцией, которая возвращает значение
1. Если f не функция, поведение extend неопределено
2. f должен возвращать значение типа v, для некоторой переменной v, содержащейся в w
3. Значения возвращенные f проверять не надо
extend должен возвращать значение того же Extend

Comonad

Значение, которое реализует спецификацию Comonad, должно реализовать спецификацию Extend.

w.extend(_w => _w.extract()) эквивалентно w (точный слева)
w.extend(f).extract() эквивалентно f(w) (точный справа)

Метод `extract`

extract :: Comonad w => w a ~> () -> a

Значение Comonad должно предоставить метод extract. Метод extract не принимает никаких аргументов:

w.extract()

extract должен возвращать значение типа v, для некоторой переменной v, содержащиеся в w
1. v должен иметь тот же тип, что возвращает f в extend

Bifunctor

Значение, которое реализует спецификацию Bifunctor, должно также реализовать спецификацию Functor.

p.bimap(a => a, b => b) эквивалентно р (точный)
p.bimap(a => f(g(a)), b => h(i(b)) эквивалентно p.bimap(g, i).bimap(f, h) (композиция)

Метод `bimap`

bimap :: Bifunctor f => f a c ~> (a -> b, c -> d) -> f b d

Значение Bifunctor должно предоставить метод bimap. Метод bimap принимает два аргумента:

c.bimap(f, g)

f должен быть функцией, которая возвращает значение
1. Если f не функция, поведение bimap не определено
2. f может вернуть любое значение
3. Значение, возвращенное f, проверять не надо
g должен быть функцией, которая возвращает значение
1. Если g не функция, поведение promap не определено
2. g может возвращать любое значение
3. Значение, возвращенное g, проверять не надо
bimap должен возвращать значение того же Bifunctor

Profunctor

Значение, которое реализует спецификацию Profunctor, должно также реализовать спецификацию Functor.

p.promap(a => a, b => b) эквивалентно р (точный)
p.promap(a => f(g(a)), b => h(i(b))) эквивалентно p.promap(f, i).promap(g, h) (композиция)

Метод `promap`

promap :: Profunctor p => p b c ~> (a -> b, c -> d) -> p a d

Значение Profunctor должно предоставить метод promap. Метод profunctor принимает два аргумента:

c.promap(f, g)

f должен быть функцией, которая возвращает значение
1. Если f не функция, поведение promap не определено
2. f может вернуть любое значение
3. Значение, возвращенное f, проверять не надо
g должен быть функцией, которая возвращает значение
1. Если g не функция, поведение promap не определено
2. g может возвращать любое значение
3. Значение, возвращенное g, проверять не надо
promap должен возвращать значение того же Profunctor

Реализации

При создании типов данных, которые удовлетворяют нескольким алгебрам, авторы могут выбрать для реализации определенных методов другие методы. Реализации:

map может быть реализован с помощью ap и of:
```
function(f) { return this.ap(this.of(f)); }
```
mapможет быть реализован с помощью chain и of:
```
function(f) { return this.chain(a => this.of(f(a))); }
```
map может быть реализован с помощью bimap:
```
function(f) { return this.bimap(a => a, f); }
```
map может быть реализован с помощью promap:
```
function(f) { return this.promap(a => a, f); }
```
ap может быть реализован с помощью chain:
```
function(m) { return m.chain(f => this.map(f)); }
```

reduce может быть реализован так:

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 может быть реализован так:

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;
}

Если тип данных реализует метод, который может быть реализован, его поведение должно быть эквивалентно реализации (или реализациям).

Примечания

Если есть больше, чем один способ реализации методов и законов, реализация должна выбрать один и представить обертку для других применений.
Не рекомендуется перегружать спецификации методов. Можно легко в результате получить сломанное и неправильное поведение.
Рекомендуется выбрасывать предупреждение на незадокументированное применение.
Контейнер Id, реализующий множество методов, доступен в internal/id.js.

Альтернативы

Существует также Спецификация Static Land

Name		Name	Last commit message	Last commit date
Latest commit History 232 Commits
figures		figures
internal		internal
laws		laws
.gitignore		.gitignore
.travis.yml		.travis.yml
LICENSE		LICENSE
README.md		README.md
bower.json		bower.json
implementations.md		implementations.md
index.js		index.js
logo.png		logo.png
package.json		package.json
test.js		test.js

License

devSchacht/fantasy-land

Folders and files

Latest commit

History

Repository files navigation

Спецификация Fantasy Land

Общее

Терминология

Префиксы имен методов

Представление типа

Алгебры

Setoid

Метод equals

Semigroup

Метод concat

Monoid

Метод empty

Functor

Метод map

Contravariant

Метод contramap

Apply

Метод ap

Applicative

Метод of

Alt

Метод alt

Plus

Метод zero

Alternative

Foldable

Метод reduce

Traversable

Метод traverse

Chain

Метод chain

ChainRec

Метод chainRec