オブジェクト指向の背景から来た人にとって、関数型プログラミングを学ぶ上で最も難しい点の1つは、明確なデザインパターンが見当たらないことです。 部分適用やエラー処理テクニックなどのイディオムは多くありますが、GoF的な意味での明らかなパターンはありません。

この記事では、モノイドと呼ばれる非常に一般的な「パターン」を見ていきます。モノイドは、厳密にはデザインパターンではありません。むしろ、様々な種類の値を共通の方法で扱うためのアプローチと言えます。 実際、モノイドを理解すると、モノイドがあらゆるところに潜んでいることに気づくようになります。

残念ながら、「モノイド」という用語自体は少し敬遠されがちです。もともとは数学に由来していますが、 プログラミングに適用される概念は、これから示すように、数学をまったく使わずに理解するのは簡単です。実際、今日のプログラミングの文脈でこの概念に名前をつけるとしたら、 ICombinableのような、それほど怖くない名前になっていたかもしれません。

最後に、「モノイド」と「モナド」に何か関連があるのかと疑問に思うかもしれません。確かに、数学的にはつながりがありますが、プログラミングの観点では、似た名前にもかかわらず、非常に異なるものです。

ああ...方程式が出てきた

このサイトでは、一般的に数学を使いませんが、今回は自分で課したルールを破って、いくつかの方程式をお見せします。

準備はいいですか？これが1つ目です：

1 + 2 = 3

これは大丈夫でしたか？もう1つどうでしょう：

1 + (2 + 3) = (1 + 2) + 3

そして最後にもう1つ...

1 + 0 = 1 そして 0 + 1 = 1

はい、終わりです！これらの方程式を理解できれば、モノイドを理解するのに必要な数学はすべて持っていることになります。

数学者のように考える

「数学者は、画家や詩人と同じように、パターンの作り手です。彼らのパターンがより永続的であるとすれば、それはアイデアで作られているからです」 -- G H ハーディ

多くの人は、数学者が数字を扱い、複雑な計算や微積分を行うと想像しています。

これは誤解です。たとえば、典型的な高度な数学の議論を見ると、 奇妙な言葉や文字、記号はたくさん見かけますが、計算はあまり見かけません。

しかし、数学者が実際に行っていることの1つは、物事のパターンを見つけようとすることです。「これらの物事に共通点は何か？」「これらの概念をどのように一般化できるか？」といった問いは、数学的な疑問の典型例です。

では、数学者の目を通して、これら3つの方程式を見てみましょう。

最初の方程式の一般化

数学者は 1 + 2 = 3 を見て、次のように考えるでしょう：

• 一群のもの（この場合は整数）がある
• それらを2つずつ組み合わせる方法（この場合は加算）がある
• そして結果はこれらのものの1つになる（つまり、別の整数が得られる）

そして数学者は、このパターンを他の種類のものや操作に一般化できないかと考えるかもしれません。

まずは、「もの」として整数を維持しましょう。整数を組み合わせる他の方法にはどのようなものがあるでしょうか？そしてそれらはこのパターンに当てはまるでしょうか？

乗算を試してみましょう。これはパターンに当てはまるでしょうか？

答えはイエスです。2つの整数を掛け合わせた結果は別の整数になるので、乗算はこのパターンに当てはまります。

除算はどうでしょうか？これはパターンに当てはまるでしょうか？答えはノーです。なぜなら、ほとんどの場合、2つの整数を割ると分数になり、整数ではありません（整数除算は無視します）。

max関数はどうでしょうか？これはパターンに当てはまるでしょうか？2つの整数を組み合わせてそのうちの1つを返すので、答えはイエスです。

equals関数はどうでしょうか？2つの整数を組み合わせますが、ブール値を返すので整数ではありません。したがって答えはノーです。

整数はもう十分です！他にどんな種類のものを考えられるでしょうか？

浮動小数点数は整数に似ていますが、整数とは異なり、浮動小数点数での除算は別の浮動小数点数になるので、除算操作はパターンに当てはまります。

