数学的な知識をほぼ必要とせずに一般的な関数パターンを説明する
もしも読者にOOのバックグラウンドがあるのであれば、 関数型言語を学習するにあたって問題となるのは 関数型言語にはこれといった明確なデザインパターンが存在しないことでしょう。 部分適用 だとか エラー処理のテクニック ( 拙訳 )といったものはありますが、 GoF的な 明確なパターンは存在しません。
この記事では モノイド と呼ばれる非常に一般的な「パターン」について説明します。 モノイドは厳密にはデザインパターンではありません。 どちらかというと、多数の様々な型を持った値を共通の方法で処理するための方法だと言えます。 実際、モノイドを理解した後になればあちこちで使われていることに気がつくようになるでしょう！
残念なことに「モノイド」という単語自体は少し紛らわしいものです。
元々は 数学 用語なのですが、プログラミングにこの概念を応用する場合には
数学の知識無しでも簡単に理解できるはずです。
それがこの記事の目的とするところであるわけですが。
実際、プログラミングの分野から見て名前をつけ直すことができるのであれば、
ICombinable とでも呼ばれていたかもしれません。
これならそれほど怖くないでしょう。
最後に、「モノイド」は「モナド」と何か関連が有るのでは無いかと思うかもしれません。 その通り、両者には数学的な関連性があります。 しかしよく似た名前ではありますが、プログラミング用語的にはそれぞれ非常に異なるものです。
このサイトでは基本的に数学を必要としないようにしているのですが、 今回はその自分で決めたルールを破っていくつか等式を紹介します。
用意はいいですか？ まず1つ目です：
1 + 2 = 3まだ大丈夫？ 次はどうです？
1 + (2 + 3) = (1 + 2) + 3最後にもう1つ...
1 + 0 = 1 かつ 0 + 1 = 1以上！ これらの等式が理解できたのであればモノイドを理解するための数学的な知識は十分です。
「数学者は画家や詩人のようにパターンを作り出すものである。 数学者によるパターンが他よりも永続的なものだとすれば、 それはパターンに数学者達の知識が詰め込まれているからだ。」G H Hardy
たいていの人は数学者といえば数字を扱ったり、複雑な数式や計算ばかりを 相手にしているものだと想像することでしょう。
しかし実際はそうではありません。 たとえば 典型的なレベルの高い 数学に関する議論 を見てみると 奇妙な単語や文字、シンボルがたくさん現れるものの、数式はほとんど見かけません。
数学者の仕事の1つは、あるものに対するパターンを見つけ出そうとすることです。 一般的な数学の問題とは「これらに共通するものは何だ？」とか 「これらの概念をどうすれば一般化できるだろうか？」とかいうものです。
では先ほどの等式を数学者の視点で見てみることにしましょう。
数学者は 1 + 2 = 3 という等式を目にすると以下のようなことを考えます：
- いくつかの要素がある（この場合は整数）
- それら2つを何らかの方法で連結している（この場合は加算）
- そしてそれらとは別に結果がある（2つとは別の整数）
そして数学者は別のものや演算子を使用してこのパターンを一般化出来ないだろうかと考えます。
ではまず整数を「何か」にするところから始めましょう。 整数を連結する別の方法があるでしょうか？ そしてそれは今回のパターンに一致するでしょうか？
まずかけ算から検討してみましょう。 パターンに一致しますか？
答えはYesです。 かけ算もやはり2つの整数を掛け合わせると別の整数値が結果になります。
割り算はどうでしょう？ パターンに一致しますか？ 答えはNoです。 ほとんどの場合、割り算の結果は小数であり、整数にはなりません （そのため整数値の割り算については無視します）。
max 関数はどうでしょうか？
パターンに一致しますか？
この関数は2つの整数を受け取ってそれらのうちの1つを返すわけなので、答えはYesです。
equals 関数はどうでしょうか？
この関数は2つの整数を受け取りますが、結果が整数ではなくブール値です。
したがって答えはNoです。
整数についてはこれで十分です！ 他にどんなものが考えられるでしょうか？
浮動小数は整数によく似ていますが、整数と異なり浮動小数の割り算の結果は 別の浮動小数になるため、パターンに一致します。
ブール値はどうでしょうか？
ブール値はANDやORのような演算子で連結できます。
aBool AND aBool の結果は別のブール値でしょうか？
そうです！
また OR でも同じです。
次は文字列です。 どうやって連結できるでしょうか？ 1つの方法としては文字列連結することです。 これであれば別の文字列が結果になるためパターンに一致します。 ただし等式演算子など、結果がブール値になるものについては一致しません。
最後にリストを考えてみましょう。 文字列と同じく、リストはリスト同士を連結させることが出来、 別のリストが返されるわけなのでパターンに一致します。
こういった検討をすべてのオブジェクトと演算子の組み合わせに対して検討していくことができますが、 今はこれがどのように機能するのか見ていくことにします。
「演算子が同じ型の別のものを返すことがどうしてそれほど重要なのだろう？」 と疑問に思うかもしれません。 こういった演算子を使用すれば複数のオブジェクトを 演算子でつなぎ合わせることができるから、というのがその答えです。
たとえば1 + 2は別の整数を返すので、そこへさらに3を足すことができます。
そうすると1 + 2 + 3も整数を返すので、この結果に4を足すことができます。
別の言い方をすると、パターンに一致する整数の加算を使用すれば
1 + 2 + 3 + 4のように加算のシーケンスを記述できるというわけです。
整数の等式演算子はパターンに一致しないため、1 = 2 = 3= 4というようには記述できません。
もちろん、項目の連結のチェーンは任意個並べることができます。 つまりこのパターンを使用すれば、二項演算子を拡張して、 リストに対しても機能するような演算子にできるというわけです。
このように、「結果がそれぞれとは異なるもの」になるべきだという条件は、 数学的には クロージャ (closure)条件と呼ばれています。
さて次の1 + (2 + 3) = (1 + 2) + 3という等式はどうでしょう？
何故これが重要なのでしょう？
1番目のパターンを検討した際、1 + 2 + 3というような演算子のチェーンを
作れるという説明をしました。
しかしそれは二項演算子に限定された話でした。
ではどういう順番で演算子を組み合わせたらよいのでしょう？
まず1と2を組み合わせてから、その結果と3を組み合わせる？
それとも2と3を組み合わせてから、1とその結果を組み合わせる？
これらは違う話なのでしょうか？
ここで2番目の等式が重要な意味をもってきます。 この等式からわかることは足し算であれば組み合わせる順序を気にする必要がないということです。 どの順序でも同じ結果が得られます。
つまり1 + 2 + 3 + 4のような式があるとして、
((1+2) + 3) + 4のように左側から計算しても、
1 + (2 + (3+4))のように右側から計算しても、
(1+2) + (3+4)のように2組の足し算を足してもよいわけです。
このパターンが既に検討してきた他の例に適用できるかどうかチェックしてみましょう。
まずは再び整数を組み合わせる場合を検討してみます。
再度かけ算から見てみましょう。
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)) の結果は同じです。
文字列やリストはどうでしょう？ これらの連結機能はパターンに一致しますか？ どう思います？
ここで問題です。 果たして順序に依存するような文字列用の演算子を思いつけますか？
たとえば右側の文字列から左側の文字列をすべて取り除くような関数
removeAll はどうでしょう？
つまり subtractChars("ab", "abc") が "c" になるような関数です。
subtractChars("abc", subtractChars("abc", "abc")) の結果と
subtractChars(subtractChars("abc", "abc"), "abc") の結果が異なるように、
subtractChars は順序に依存することがわかります。
このように「順序に依存しない」という条件は 数学的には 結合性 (associativity) 条件と呼ばれます。
重要な補足として、 以降で「連結の順序」という用語を使った場合には 対をなしている複数の連結処理、つまり1対を連結した後、 連結した結果と次の項目を連結するという処理の順序のことを指します。
ただし一連の項目の順序は変更されないものとします。
もしある特定の演算子に対して一連の項目の順序を変更してしまうと
得られる結果は全く違うものになります！
1 - 2 の結果は 2 - 1 とは違いますし、
2 / 3 の結果は 3 / 2 とは違います。
当然ながらたいていの場合には項目の順序は重要ではありません。
1+2 の結果は 2+1 と同じです。
このような演算子は 可換 (commutative)であるといいます。
次は3番目の 1 + 0 = 1 という等式を見ていきましょう。
数学者ならばきっと興味深いと言うでしょう。 この特別なもの(「ゼロ」)に別のものを連結するとあたかも何も起こらなかったかのように 元のものが返されるというわけです。
そこでもう一度、この「ゼロ」という概念がその他の演算子やその他のものについて 成り立つかどうか確認してみることにしましょう。
まずはかけ算です。 数値を掛け合わせると元々の数値が返されるような値があるでしょうか？
もちろんあります！ 1です。 つまりかけ算の場合は数字1が「ゼロ」です。
max の場合はどうでしょうか？
「ゼロ」がありますか？
32ビット整数の場合はYesです。
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 の「ゼロ」もまた別の値です。
この「ゼロ」を数学的には 単位元 (identity element) と呼びます。
さてでは新しく習得した汎用化の観点で等式を再確認してみましょう。
以前の等式はこうでした：
1 + 2 = 3
1 + (2 + 3) = (1 + 2) + 3
1 + 0 = 1 かつ 0 + 1 = 1しかし今ならこれらをさらに抽象化して以下のように一般化することができます：
- 一連のものがあって、これらのうち2つを一度に連結するような方法がある
- 規則1 (クロージャ)：2つのものを連結した結果は常に別のものになる
- 規則2 (結合性)：2つ以上のものを連結する場合、最初に連結する対はどれでも構わない
- 規則3 (単位元)：別のものと連結しても常に別のものが返されるような「ゼロ」と呼ばれる特別なものがある
これらのルールが整ったので、モノイドの定義に振り返りましょう。 「モノイド」とは単にこれら3つの規則を満たすシステムです。 単純です！
最初に宣言した通り、数学的な背景を準備しておく必要はありません。 プログラマがこのパターンに名前をつけたとしたら、「モノイド」というよりは 「連結可能パターン」と呼んだことでしょう。 しかし世の中そんなものです。 既に専門用語として広く出回ってしまっているわけなので、 「モノイド」と呼ばざるを得ないわけです。
モノイドの定義にはものとそれに関連する演算子という 2つの要素がある点に注意してください。 モノイドは単に「ものの集まり」というわけではなく、「ものの集まり」 かつ 「それらを連結するいくつかの方法」が組み合わさったものです。 したがって、たとえば「整数の集合」はモノイドではありませんが、 「足し算における整数の集合」はモノイドです。
場合によっては最初の2つの規則しか満たさず、 「ゼロ」値に該当するものがないことがあります。
たとえば厳密に正の値の数だけを加算することを考える場合、 これらはクロージャと結合性の規則を満たしますが、 「ゼロ」に該当するものがありません。
さらに別の例として、有限のリストに対する共通集合もそうです。 クロージャと結合性の規則を満たしますが、 別の有限リストとの共通集合が元の有限リストのままになるような (有限の)リストはありません。
これらの性質を持ったシステムもやはり有用で、数学的には「半群」と呼ばれています。 幸いにして、半群をモノイドに変換するようなトリックが存在することが知られています (後ほど説明します)。
これまでの例を表にして、全体を俯瞰できるようにしましょう。
| もの | 演算子 | クロージャ？ | 結合性？ | 単位元？ | クラス分け |
|---|---|---|---|---|---|
| Int32 | 足し算 | Yes | Yes | 0 | モノイド |
| Int32 | かけ算 | Yes | Yes | 1 | モノイド |
| Int32 | 引き算 | Yes | No | 0 | その他 |
| Int32 | Max | Yes | Yes | Int32.MinValue | モノイド |
| Int32 | 等式 | No | その他 | ||
| Int32 | より少ない | No | その他 | ||
| Float | かけ算 | Yes | No ( ** ) | 1 | モノイド |
| Float | 割り算 | Yes | No | 1 | その他 |
| 正の整数 | 足し算 | Yes | Yes | なし | 半群 |
| 正の整数 | かけ算 | Yes | Yes | 1 | モノイド |
| ブール値 | AND | Yes | Yes | true | モノイド |
| ブール値 | OR | Yes | Yes | false | モノイド |
| 文字列 | 連結 | Yes | Yes | 空文字列 "" | モノイド |
| 文字列 | 等号 | No | その他 | ||
| 文字列 | "subtractChars" | Yes | No | 空文字列 "" | その他 |
| リスト | 連結 | Yes | Yes | 空のリスト [] | モノイド |
| リスト | 共通集合 | Yes | Yes | なし | 半群 |
** コメントで指摘のあった通り、Floatには結合性がありません。Floatではなく実数であれば結合性があります。
たとえば多項式や行列、確率分布など、他にも様々な種類のものを このリストに追加することができます。 この記事ではそれらについて言及しませんが、 モノイドの概念が理解出来てしまえばあらゆる種類のものに モノイドの概念を適用することができることがわかるでしょう。
これまでは抽象的な概念についての説明でした。 では現実世界におけるプログラミングの問題に対してこれらがどのように役立つのでしょう？
既に見てきたように、クロージャ規則には複数の二項演算子を リストやシーケンスに対しても機能するような演算子へと変換できるという利点があります。
別の言い方をすると、二項演算子が定義できればそれを 「そのまま」リスト演算子へと変換できるということです。
このような処理を行う関数は「reduce」と呼ばれます。 以下の例を参照してください。
| 明示的な式 | reduceを使用した場合 |
|---|---|
1 + 2 + 3 + 4 |
[ 1; 2; 3; 4 ] |> List.reduce (+) |
1 * 2 * 3 * 4 |
[ 1; 2; 3; 4 ] |> List.reduce (*) |
"a" + "b" + "c" + "d" |
[ "a"; "b"; "c"; "d" ] |> List.reduce (+) |
[1] @ [2] @ [3] @ [4] |
[ [1]; [2]; [3]; [4] ] |> List.reduce (@) |
このように、 reduce を使用するとリスト内の各要素の間に
指定した演算子を挟み込むことができることがわかります。
なお最後の例では reduce の入力としてリストのリストを指定していますが、
結果は1つのリストになります。
その理由については別途確認しておいてください。
二項の連結が任意の順序で行える場合、以下のような興味深いテクニックが利用できるようになります：
- 分割統治アルゴリズム
- 並列化
- インクリメンタリズム
それぞれ複雑な話ですが、大まかなところだけ見ていきましょう！
たとえば1から8までの整数に対する総和を計算したいとします。 これをどうやって実装しますか？
一つは次のようにステップバイステップで和を求める大雑把な方法です：
let sumUpTo2 = 1 + 2
let sumUpTo3 = sumUpTo2 + 3
let sumUpTo4 = sumUpTo3 + 3
// etc
let result = sumUpTo7 + 8しかし足し算は順不同で計算できるわけなので、以下のように半分ずつ計算することもできます：
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 による結合のように、
有名な集計アルゴリズムの基礎になっています。
分割統治アルゴリズムが分かってしまえばそれを並列アルゴリズムに簡単に応用できます。
たとえば1から8までを4コアのCPUで足しあわせる場合、以下のようにします：
| コア1 | コア2 | コア3 | コア4 | |
|---|---|---|---|---|
| ステップ1 | sum12 = 1 + 2 |
sum34 = 3 + 4 |
sum56 = 5 + 6 |
sum78 = 7 + 8 |
| ステップ2 | sum1234 = sum12 + sum34 |
sum5678 = sum56 + sum78 |
(アイドル) | (アイドル) |
| ステップ3 | sum1234 + sum5678 |
(アイドル) | (アイドル) | (アイドル) |
最終結果を得るまでにはやはり7回の計算が必要ですが、 一部の計算を並列実行しているため、3ステップで処理が終了できます。
繰り返しますが、この例もかなりわかりやすいものです。 しかしHadoopのように非常に大量のデータを集計するようなビッグデータシステムでは 集計処理がモノイドであれば論理的には処理を複数のマシンに簡単に分散することができます。 *
* もちろん現実的には細部に悪魔が潜んでいるため、 実世界のシステムを同じ方法で拡張することはできません。
並列化が不要だったとしても、モノイドの素晴らしい性質によって インクリメンタル計算ができるようになります。
たとえば1から5までの和を計算するとします。 当然答えは15です。
しかし気が変わって、代わりに1から6まで計算したくなったとします。 そうするとまた最初からすべて計算し直さなければいけないのでしょうか？ いいえ、直前までの和を使って、単にそこへ6を追加するだけで済みます。 これは整数の足し算がモノイドであるからこそ可能な処理です。
つまり 1 + 2 + 3 + 4 + 5 + 6 という計算をするときには
任意個のグループに分けて計算することができるわけです。
具体的には (1 + 2 + 3 + 4 + 5) + 6 とグループに分けて、
15 + 6 と縮尺できます。
今回の場合には最初から計算し直したとしてもそれほどたいした問題にはなりませんが、 実世界の例として直近30日の訪問者数をカウントするようなWeb解析処理を考えてみましょう。 単純な実装としては直近30日のログを解析して訪問者数を集計します。 より効率的な方法としては、直近29日分のデータが変更されないことがわかっているわけなので、 直近1日分だけをインクリメンタル処理すればいいはずです。 その結果ログの解析時間を大幅に減少できます。
同様に、100ページの本の単語数をカウントしてあるとして、 さらにもう1ページ増えたとしても101ページをすべて解析しなおす必要はありません。 最後のページにある単語数だけをカウントして、以前の合計値に足すだけで済みます。 *
* 厳密にはモノイド準同型という恐ろしそうなものもあります。 これについては以降の記事で説明します。
単位元を持つことは常に必須の条件ではありません。 クロージャと結合性があれば(つまり半群であれば)多くの有用な機能が利用できます。
しかし場合によっては半群の機能だけでは足りません。 たとえば以下のような場合を考えてみましょう：
- 空のリストに対してどうやって
reduceを使えばいいだろうか？ - 分割統治アルゴリズムを採用しようとしているものの、何もすることがないステップをどうやって「分割」すればいいのだろうか？
- インクリメンタルアルゴリズムを使用する場合、データが無い場合にはどんな値を最初の値にすればいいだろうか？
いずれの場合も「ゼロ」値が必要です。
したがってたとえば空のリストの合計値は 0 になるでしょう。
上のリストの1番目について、リストが空の場合があり得るのであれば
reduce を fold に置き換えなければいけません。
fold であれば初期値を渡す事ができます。
(もちろん fold は単にモノイド演算子以外のものにも使用できます。)
以下は reduce と fold の具体例です：
// OK
[1..10] |> List.reduce (+)
// エラー
[] |> List.reduce (+)
// OK：明示的に0を指定
[1..10] |> List.fold (+) 0
// OK：明示的に0を指定
[] |> List.fold (+) 0「ゼロ」を使うと場合によっては直感に反する結果が得られることがあります。 たとえば整数の空のリストに対する積は何になるでしょう？
答えは 0 ではなくて 1 です！
以下のコードで確認できます：
[1..4] |> List.fold (*) 1 // 結果は24
[] |> List.fold (*) 1 // 結果は1まとめると、モノイドとは基本的には集計パターンを説明する方法の1つです。 一連のものがあり、それらを連結するための方法があった時に、 最終的に1つの集計されたオブジェクトが得られるというわけです。
あるいはF#的には以下のように表現できます：
Monoid Aggregation : 'T list -> 'Tつまりコードを設計していて、「和」「積」「合成」「連結」といった単語を使い始めたら、 それがまさにモノイドを使っているという合図なのです。
以上でモノイドが何なのかがわかるようになったので、 実際にそれをどうやって使うのか見ていくことにしましょう。
次回はモノイド「パターン」を実装するための実際のコードを見ていくことにします。