Спецификация Fantasy Land
(aka “Спецификация Алгебраический JavaScript”)
Перевод спецификации Fantasy Land.
Этот проект определяет взаимодействие общих алгебраических структур:
- 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. Если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. Если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
должен быть функцией. Еслиf
не функция, поведениеmap
не определено.f
может вернуть любое значение. Значения возвращенные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
должен быть функцией. Еслиf
не функция, поведениеcontramap
не определено.f
может вернуть любое значение. Значения возвращенные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
должен быть функцией. Еслиb
не является функцией, поведениеap
не определеноa
должен быть любым значением Applyap
должны применять функцию Applyb
со значением Applya
. Значения возвращенные этой функцией проверять не надо
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. Значения возвращенные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. Еслиb
не тот же Alt, поведениеalt
не определено.a
иb
могут содержать любое значение того же типа. Значения содержащиеся в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
должен быть двоичной функцией. Еслиf
не функция, поведениеreduce
не определено. Первый аргументf
должен быть такого же типа, какx
.f
должен возвращать значение такого же типа, какx
. Значения возвращенныеf
проверять не надоx
- это первоначальное аккумулятивное значение для преобразования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)
для любой ApplicativeF
(идентичность)u.traverse(Compose, x => new Compose(x))
эквивалентноnew Compose(u.traverse(F, x => x).map(x => x.traverse(G, x => x)))
дляCompose
, определенных ниже, и любых ApplicativesF
и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
должен быть представлением типа Applicativef
должен быть функцией, которая возвращает значение. Еслиf
не функция, поведениеtraverse
не определено.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
должен быть функцией, которая возвращает значение. Еслиf
не функция, поведениеchain
не определено.f
должен возвращать значение того же Chainchain
должен возвращать значение того же 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
должен быть функцией, которая возвращает значение. Еслиf
не функция, поведениеchainRec
не определено.f
принимает три аргументаnext
,done
,value
.next
- это функция, которая принимает один аргумент того же типа, какi
и может вернуть любое значение.done
- это функция, которая принимает один аргумент и возвращает тот же тип, возвращаемое значениеnext
.value
- это значение такого же типа, какi
.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
должен быть функцией, которая возвращает значение. Еслиf
не функция, поведениеextend
не определено.f
должен возвращать значение типаv
, для некоторой переменнойv
, содержащейся вw
. Значения возвращенные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
.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
должен быть функцией, которая возвращает значение. Еслиf
не функция, поведениеbimap
не определено.f
может вернуть любое значение. Значение, возвращенноеf
, проверять не надоg
должен быть функцией, которая возвращает значение. Еслиg
не функция, поведениеpromap
не определено.g
может возвращать любое значение. Значение, возвращенное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
должен быть функцией, которая возвращает значение. Еслиf
не функция, поведениеpromap
не определено.f
может вернуть любое значение. Значение, возвращенноеf
, проверять не надоg
должен быть функцией, которая возвращает значение. Еслиg
не функция, поведениеpromap
не определено.g
может возвращать любое значение. Значение, возвращенное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
Читайте нас на Медиуме, контрибьютьте на Гитхабе, общайтесь в группе Телеграма, следите в Твиттере и канале Телеграма, рекомендуйте в VK и Facebook. Скоро подъедет подкаст, не теряйтесь. Эта спецификация на GitHub.