第13章: モノイドによる統合

ワイルド・コンビネーション

本章では、セミグループを経由してモノイドを考察する。モノイドは数学的抽象化における髪についたガムのような存在だ。複数の分野に跨る概念を捕捉し、比喩的にも文字的にもそれらを統合する。計算に関わる全てを繋ぐ脅威的な力であり、コードベースの酸素であり、実行基盤であり、量子もつれをコード化した存在である。

モノイドは結合に関する概念である。しかし結合とは何か？ 累加、連結、乗算、選択、合成、順序付け、評価まで含む多様な意味を持つ。本章では多くの例を提示するが、モノイドの山麓を軽く踏む程度に留める。実例は豊富で応用範囲は広大だ。本章の目的は直観的理解を提供し、独自のモノイドを構築できるようにすることである。

加算の抽象化

加算には議論すべき興味深い特性がある。抽象化レンズを通して考察してみよう。

まず、二項演算である点。つまり同一集合内の2つの値を受け取り、1つの値を返す操作だ。

// a binary operation
1 + 1 = 2

見ての通り、定義域の2値から余域の1値を生成し、すべて同じ集合（数値）に属する。これを「加算について閉じている」と言い、型が変化しないことを意味する。この性質により操作を連鎖できる:

// we can run this on any amount of numbers
1 + 7 + 5 + 4 + ...

さらに（計算された洒落...）結合性を備えるため、演算のグループ化を自由に行える。ちなみに結合的二項演算は並列計算の基盤となる。作業を分割分散可能だからだ。

// associativity
(1 + 2) + 3 = 6
1 + (2 + 3) = 6

ただし、これは順序変更を許す可換性と混同しないこと。加算では成り立つが、今はこの特性に特に興味がない。抽象化には過度に特化的だ。

そもそも抽象スーパークラスに必要な特性は何か？ 加算固有の特性と一般化可能な特性は？ この階層に他の抽象概念はあるか？ 数学の先人たちが抽象代数のインターフェースを考案した際、まさにこの種の思考が行われた。

歴史を振り返れば、古典的な抽象化論者は加算を抽象化する際に群の概念に到達した。群は負数の概念まで含む完全装備だ。ここで関心があるのは結合的二項演算子のみのため、より一般的なインターフェースであるセミグループを選択する。セミグループは結合的二項演算子として機能するconcatメソッドを持つ型である。

加算用にSumを実装しよう:

const Sum = x => ({
  x,
  concat: other => Sum(x + other.x)
})

他のSumとconcatし、常にSumを返す点に注意。

ここではプロトタイプ儀式ではなくオブジェクト工場を使用した。主にSumがポイント型でなくnew入力不要のため。実際の使用例:

Sum(1).concat(Sum(3)) // Sum(4)
Sum(4).concat(Sum(37)) // Sum(41)

こうして実装ではなくインターフェースに沿ってプログラミングできる。このインターフェースは群論由来のため、数世紀の文献が蓄積されている。無料ドキュメントだ！

前述の通りSumはポイント型でもファンクターでもない。演習として法則を確認されたし。答え: 数値のみ保持可能なためmapは無意味。型変換できないからだ。

これが有用な理由？ インターフェースによりインスタンスを交換して異なる結果を得られる:

const Product = x => ({ x, concat: other => Product(x * other.x) })

const Min = x => ({ x, concat: other => Min(x < other.x ? x : other.x) })

const Max = x => ({ x, concat: other => Max(x > other.x ? x : other.x) })

数値に限定されない。他タイプも見てみよう:

const Any = x => ({ x, concat: other => Any(x || other.x) })
const All = x => ({ x, concat: other => All(x && other.x) })

Any(false).concat(Any(true)) // Any(true)
Any(false).concat(Any(false)) // Any(false)

All(false).concat(All(true)) // All(false)
All(true).concat(All(true)) // All(true)

[1,2].concat([3,4]) // [1,2,3,4]

"miracle grow".concat("n") // miracle grown"

Map({day: 'night'}).concat(Map({white: 'nikes'})) // Map({day: 'night', white: 'nikes'})

これらのパターンはマジックアイのように顕在化する。データ構造の統合、論理の結合、文字列構築...ほぼ全てのタスクをこの結合ベースのインターフェースに押し込める。

マップを複数回使用したが、これはObjectをラップしたもの。元の構造を維持したまま追加メソッドを装備できる。

私のお気に入りファンクターは全てセミグループだ。

従来のファンクター実装型はセミグループも実装している。Identity（旧Container）を見よう:

