More than 1 year has passed since last update.

fp-ts 代数型の型クラス

Last updated at 2022-02-20Posted at 2021-07-19

fp-tsはstatic-landで定義されたTypeScriptの代数型を参照して実装されている。
馴染みのない用語だらけなので、整理がてらに仕様のまとめ。

代数型	要約	継承
Setoid	等値関係
Ord	大小関係	Setoid
Semigroup	半群、二項演算
Monoid	モノイド、二項演算 + 単位元	Semigroup
Group	群、二項演算 + 単位元 + 逆元	Monoid
Semiroupid	半圏、恒等射のない圏
Category	圏	Semigroupid
Functor	関手
Bifunctor	双関手	Functor
Contravariant	反変関手
Profunctor	対角関手	Functor
Apply	評価射、積と冪からなる随伴の余単位	Functor
Applicative	強Laxモノイダル関手	Apply
Chain	モナドの結合法則	Apply
Monad	モナド	Chain, Applicative
Extend	コモナドの結合法則	Functor
Comonad	コモナド	Extend
Alt	関手の（圏論的な意味でない）結合法則と分配法則	Functor
Plus	関手の（圏論的な意味でない）結合法則と分配法則と単位元	Alt
Alternative		Plus, Applicative
Filterable	フィルタリング
ChainRec	末尾再帰のChain	Chain
Foldable	catamorphism
Traversable	計算効果の簡約化	Functor, Foldable

「型クラス」とは言え、HaskellとかScalaとは違い、言語的サポートがないTypeScriptでは、単なるインタフェースとして定義されてる。
便利でもないし、扱いやすくもない。fp-tsではTypeScriptのわりと特殊な（だけども素晴らしい設計の）型システムを
最大限利用して高階カインド（らしきもの）をひねり出しているので、すこしは扱いやすくなっている。

Setoid

等値関係が定義された集合。

Setoid<T> {
  equals: (T, T) => boolean
}

法則

Reflexivity: S.equals(a, a) === true
Symmetry: S.equals(a, b) === S.equals(b, a)
Transitivity: if S.equals(a, b) and S.equals(b, c), then S.equals(a, c)

Ord

大小関係が全ての要素に対して定義されている集合。

Ord<T> {
  lte: (T, T) => boolean
}

法則

Totality: S.lte(a, b) or S.lte(b, a)
Antisymmetry: if S.lte(a, b) and S.lte(b, a), then S.equals(a, b)
Transitivity: if S.lte(a, b) and S.lte(b, c), then S.lte(a, c)

Semigroup

２項演算が定義されている集合

Semigroup<T> {
  concat: (T, T) => T
}

法則

結合則: S.concat(S.concat(a, b), c) ≡ S.concat(a, S.concat(b, c))

Monoid

２項演算に加えて、単位元が定義されている集合

Monoid<T> {
  empty: () => T
}

法則

右単位元: M.concat(a, M.empty()) ≡ a
左単位元: M.concat(M.empty(), a) ≡ a

Group

２項演算、単位元に加えて、逆元が定義されている集合

Group<T> {
  invert: (T) => T
}

法則

右逆元: G.concat(a, G.invert(a)) ≡ G.empty()
左逆元: G.concat(G.invert(a), a) ≡ G.empty()

Semigroupoid

恒等射がない圏（恒等射がない時点で圏の定義から外れるので、圏じゃないのだけれど...）。

Semigroupoid<T> {
  compose: <i, j, k>(T<i, j>, T<j, k>) => T<i, k>
}

法則

結合則: S.compose(S.compose(a, b), c) ≡ S.compose(a, S.compose(b, c))

Functor

Functor<T> {
  map: <a, b>(a => b, T<a>) => T<b>
}

法則

単位元: F.map(x => x, a) ≡ a
合成: F.map(x => f(g(x)), a) ≡ F.map(f, F.map(g, a))

Bifunctor

Bifunctor<T> {
  bimap: <a, b, c, d>(a => b, c => d, T<a, c>) => T<b, d>
}

法則

単位元: B.bimap(x => x, x => x, a) ≡ a
合成: B.bimap(x => f(g(x)), x => h(i(x)), a) ≡ B.bimap(f, h, B.bimap(g, i, a))

mapの導出

Functor's map: A.map = (f, u) => A.bimap(x => x, f, u)

Contravariant

Contravariant<T> {
  contramap: <a, b>(a => b, T<b>) => T<a>
}

法則

単位元: F.contramap(x => x, a) ≡ a
合成: F.contramap(x => f(g(x)), a) ≡ F.contramap(g, F.contramap(f, a))

Profunctor

Profunctor<T> {
  promap: <a, b, c, d>(a => b, c => d, T<b, c>) => T<a, d>
}

法則