ブール値はどうでしょうか？ANDやORなどの演算子で組み合わせることができます。aBool AND aBoolは別のブール値になりますか？はい！そしてORもパターンに当てはまります。

次は文字列です。どのように組み合わせられるでしょうか？1つの方法は文字列の連結で、これは別の文字列を返すのでパターンに当てはまります。しかし、等価性操作のようなものはブール値を返すのでパターンに当てはまりません。

最後にリストを考えてみましょう。文字列と同様に、明らかな組み合わせ方法はリストの連結で、これは別のリストを返すのでパターンに当てはまります。

このように、さまざまなオブジェクトと組み合わせ操作について続けることができますが、どのように機能するかはもうわかったでしょう。

操作が同じ型の別のものを返すことがなぜそんなに重要なのかと疑問に思うかもしれません。答えは、操作を使って複数のオブジェクトを連鎖的に組み合わせることができるからです。

たとえば、1 + 2は別の整数なので、それに3を足すことができます。そして1 + 2 + 3も整数なので、続けてたとえば4を足すことができます。 つまり、整数の加算がこのパターンに当てはまるからこそ、1 + 2 + 3 + 4のような一連の加算を書くことができるのです。同じように1 = 2 = 3 = 4とは書けません。 なぜなら、整数の等価性はこのパターンに当てはまらないからです。

もちろん、組み合わされた項目の連鎖は好きなだけ長くすることができます。言い換えれば、このパターンによって、ペアワイズ操作をリストに対する操作に拡張することができます。

数学者は、「結果が別のこれらのもの1つになる」という要件を閉包要件と呼びます。

2つ目の方程式の一般化

さて、次の方程式 1 + (2 + 3) = (1 + 2) + 3 はどうでしょうか？なぜこれが重要なのでしょうか？

最初のパターンを考えると、1 + 2 + 3のような操作の連鎖を構築できると言っています。しかし、ペアワイズ操作しか持っていません。では、どの順序で組み合わせるべきでしょうか？まず1と2を組み合わせて、 その結果を3と組み合わせるべきでしょうか？それとも、まず2と3を組み合わせて、その結果を1と組み合わせるべきでしょうか？違いはあるのでしょうか？

ここで2つ目の方程式が役立ちます。加算の場合、組み合わせの順序は関係ないと言っています。どちらの方法でも同じ結果が得られます。

したがって、1 + 2 + 3 + 4のような4つの項目の連鎖の場合、左側から始めることもできます：((1+2) + 3) + 4、右側から始めることもできます：1 + (2 + (3+4))、 あるいは2つの部分に分けて組み合わせることもできます：(1+2) + (3+4)。

これまで見てきた例にこのパターンが当てはまるかどうか見てみましょう。

再び、整数を組み合わせる他の方法から始めましょう。

まず乗算から始めます。1 * (2 * 3)は(1 * 2) * 3と同じ結果になりますか？はい。加算と同様に、順序は関係ありません。

次に減算を試してみましょう。1 - (2 - 3)は(1 - 2) - 3と同じ結果になりますか？いいえ。減算の場合、順序が重要です。

除算はどうでしょうか？12 / (2 / 3)は(12 / 2) / 3と同じ結果になりますか？いいえ。除算の場合も順序が重要です。

しかし、max関数は機能します。max(max(12,2), 3)はmax(12, max(2,3))と同じ結果になります。

文字列やリストはどうでしょうか？連結はこの要件を満たしますか？どう思いますか？

ここで質問です... 文字列に対して、順序に依存する操作を考え出せますか？

たとえば、「subtractChars」のような関数はどうでしょうか。これは左の文字列から右の文字列にあるすべての文字を取り除きます。つまり、subtractChars("abc","ab")は単に"c"になります。 subtractCharsは確かに順序に依存します。簡単な例で確認できます：subtractChars("abc", subtractChars("abc","abc"))はsubtractChars(subtractChars("abc","abc"),"abc")と同じ文字列にはなりません。

数学者は「順序が関係ない」という要件を結合法則と呼びます。