Identity.prototype.concat = function(other) {
  return new Identity(this.__value.concat(other.__value))
}

Identity.of(Sum(4)).concat(Identity.of(Sum(1))) // Identity(Sum(5))
Identity.of(4).concat(Identity.of(1)) // TypeError: this.__value.concat is not a function

内部値__valueがセミグループである時のみセミグループとなる。持ち主次第で性質が変化する。

他タイプも同様の振る舞い:

// combine with error handling
Right(Sum(2)).concat(Right(Sum(3))) // Right(Sum(5))
Right(Sum(2)).concat(Left('some error')) // Left('some error')


// combine async
Task.of([1,2]).concat(Task.of([3,4])) // Task([1,2,3,4])

セミグループを積層結合する際に特に有用:

// formValues :: Selector -> IO (Map String String)
// validate :: Map String String -> Either Error (Map String String)

formValues('#signup').map(validate).concat(formValues('#terms').map(validate)) // IO(Right(Map({username: 'andre3000', accepted: true})))
formValues('#signup').map(validate).concat(formValues('#terms').map(validate)) // IO(Left('one must accept our totalitarian agreement'))

serverA.get('/friends').concat(serverB.get('/friends')) // Task([friend1, friend2])

// loadSetting :: String -> Task Error (Maybe (Map String Boolean))
loadSetting('email').concat(loadSetting('general')) // Task(Maybe(Map({backgroundColor: true, autoSave: false})))

最初の例ではIOが保持するEither内のマップを結合しフォーム値を検証・結合。次に複数サーバーへアクセスしTaskとArrayで非同期結合。最後にTask、Maybe、マップを積層し設定を読み込み・解析・結合。

chainやapは可能だが、セミグループの方が簡潔に意図を表現できる。

これはファンクターを超えて適用可能。実際、セミグループで構成されるものは全てセミグループになる。部品が結合可能なら全体も結合可能だ。

const Analytics = (clicks, path, idleTime) => ({
  clicks,
  path,
  idleTime,
  concat: other =>
    Analytics(clicks.concat(other.clicks), path.concat(other.path), idleTime.concat(other.idleTime))
})

Analytics(Sum(2), ['/home', '/about'], Right(Max(2000))).concat(Analytics(Sum(1), ['/contact'], Right(Max(1000))))
// Analytics(Sum(3), ['/home', '/about', '/contact'], Right(Max(2000)))

あらゆるものが適切に結合方法を知っている。マップ型を使えば同様の処理が可能:

Map({clicks: Sum(2), path: ['/home', '/about'], idleTime: Right(Max(2000))}).concat(Map({clicks: Sum(1), path: ['/contact'], idleTime: Right(Max(1000))}))
// Map({clicks: Sum(3), path: ['/home', '/about', '/contact'], idleTime: Right(Max(2000))})

任意の数だけ積層結合可能。別の木を森に加えるようなものだ（コードベース次第では山火事にもなる）。

デフォルト挙動は保持値の結合だが、コンテナ自体を結合する例もある。Stream型を考えよう:

const submitStream = Stream.fromEvent('click', $('#submit'))
const enterStream = filter(x => x.key === 'Enter', Stream.fromEvent('keydown', $('#myForm')))

submitStream.concat(enterStream).map(submitForm) // Stream()

イベントストリームを結合して新たなストリームを生成可能。代わりにセミグループ保持を強制することもできる。実際、各型には複数の可能なインスタンスが存在。Taskは実行順序選択で結合可能。エラーを無視するLeftではなく最初のRightを選択できる。代替インターフェースAlternativeも存在し、選択に焦点を当てている。必要に応じて調査すべきだ。

モノイドの無価値性

我々は加算を抽象化していたが、バビロニア人の如くゼロ概念を欠いていた（ゼロ言及無し）。

ゼロは単位元として機能し、どの要素も0を加算すると元の値が返る。抽象的には0を中立/空要素と考える。二項演算の左右で同じ振る舞いが重要:

// identity
1 + 0 = 1
0 + 1 = 1

この概念をemptyと呼び新インターフェースを作成。スタートアップの如く無益だが検索容易な名前モノイドを選択。モノイドのレシピはセミグループに単位元を加えること。型自体にempty関数を実装:

Array.empty = () => []
String.empty = () => ""
Sum.empty = () => Sum(0)
Product.empty = () => Product(1)
Min.empty = () => Min(Infinity)
Max.empty = () => Max(-Infinity)
All.empty = () => All(true)
Any.empty = () => Any(false)

空単位値が有用な場面？ それはゼロの有用性を問うようなものだ...