単位元: P.promap(x => x, x => x, a) ≡ a
合成: P.promap(x => f(g(x)), x => h(i(x)), a) ≡ P.promap(g, h, P.promap(f, i, a))

mapの導出

Functor's map: A.map = (f, u) => A.promap(x => x, f, u)

Haskellだとpromapでなくdimap

dimap :: (a -> b) -> (c -> d) -> p b c -> p a d

Apply

評価射、積と冪からなる随伴の余単位。

Apply<T> {
  ap: <a, b>(T<a => b>, T<a>) => T<b>
}

法則

合成: A.ap(A.ap(A.map(f => g => x => f(g(x)), a), u), v) ≡ A.ap(a, A.ap(u, v))

Applicative

Applicative関手についてはこちらのサイト - アプリカティブ関手ってなに？モノイド圏との関係は？調べてみました！ - が詳しくて日本語でお勧めです。
（中身を理解していないので伝聞調、信頼性なし）

圏論的には strong lax monoidal functor というらしい。laxは「〔規律などが〕緩い」という意味だそうで、無理くり訳すと「強くて緩いモノイダル関手」となって、訳さない、カタカナのママがよい用語の好例なのかもしれない。

StackExchange: Explaining Applicative functor in categorical terms - monoidal functorsによると、カルテシアン閉圏のモノイダル関手が「強」であることと、自然変換map:(A⇒B)→(F(A)⇒F(B))を持つことは同値となる。モノイダル閉圏なので(A⇒B)も(F(A)⇒F(B))も内部Homとして存在して、それらの間に射があるというが「強」の条件となっている。

またlax monoidal functorは、モノイダル関手（モノイダル圏(C,⊗,I) から (D,⊕,J) への関手）に対して自然変換i:J→F(I)を条件としているらしいので、これがofのインタフェースになっているっぽい。

Wikipediaでカルテシアン閉圏を調べるとデカルト閉圏が出てきて、「デカルト閉（英語: cartesian closed）な圏はラムダ計算の自然な設定ができるという点で数理論理学およびプログラミングの理論において特に重要である。デカルト閉圏の概念はモノイド圏に一般化される」んだそうで、プログラミングにおいてはこの辺りの性質がガバガバで利用できる、っぽい。

Applicative<T> {
  of: <a>(a) => T<a>
}

法則

Identity: A.ap(A.of(x => x), v) ≡ v
Homomorphism: A.ap(A.of(f), A.of(x)) ≡ A.of(f(x))
Interchange: A.ap(u, A.of(y)) ≡ A.ap(A.of(f => f(y)), u)

mapの導出

Functor's map: A.map = (f, u) => A.ap(A.of(f), u)

Chain

Chain<T> {
  chain: <a, b>(a => T<b>, T<a>) => T<b>
}

法則

結合則: M.chain(g, M.chain(f, u)) ≡ M.chain(x => M.chain(g, f(x)), u)

apの導出

Apply's ap: A.ap = (uf, ux) => A.chain(f => A.map(f, ux), uf)

Monad

モナド。

法則

左単位元: M.chain(f, M.of(a)) ≡ f(a)
右単位元: M.chain(M.of, u) ≡ u

mapの導出

Functor's map: A.map = (f, u) => A.chain(x => A.of(f(x)), u)

Extend

Chainの双対。

Extend<T> {
  extend: <a, b>(T<a> => b, T<a>) => T<b>
}

法則

結合則: E.extend(f, E.extend(g, w)) ≡ E.extend(_w => f(E.extend(g, _w)), w)

Comonad

コモナド。

Comonad<T> {
  extract: <a>(T<a>) => a
}

法則

左単位元: C.extend(C.extract, w) ≡ w
右単位元: C.extract(C.extend(f, w)) ≡ f(w)

Alt

関手の並列的な合成。合成とは言え、圏論的な意味合いではなく、
Altという名のごとく、同時に実行して、その結果からどちらかを
「選択」する、もしくは単純な「和」をとるようなことする場合に使う。

ある文字列を parse するのに、それが数字なのかキーワードなのか時間なのか、
それぞれの parser を Alt でまとめて最初にうまく行った parser の結果に
より選択する、とか、代数的というよりはプログラミング的な意味合い。

Alt<T> {
  alt: <a>(T<a>, T<a>) => T<a>
}

法則

結合則: A.alt(A.alt(a, b), c) ≡ A.alt(a, A.alt(b, c))
分配則: A.map(f, A.alt(a, b)) ≡ A.alt(A.map(f, a), A.map(f, b))

Plus

fp-tsではPlusの実装はなく、zeroはAlternativeで定義している。

Plus<T> {
  zero: <a>() => T<a>
}

法則

右単位元: P.alt(a, P.zero()) ≡ a
左単位元: P.alt(P.zero(), a) ≡ a
零化: P.map(f, P.zero()) ≡ P.zero()