重要な注意： 「組み合わせの順序」と言うとき、ペアワイズの組み合わせステップを行う順序について話しています - 1つのペアを組み合わせ、その結果を次の項目と組み合わせます。

しかし、項目の全体的な順序を変更しないことが重要です。なぜなら、特定の操作では、項目の順序を変更すると まったく異なる結果になるからです！1 - 2は2 - 1と同じ意味ではありませんし、2 / 3は3 / 2と同じ意味ではありません。

もちろん、多くの一般的なケースでは、順序は関係ありません。結局のところ、1+2は2+1と同じです。この場合、操作は可換であると言います。

3つ目の方程式

では、3つ目の方程式 1 + 0 = 1 を見てみましょう。

数学者はこう言うでしょう：面白い - 特別な種類のもの（「ゼロ」）があって、それを何かと組み合わせると、 まるで何も起こらなかったかのように元のものがそのまま返ってくる。

そこで、もう一度例を振り返り、この「ゼロ」の概念を他の操作や他のものに拡張できるかどうか見てみましょう。

再び、乗算から始めましょう。ある値があって、それを数と掛け合わせると元の数が返ってくるようなものはあるでしょうか？

ええ、もちろんあります！数字の1です。つまり、乗算の場合、数字「1」が「ゼロ」になります。

maxはどうでしょうか？「ゼロ」はありますか？32ビット整数の場合、はい。System.Int32.MinValueを他の任意の32ビット整数とmaxを使って組み合わせると、他の整数が返されます。 これは「ゼロ」の定義に完全に当てはまります。

ANDを使って組み合わせるブール値はどうでしょうか？これに「ゼロ」はありますか？はい。値Trueです。なぜなら、True AND FalseはFalseで、True AND TrueはTrueだからです。どちらの場合も他の値がそのまま返されます。

ORを使って組み合わせるブール値にも「ゼロ」はありますか？答えはあなたに委ねます。

次に、文字列の連結はどうでしょうか？これに「ゼロ」はありますか？ええ、確かにあります - 空の文字列です。

"" + "hello" = "hello"
"hello" + "" = "hello"

最後に、リストの連結の場合、「ゼロ」は空のリストです。

[] @ [1;2;3] = [1;2;3]
[1;2;3] @ [] = [1;2;3]

「ゼロ」の値は、ものの集合だけでなく、操作にも大きく依存することがわかります。整数加算の「ゼロ」は整数乗算の「ゼロ」とは異なり、 それはさらにMaxの「ゼロ」とも異なります。

数学者は「ゼロ」を単位元と呼びます。

方程式の再考

では、新しい一般化を念頭に置いて、方程式を再考してみましょう。

以前は次のようでした：

1 + 2 = 3
1 + (2 + 3) = (1 + 2) + 3
1 + 0 = 1 そして 0 + 1 = 1

しかし今では、あらゆる種類のものに適用できる、はるかに抽象的な一連の一般化された要件があります：

• あなたは一群のものと、それらを2つずつ組み合わせる方法から始めます。
• 規則1（閉包）：2つのものを組み合わせた結果は、常にそれらのものの1つになります。
• 規則2（結合法則）：2つ以上のものを組み合わせる場合、どのペアワイズの組み合わせを最初に行うかは関係ありません。
• 規則3（単位元）：「ゼロ」と呼ばれる特別なものがあり、任意のものと「ゼロ」を組み合わせると元のものが返されます。

これらの規則が整えば、モノイドの定義に戻ることができます。「モノイド」とは単に、これら3つの規則すべてに従う仕組みのことです。簡単でしょう！

冒頭で述べたように、数学的背景に気後れしないでください。プログラマーがこのパターンに名前をつけていたら、おそらく「モノイド」ではなく「組み合わせ可能パターン」のような名前になっていたでしょう。 しかし、それが現実です。用語はすでに確立されているので、使わざるを得ません。

モノイドの定義には2つの部分があることに注意してください - ものと、それに関連する操作です。 モノイドは単に「一群のもの」ではなく、「一群のもの」と「それらを組み合わせる方法」です。 したがって、たとえば「整数」はモノイドではありませんが、「加算下の整数」はモノイドです。

