Chapter 18

3.4 集合としてのモノイド

さのたけと
さのたけと
2021.05.31に更新

モノイドは呆れるほど単純だが驚くほど強力な概念である。これは基本的な計算の背後にある概念であり、足し算と掛け算は共にモノイドをなす。モノイドはプログラミングの至るところに存在する。文字列、リスト、畳み込み可能なデータ構造、並行プログラミングにおけるフューチャ、関数型リアクティブプログラミングにおけるイベントなどに現れる。

伝統的には、モノイドは二項演算を備えた集合として定義される。その演算について要求されるものは、それが結合的であることと、その演算についての単位のように振る舞う特別な一つの要素が存在することである。

例えば、ゼロを含めた自然数は加法についてモノイドをなす。結合性は

(a+b)+c=a+(b+c)

が成り立つということ。(言い換えると、数を足すときには括弧をつけないでもよいということだ。)

単位元はゼロである。
なぜなら、

0+a=a

であり

a+0=a

であるからだ。
二つ目の等式は不必要で、なぜなら加法は可換(a+b=b+a)であるからだが、しかし可換性はモノイドの定義には含まれない。例えば文字列の結合は可換ではなく、しかしながらこれはモノイドをなす。なお、文字列の結合についての単位元は空文字列である。これは文字列の前後両側にその文字列を変えることなく付け加えることができる。

Haskellでは、モノイドのための型クラスを'mempty'と呼ばれる単位元と'mappend'と呼ばれる二項演算を持つ型として定義できる。

class Monoid m where
    mempty  :: m
    mappend :: m -> m -> m

二変数関数のための型シグネチャ'm -> m -> m'は最初奇妙に見えるかもしれないが、カリー化について説明した後には完全に理にかなったものになるだろう。複数の矢印を持つシグネチャーは二つの基本的な方法で解釈することができる。一つは複数の変数を持ち最も右の型が返り値の型である関数として、もう一つは一つの引数(最も左の形)を持つ関数で、関数を返すものとして。後者の解釈は'm -> (m -> m)'のようにカッコをつけることで強調することもできる。(しかし、矢印は右結合的なのでこれは冗長である)次のように。この解釈については少し後でまた戻ってくる。

注意として、Haskellにおいて、'mempty'と'mappend'のモドイドとしての性質(つまり、'mempty'が単位元であり、'mappend'が結合的であるという事実)を表現する方法はない。それらが満たされることを確かめるのはプログラマの責任である。

Haskellの型はC++の型ほど煩わしくない。新しい型を定義するときに、そのクラスを前もって特定する必要はない。自由に先延ばしにできるし、与えられた型をかなり後になって定義されるクラスのインスタンスとして宣言できる。例えば、'String'を'mempty'と'mappend'の実装を与えてモノイドとして宣言しよう。(実際、これは標準プレリュードでなされているものである)

instance Monoid String where
    mempty = ""
    mappend = (++)

ここで、リスト結合演算子(++)を再利用した。なぜなら'String'は単なる文字のリストであるから。

Haskellの文法について少しだけ加えておく。中置演算子はカッコで囲むことで二変数関数に変更することができる。与えられた二つの文字列に対し、それらの間に++を挿入することでそれらを結合することができる。

"Hello " ++ "world!"

あるいは、カッコ付きの(++)の二つの引数として与えることでもできる。

(++) "Hello " "world!"

関数の引数は今まで区切られたりカッコで囲まれていないことに注意しよう。(これはもしかしたらHaskellを学ぶときに最も慣れるのが難しいことかもしれない。)

次のように、Haskellは関数が等しいことをを表現することを許すことは強調する価値があるだろう。

mappend = (++)

概念上は、このことは次のような関数から生成される値の等号を表現とは異なる。

mappend s1 s2 = (++) s1 s2

前者は圏\mathbf{Hask}における射の一致に翻訳できる。(あるいは、もし決して終わらない計算を表すものであるbottomsを無視するなら、圏\mathbf{Set}において。)そのような等式は単に簡潔であるというだけでなく、しばしば他の圏に一般化される。後者は外延的な(extensional)一致と呼ばれ、いかなる二つの入力文字列についてその'mappend'と'(++)'の出力が一致することを主張する。引数の値は時々(points)と呼ばれることがある(fの点xでの値、というように)ため、このことは点ごとの一致と呼ばれる。引数を特定することのない関数の相等は点なし(point-free)と記述される。(ちなみに、点なし等式はしばしば関数の合成を伴い、それは点という記号を用いて表されるため、少しだけ初心者には混乱を引き起こすかもしれない。)

C++でモノイドを宣言できる最も近い方法はコンセプトの文法(提案されている)を使うことだよう。

template<class T>
struct mempty;

template<class T>
T mappend(T, T) = delete;

template<class M>
concept Monoid = requires (M m) {
    { mempty<M>::value() } -> std::same_as<M>;
    { mappend(m, m) } -> std::same_as<M>;
};

最初の定義では値テンプレート(これも提案されている)を使っている。ポリモーフィックな値は値の族である、つまり全ての型に対して異なる値を持つ。

'delete'キーワードはデフォルトの定義された値が存在しないことを意味する。それは個々の場合に応じて特定される。同様に、'mappend'についてもデフォルトの値は存在しない。

'Monoid'のコンセプトは、与えられた型Mに適切なmenmptyとmappendの定義が存在するかどうかを確かめる述語である(したがってブール型である。)

モノイドのコンセプトのインスタンス化は適切な特殊化とオーバーロードを与えることによって達成される。

template<>
struct mempty<std::string> {
    static std::string value() { return ""; }
};

template<>
std::string mappend(std::string s1, std::string s2) {
    return s1 + s2;
}

(和訳:@unaoya