Alternative

「和」であるaltに対して、apが「積」を期待されているようにみえる。

法則

分配則: A.ap(A.alt(a, b), c) ≡ A.alt(A.ap(a, c), A.ap(b, c))
零化: A.ap(A.zero(), a) ≡ A.zero()

Filterable

Filterable<T> {
  filter: <a>(a => boolean, T<a>) => T<a>
}

法則

分配則: F.filter(x => f(x) && g(x), a) ≡ F.filter(g, F.filter(f, a))
単位元: F.filter(x => true, a) ≡ a
零化: F.filter(x => false, a) ≡ F.filter(x => false, b)

ChainRec

Recはrecursion（再帰）の意味。Stack overflowを避けるのにtail recursion（末尾再帰）の実装をする（して欲しい）。

ChainRec<T> {
  chainRec: <a, b>((a => Next<a>, b => Done<b>, a) => T<Next<a> | Done<b>>, a) => T<b>
}

法則

等価性: C.chainRec((next, done, v) => p(v) ? C.map(done, d(v)) : C.map(next, n(v)), i) ≡ (function step(v) { return p(v) ? d(v) : C.chain(step, n(v)) }(i))
Stack usage of C.chainRec(f, i) must be at most a constant multiple of the stack usage of f itself.

// fp-tsでの定義は違う

export interface ChainRec<F> extends Chain<F> {
  readonly chainRec: <A, B>(a: A, f: (a: A) => HKT<F, Either<A, B>>) => HKT<F, B>
}

// FがIdentityの場合のchainRecの実装は用意されている
//
// よくあるEitherの使い方ではない。rightが正常値、leftがエラー値ではない。読み間違えないように

export const tailRec = <A, B>(startWith: A, f: (a: A) => Either<A, B>): B => {
  let ab = f(startWith)
  while (ab._tag === 'Left') {
    ab = f(ab.left)
  }
  return ab.right
}

Foldable

Foldable<T> {
  reduce: <a, b>((a, b) => a, a, T<b>) => a
}

関手Tに対するcatamorphisim（の一種）。第1引数と第2引数がF代数（を作るために必要なブツ）、キャリア型が<a,b>

法則

F.reduce ≡ (f, x, u) => F.reduce((acc, y) => acc.concat([y]), [], u).reduce(f, x)
- 最初のreduceで、uを[ ](配列)に移し替えた後、その配列に対して2番目のreduceを行っても結果は同じ。

fp-tsインスタンス

Array
Either
Identity
Map
NonEmptyArray
Option
ReadonlyArray
ReadonlyMap
ReadonlyNonEmptyArray
ReadonlyRecord
ReadonlyTuple
Record
These
Tree
Tuple

Traversable

Uは何がしかの計算効果をもつものとして、その計算効果をTの各要素の計算に個別に（複数回）適用するのでなく、Tの各要素の計算全体に（１回だけ）適用する。

[#] 計算効果

Traversable<T> {
  traverse: <U, a, b>(Applicative<U>, a => U<b>, T<a>) => U<T<b>>
}

法則

Naturality: f(T.traverse(A, x => x, u)) ≡ T.traverse(B, f, u) for any f such that B.map(g, f(a)) ≡ f(A.map(g, a))
- aに対して、関数f（計算効果を伴う）を適用した後にgを適用することと、gを適用した後に関数fを適用することの結果は同じとみなせる。
単位元: T.traverse(F, F.of, u) ≡ F.of(u) for any Applicative F
合成: T.traverse(Compose(A, B), x => x, u) ≡ A.map(v => T.traverse(B, x => x, v), T.traverse(A, x => x, u)) for Compose defined bellow and for any Applicatives A and B

function Compose(A, B) {
  return {

    of(x) {
      return A.of(B.of(x))
    },

    ap(a1, a2) {
      return A.ap(A.map(b1 => b2 => B.ap(b1, b2), a1), a2)
    },

    map(f, a) {
      return A.map(b => B.map(f, b), a)
    },

  }
}

reduceの導出

F.reduce = (f, acc, u) => {
  const of = () => acc
  const map = (_, x) => x
  const ap = f
  return F.traverse({of, map, ap}, x => x, u)
}

mapの導出

`js
F.map = (f, u) => {
const of = (x) => x
const map = (f, a) => f(a)
const ap = (f, a) => f(a)
return F.traverse({of, map, ap}, f, u)
}

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

fp-ts 代数型の型クラス

Setoid

Ord

Semigroup

Monoid

Group

Semigroupoid

Category

Functor

Bifunctor

Contravariant

Profunctor

Apply

Applicative

Chain

Monad

Extend

Comonad

Alt

Plus

Alternative

Filterable

ChainRec

Foldable

Traversable