半群

場合によっては、最初の2つの規則にのみ従う仕組みがあり、「ゼロ」の候補がないことがあります。

たとえば、ドメインが厳密に正の数のみで構成される場合、加算の下で閉じていて結合的ですが、「ゼロ」になる正の数はありません。

別の例として、有限リストの交差があります。これは閉じていて結合的ですが、他の任意の有限リストと交差させたときにそのリストをそのまま残す（有限の）リストはありません。

この種の仕組みはまだかなり有用で、数学者によって「半群」と呼ばれます。モノイドではありません。 幸いなことに、任意の半群をモノイドに変換するトリックがあります（後で説明します）。

分類の表

これまでの例をすべて表にまとめてみましょう。

このリストに追加できる他の種類のものがたくさんあります。多項式、行列、確率分布などです。 この投稿ではそれらについて議論しませんが、モノイドの考え方を理解すれば、この概念をあらゆる種類のものに適用できることがわかるでしょう。

[注1] Dougがコメントで指摘しているように、浮動小数点数は結合的ではありません。 結合性を得るには、'float'を'実数'に置き換えてください。

[注2] 数学的な実数は除算の下で閉じていません。なぜなら、0で割って別の実数を得ることはできないからです。しかし、IEEE浮動小数点数では 0で割ることができ、有効な値を得ることができます。 したがって、浮動小数点数は確かに除算の下で閉じています！ここに示します：

let x = 1.0/0.0 // 無限大
let y = x * 2.0 // 無限大の2倍 
let z = 2.0 / x // 2を無限大で割る

プログラマーにとってモノイドはどのような用途があるか？

ここまで、いくつかの抽象的な概念を説明してきましたが、実世界のプログラミングの問題にどのような有用性があるのでしょうか？

閉包の利点

見てきたように、閉包規則には、ペアワイズ操作をリストや配列に対する操作に変換できるという利点があります。

言い換えれば、ペアワイズ操作を定義できれば、それをリスト操作に「無料で」拡張できます。

この機能を実行する関数は通常「reduce」と呼ばれます。いくつか例を挙げましょう：

reduceは指定された操作をリストの各要素の間に挿入すると考えることができます。

最後の例で、reduceへの入力がリストのリストで、出力が単一のリストであることに注意してください。なぜそうなるのか理解していることを確認してください。

結合性の利点

ペアワイズの組み合わせを任意の順序で行うことができれば、次のような興味深い実装テクニックが可能になります：

• 分割統治アルゴリズム
• 並列化
• 増分性

これらは深いトピックですが、簡単に見てみましょう！

分割統治アルゴリズム

最初の8つの整数の合計を求める課題を考えてみましょう。これをどのように実装できるでしょうか？

1つの方法は、次のような単純な段階的な合計です：

let sumUpTo2 = 1 + 2
let sumUpTo3 = sumUpTo2 + 3
let sumUpTo4 = sumUpTo3 + 4
// 以下同様
let result = sumUpTo7 + 8

しかし、合計を任意の順序で行えるため、要件を次のように2つの半分に分割して実装することもできます：

let sum1To4 = 1 + 2 + 3 + 4
let sum5To8 = 5 + 6 + 7 + 8
let result = sum1To4 + sum5To8

そして、基本的なペアワイズ操作に到達するまで、同じ方法で合計を再帰的に部分合計に分割できます：

let sum1To2 = 1 + 2 
let sum3To4 = 3 + 4
let sum1To4 = sum1To2 + sum3To4

この「分割統治」アプローチは、単純な合計のような場合には大げさに見えるかもしれませんが、後の投稿で、mapと組み合わせることで、よく知られているいくつかの集約アルゴリズムの基礎になることを見ていきます。

並列化

分割統治戦略を持っていれば、それを簡単に並列アルゴリズムに変換できます。

たとえば、4コアのCPUで最初の8つの整数の合計を求めるには、次のようなことができるかもしれません：

まだ7つの計算を行う必要がありますが、並列で行うことで3つのステップで実行できます。