他に何もない時、頼れるのはゼロ。望ましいバグ数？ゼロ。安全でないコードへの耐性。新たな出発。究極の代償。周囲を壊滅させる力と窮地を救う力を持つ。

コード上では適切なデフォルトに対応:

const settings = (prefix="", overrides=[], total=0) => ...

const settings = (prefix=String.empty(), overrides=Array.empty(), total=Sum.empty()) => ...

他にデータ無し時に有用な値を返す場合:

sum([]) // 0

アキュムレータの初期値として最適...

畳み込み展開

concatとemptyはreduceの最初の2スロットに適合。セミグループ配列をempty値を無視して縮約可能だが危険が伴う:

// concat :: Semigroup s => s -> s -> s
const concat = x => y => x.concat(y)

[Sum(1), Sum(2)].reduce(concat) // Sum(3)

[].reduce(concat) // TypeError: Reduce of empty array with no initial value

空配列の場合ランタイム例外発生。JavaScriptは空配列実行時に容赦なく停止する。正しい型の結果が必要な場合、Maybeで失敗可能性を示すことも可能だが、より良い方法がある。

カリー化されたreduceを使用しempty値を必須にした安全版foldを作成:

// fold :: Monoid m => m -> [m] -> m
const fold = reduce(concat)

初期値mはempty値（中立開始点）。mの配列を1つの値に圧縮。

fold(Sum.empty(), [Sum(1), Sum(2)]) // Sum(3)
fold(Sum.empty(), []) // Sum(0)

fold(Any.empty(), [Any(false), Any(true)]) // Any(true)
fold(Any.empty(), []) // Any(false)


fold(Either.of(Max.empty()), [Right(Max(3)), Right(Max(21)), Right(Max(11))]) // Right(Max(21))
fold(Either.of(Max.empty()), [Right(Max(3)), Left('error retrieving value'), Right(Max(11))]) // Left('error retrieving value')

fold(IO.of([]), ['.link', 'a'].map($)) // IO([<a>, <button class="link"/>, <a>])

最後の2例では手動でempty値を設定。型自体に定義できないため。型付き言語では自動推論可能だが、ここでは明示的に渡す。

非モノイド

empty値（初期値）を提供できないセミグループが存在。初項保持型Firstを参照:

const First = x => ({ x, concat: other => First(x) })

Map({id: First(123), isPaid: Any(true), points: Sum(13)}).concat(Map({id: First(2242), isPaid: Any(false), points: Sum(1)}))
// Map({id: First(123), isPaid: Any(true), points: Sum(14)})

複数アカウントを統合しFirstIDを保持。empty値を定義不能。有用性は失わない。

大統一理論

群論か圏論か？

二項演算の概念は抽象代数に遍在。実は圏の主要演算。ただし単位元無しでは圏論でモデル化不能。これが圏論でモノイドを扱う際にセミグループから始める理由である。

モノイドは射をconcat、単位元をemptyとし、合成が保証された単一対象圏を形成。

モノイドとしての合成

ドメインとコドメインが同一のa -> a型関数は自己準同型。これを捕捉するEndoモノイド:

const Endo = run => ({
  run,
  concat: other =>
    Endo(compose(run, other.run))
})

Endo.empty = () => Endo(identity)


// in action

// thingDownFlipAndReverse :: Endo [String] -> [String]
const thingDownFlipAndReverse = fold(Endo(() => []), [Endo(reverse), Endo(sort), Endo(append('thing down')])

thingDownFlipAndReverse.run(['let me work it', 'is it worth it?'])
// ['thing down', 'let me work it', 'is it worth it?']

同一型のためcomposeでconcat可能。型は常に整合。

モナドとしてのモノイド

joinが二重モナドを結合する結合的な操作であることに気付くだろう。これは自然変換でもある。自己関手に特化すると、joinはモノイド（圏論ではモナド）を形成。詳細は検索を推奨するが、基本的な考え方はこの通り。

Applicativeのモノイド的定式化

アプリカティブファンクターも緩いモノイド関手としてモノイド的定式化可能。apを復元できる:

// concat :: f a -> f b -> f [a, b]
// empty :: () -> f ()

// ap :: Functor f => f (a -> b) -> f a -> f b
const ap = compose(map(([f, x]) => f(x)), concat)

要約

このように、万物は繋がっている。モノイドはアプリケーションアーキテクチャからデータ断片まで強力なモデリングツールだ。蓄積・結合が必要な場面でモノイドを想起し、定義を拡張することを推奨する（驚くほど多くの事象をモデル化可能）。

演習問題