これも些細な例に見えるかもしれませんが、Hadoopのようなビッグデータシステムは大量のデータを集約することが全てで、 集約操作がモノイドであれば、理論的には、複数のマシンを使用してこれらの集約を簡単にスケールアップできます*。

*_{実際には、もちろん悪魔は細部に宿り、現実世界のシステムはこのように正確に動作しません。}

増分性

並列処理が必要ない場合でも、モノイドの素晴らしい特性として、増分計算をサポートすることが挙げられます。

たとえば、1から5までの合計を計算するよう頼まれたとしましょう。もちろん、答えは15を返します。

しかし、その後、考えが変わって1から6までの合計が欲しいと言われたとします。最初からやり直して全ての数を足し合わせる必要があるでしょうか？ いいえ、前回の合計を使って、6を増分的に加えることができます。これが可能なのは、整数の加算がモノイドだからです。

つまり、1 + 2 + 3 + 4 + 5 + 6のような合計に直面したとき、好きなように数をグループ化できます。 特に、(1 + 2 + 3 + 4 + 5) + 6のような増分的な合計にすることができ、これは15 + 6に簡略化されます。

この場合、最初から全ての合計をやり直すのはそれほど大変ではないかもしれませんが、たとえばウェブアナリティクスのような現実世界の例を考えてみてください。過去30日間の訪問者数を数えるとします。 素朴な実装では、過去30日分のデータのログを解析して数を計算するかもしれません。より効率的なアプローチは、前の29日分は変わっていないことを認識し、 1日分の増分変更のみを処理することです。その結果、解析の労力が大幅に削減されます。

同様に、100ページの本の単語数を数えていて、1ページ追加した場合、101ページすべてを再度解析する必要はありません。最後のページの単語を数えて、それを前の合計に加えるだけで済みます*。

• _{技術的には、これらは恐ろしげなモノイド準同型と呼ばれるものです。次の投稿で説明します。}

単位元の利点

単位元を持つことが常に必要というわけではありません。閉じていて結合的な操作（つまり半群）を持つことで、多くの有用なことができます。

しかし、場合によっては十分ではありません。たとえば、次のようなケースが出てくるかもしれません：

• 空のリストに対してreduceをどのように使用できるか？
• 分割統治アルゴリズムを設計する際、「分割」ステップの1つが何もない場合はどうすべきか？
• 増分アルゴリズムを使用する際、データがない状態から始める場合、どの値から始めるべきか？

全てのケースで「ゼロ」値が必要です。これにより、たとえば空のリストの合計は0であると言えます。

上記の最初の点に関して、リストが空である可能性がある場合は、reduceをfoldに置き換える必要があります。foldは初期値を渡すことができます。 （もちろん、foldはモノイド操作以外にも使用できます。）

以下にreduceとfoldの動作例を示します：

// OK
[1..10] |> List.reduce (+)

// エラー
[] |> List.reduce (+)  

// 明示的なゼロでOK
[1..10] |> List.fold (+) 0 

// 明示的なゼロでOK
[] |> List.fold (+) 0

「ゼロ」を使用すると、時々直感に反する結果になることがあります。たとえば、空の整数リストの積は何でしょうか？

答えは、予想されるかもしれない0ではなく、1です！以下のコードで証明できます：

[1..4] |> List.fold (*) 1  // 結果は24
[] |> List.fold (*) 1      // 結果は1

利点のまとめ

要約すると、モノイドは基本的に集約パターンを記述する方法です - ものののリストがあり、それらを組み合わせる方法があり、最後に単一の集約されたオブジェクトが返されます。

あるいはF#の用語で言えば：

モノイド集約 : 'T list -> 'T

したがって、コードを設計する際に、「合計」、「積」、「構成」、または「連結」などの用語を使用し始めたら、モノイドを扱っている可能性があるというヒントです。

次のステップ

モノイドが何であるかを理解したので、実際にどのように使用できるか見てみましょう。

このシリーズの次の投稿では、モノイド「パターン」を実装する実際のコードをどのように書くかを見ていきます。