bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

モナドを攻略する

1.モナド

クリスマスパーティーは大きくなった孫たちが集まりとても賑やかだった。今年は、ターキーを2羽焼いた。例によって、ブライン液につけ、ジューシーな味を楽しんだ。

f:id:bitterharvest:20181224132757j:plain
今年のターキー。焦げ具合が違うのは、250度で10分焼いた後、左側を170度、右を180度で焼いたため。両方ともおよそ1時間半焼いた。
クリスマスに掲載する記事もなかなかの大作になった。何回か説明してきたモナドだが、新しいアプローチで迫ることにした。これまでは、先人たちが築き上げてきた定義や定理を説明するという方法をとった。今回は、どのように発明・発見されたのかを知る手がかりを得るために、足場を築きながらモナドの定義を作り出すことにした。このようなアプローチをとれば、先人たちが到達するに至った深遠な意味を知ることができるだろう。さらには、格段に深いレベルでの理解も得られることにもなるだろう。それでは、始めることにしよう。

1.1 モナドの本来の意味

モナドって何ですかと問われたとき、何と答えるであろうか。数学やプログラミングに馴染みのある人は、この分野での専門用語の一つと答えることだろう。ウィキペディアで調べると、哲学でも使われていることが分かる。実はこちらの方が古くて、数学やプログラミングの分野で使われているモナドは、哲学の分野からの借用語だ。

モナドは、ギリシャ語のモナス(monas)に由来する。モナスは単子と訳されるが、それは単位としての1が原義だ。ピタゴラス(Pythagoreans)によって用いられ、ライプニッツ(Leibniz)によって発展させられた概念である。

モナドの概念を『ブリタニカ国際大百科事典』から引用すると「モナドは部分をもたない単純な実体で,物質的ではなく霊的である。生成消滅することはなく,そこに起る一切の変化は内的原理に由来し、表象によって全世界と全歴史を表現する。表象を変化させる通時的原理は欲求である。モナドは外からの影響を受けないから,モナド間に因果関係はなく、相互間の関係は予定調和の原理で説明される。世界は低級な物体から神にいたるモナドによって構成されており,この位階はそれぞれのモナドの含む表象の明瞭度による」となる。

今日の視点で見ると、ライプニッツの説明は宗教的で神秘的な雰囲気だが、モナドという概念を記述するためのキーワードは、単純な実体と表象のように見える。そして、表象は単純な実体を外に見せるための表現と捉えてよさそうだ。さらに、表象は時間的な変化により明瞭度での濃淡もあるようだ。図で示すと次のようになるだろうか。

f:id:bitterharvest:20181221202052p:plain
図1:哲学の分野で使われるモナドの概念を図示すると単純な実体と表象の列として表される。表象には明瞭度があり、実体に近いほど高い
この記事を書いているときに、若尾政希著『百姓一揆』の本をたまたま並行して読んいた。しばらく読み進むと、表象という言葉に出くわす。あまり使われない言葉なので、特別な関心を払って読んでいくうちに、表象という言葉はこのように使われるのだと改めて認識させてくれる。

歴史研究においては、歴史史料が重要な役割をなす。歴史史料は、事件の様子を伝えてくれる表象だと若尾さんは述べ、史料の扱い方について説明する。百姓一揆を研究するために使われる歴史史料には、百姓たちが幕府や藩に対して訴えた願書や、逆に百姓たちに命じる触書や、あるいは一揆の様子を叙述的に記述した物語などがある。願書や触書は事件の内容を直接伝えてくれるので一次史料と呼ばれ、物語などはエンターテインメント性をもたらせるために脚色されていて、当てにならないことが含まれているので、二次史料と言われる。モナドの説明に従えば、一次史料は明瞭度の高い表象であり、二次史料は明瞭度で劣る表象ということになる。そして、一揆という事件そのものは単純な実体だ。

話はモナドの説明とは少しずれるが、著者は、本の中で、一次史料だけ扱っていればよいのかと問いかける。歴史家たちが拠り所にしていた一次資料を精査すると、願書や触書には、前の事件を真似て書いたものが多いことに気がつくそうだ。現在の言葉で言うならばコピペが満ち溢れているということだろう。このため歴史研究をする上で、一次史料は必ずしも重宝に使っていればよいというものではないと言う。一次史料、二次史料を上手に利用して、そこから飾られた部分を除いて、真実の部分を探求することが重要だと教えてくれる。話は外れたが、事件を説明する歴史史料を表象という言葉で説明していることが、モナドの概念を深めてくれ、有意義な説明であった。

1.2 モナドの定義を試みる

話を元に戻そう。数学やプログラミングで用いるモナドは、哲学の分野で使われている概念を引き継いでいると言われている。高校数学の範囲の中で探すと、冪集合がそうだろう。ある集合の冪集合とは、その部分集合の全てを要素とする集合である。例えば集合\(A\)が3要素\( \{a,b,c\} \)からなるとする。それでは、この冪集合を求めてみよう。1)部分集合の中に複数の同じ要素が入っているものは一つにまとめられること、2)要素の出現順序は変えても構わないことに注意すると、求める冪集合は
\begin{eqnarray}
P(A)&=\{& \{\}, \{a\}, \{b\}, \{c\}, \\
&&\{a,a\}, \{a,b\}, \{a,c\}, \\
&&\{b,a\}, \{b,b\}, \{b,c\}, \\
&&\{c,a\}, \{c,b\}, \{c,c\}, \\
&&\{a,b,c\}\} \\
&=\{& \{\}, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}
\end{eqnarray}
となる。今得られた冪集合に対して、さらに冪集合を作ることができる。これを下図に示そう。なお煩雑になることを避けるため2要素\( \{1,2\} \)にした。

f:id:bitterharvest:20181221202123p:plain
図2:冪集合はモナドの概念を表現していると考えられ、単純な実体は集合の構成要素、表象は集合と冪集合、さらには冪集合の冪集合となる
新たな冪集合の作成は、その構造の変化だけを観察すると、カッコが一つずつ増えていくことに気がつく。また、冪集合に対して部分集合の和集合をとると、この冪集合を作る前の冪集合が得られることが分かる。これを下図に示そう。
f:id:bitterharvest:20181221202148p:plain
図3:冪集合の構造を見ると、右に進むにつれてカッコが一つ増える。逆に、部分集合の和集合を取るとカッコが一つ減る。また、単純な実体から集合が作られるところにも特徴がある
それではこれを一般化してみよう。\(n\)重のカッコを\(n+1\)重のカッコにする操作をカプセル化と呼び、名前\(T\)を与える。また、単純な実体から表象を作り出す操作を表象の創出と呼び、\(return\)という名前を与える。そして、部分集合の和集合を取る操作をカプセル統合と呼び、\(join\)という名前を与えることにしよう。

\(return\)は最も明瞭度の高い表象を作り出し、\(join\)は操作を繰り返しているうちに最も明瞭度の高い表象に至ることに気がつく。\(return\)も\(join\)も最も明瞭度の高い表象に向かうということに特徴がありそうだ。モナドを構成するときに、この性質を取り入れることが重要に思える。それ以上に重要なことは、カプセル化をしている\(T\)だろう。

そこでこれらを用いて、圏を試しに構成してみよう。圏の名前は、\(\mathcal{C}\)としよう。そして、対象は、単純な実体と表象たちだ。即ち、\( A,T(A),T(T(A)),…\)だ。射は、先ほど定義した\( return\)と\( join \)だ。また、恒等射は、\( I_{A},I_{T(A)},I_{T(T(A))},… \)だ。射の合成は\(\circ\)とし、また単位律、結合律は成り立っているとする。そして、\(T\)は、\(\mathcal{C}\)から\(\mathcal{C}\)への関手としよう。即ち、自己関手だ。まとめると試案の圏は以下のようになる。
圏\(\mathcal{C}\)の構成 (試案)
対象:\( A,T(A),T(T(A)),…\)
射:\( return : A \rightarrow T(A), join : T(T(A)) \rightarrow T(A) \)
恒等射:\( I_{A},I_{T(A)},I_{T(T(A))},… \)
合成:\(\circ\)
単位律:省略
結合律:省略

図で示すと下図のようになる。

f:id:bitterharvest:20181221202408p:plain
図4:冪集合の構造的な特徴を捉えて、カッコを増やす操作を\(T\)、単純な実体から表象を創出する操作を\(return\)、和集合によってカッコを一つ減らす操作を\(join\)と名付け、これらを、モナドを圏として定義するときの、構成要素にしよう
このように定義すると、関手\(T\)によって、\(A\)から\(T(A)\)に、\(T(A)\)から\(T(T(A))\)に、さらに\( T(T(A)),T(T(T(A))),...\)も同じようによって移される。一般に関手は圏の間の射なので、\( A,T(A),T(T(A)),… \)は、それぞれを圏と見なすことにしよう。そこで、圏であることを明確にするために、\(A\)を\(\mathcal{A} \)と表すことにしよう。試案の圏は次のように書き直される。改めてということになるが、\(\mathcal{A}\)は圏である。
圏\(\mathcal{C}\)の構成
対象:\( \mathcal{A},T(\mathcal{A}),T(T(\mathcal{A})),…\)
射:\( return : \mathcal{A} \rightarrow T(\mathcal{A}), join : T(T(\mathcal{A})) \rightarrow T(\mathcal{A}) \)
恒等射:\( I_{\mathcal{A}},I_{T(\mathcal{A})},I_{T(T(\mathcal{A}))},… \)
合成:\(\circ\)
単位律:省略
結合律:省略

これで、圏\(\mathcal{C}\)が出来上がった。細部も加えて示したのが下図である。

f:id:bitterharvest:20181226093900p:plain
図5:冪集合を利用してモナドの候補を作り出した。\(T\)が圏\(\mathcal{C}\)を結ぶ関手、これがモナドと呼ばれるものになる。\(return,join\)は圏\(\mathcal{C}\)の射である
そして、これをモナド定義の候補としたい。

1.3 Haskellモナドで確認する

モナドを表すための候補が出てきたので、先に進める前に、本当にそうなのかを、Haskellでのモナドの定義を利用して確認してみよう。Control.Monadのパッケージを見ると次のようになっている。

class Applicative m => Monad m where
  (>>=) :: forall a b. m a -> (a -> m b) -> m b

  (>>) :: forall a b. m a -> m b -> m b
  m >> k = m >>= \_ - > k

  return :: a -> m a
  return = pure

  fail :: String -> m a
  fail s = errorWithoutStackTrace s

さらに、これらのメソッドは単位律と結合律を満たすものとする。

Haskellでのモナドのクラスで用意しなければならないメソッドは、\(return\)とバインド(bind)と呼ばれる\((>>=)\)だ。しかし\(return\)はモナドの上位クラスであるアプリカティブ(Applicative)で定義されるので、モナドのところで定義する必要があるメソッドは\((>>=)\)だけだ。2番目のメソッド\((>>)\)は、バインドを用いて定義されているので、定義する必要はないし、またそれほど重要なメソッドでもない。

繰り返しになるが、Haskellモナドで重要なメソッドは\( (>>=)\)と\(return\)である。そこで、冪集合がモナドであるという推察を確認するためには、冪集合のところで得た\( return\)と\(join\)が、Haskellでのメソッド\(return\)と\((>>=)\)に対応していることを示さなければならない。

冪集合 Haskell
1 \( return : A \rightarrow P(A) \) \(return :: a \rightarrow m \ a\)
2 \( join : P(P(A) \rightarrow P(A) \) \((>>=) :: forall \ a \ b. \ m \ a \rightarrow (a \rightarrow m \ b) \rightarrow m \ b\)

上の表で、式1は対応していることが分かる。しかし、式2、即ち\(join\)と\( (>>=)\)は対応しているとは即断しがたい。そこで、Haskellでの定義を変形してみよう。モナド\(m\)は関手なので、
\begin{eqnarray}
m \ a \rightarrow (a \rightarrow m \ b)
\end{eqnarray}
の部分は、下図のように表すことができる。

f:id:bitterharvest:20181221202432p:plain
図6:モナドの候補を確認する。Haskellの構造に変換し、Haskellで定義されているモナドの構造に対応しているかを観察する。そのためには、候補の\(join\)とHaskellの\(>>=\)が対応していることを示せばよい
上図で、左側の射\(f: a \rightarrow m \ b\)を関手\(m\)によって、右側に移される。そして、\(m \ a \rightarrow (a \rightarrow m \ b)\)は、右側に移った射の始点\(m \ a\)が与えられた時、その終点をあたえる。このとき右側に移った射は\(fmap \ f \ (m \ a)\)である。これより、
\begin{eqnarray}
m \ a \rightarrow (a \rightarrow m \ b) & = & (fmap \ f \ (m \ a)) \\
& = & m (f (a)) \\
& = & m (m \ b)
\end{eqnarray}
となる。まとめると、
\begin{eqnarray}
m \ a \rightarrow (a \rightarrow m \ b) \rightarrow m \ b \\
= m (m \ b) \rightarrow m \ b
\end{eqnarray}
である。\(b\)を\(a\)で置き換えると、
\begin{eqnarray}
m (m \ a) \rightarrow m \ a
\end{eqnarray}
となり、\(join\)同じであることが分かる。

これで、冪集合から得られた2関数がモナドを定義するのに必要な関数であるという裏付けを得たので、さらに議論を進めることにしよう。

1.4 汎用化する

一般的なモナドの定義に近づけるために、\( return,join\)を\(η,μ\)で置き換え、汎用化してみよう。

\begin{eqnarray}
η &:& A & \rightarrow & T(A) \\
μ &:& T(T(A) & \rightarrow & T(A)
\end{eqnarray}

さらに、\(T(A),T(T(A)),…\)は同じ薄茶色で表し、薄緑色の部分をなくすと、前に示した図は次のように表すことができる。

f:id:bitterharvest:20181221211917p:plain
図7:一般的なモナドの定義に近づけるために、\( return,join\)を\(η,μ\)で置き換える
上の式をもう少し変形してみよう。恒等射\(I:A \rightarrow A\)を用いると上記の式は次のようになる。
\begin{eqnarray}
η &:& I(A) & \rightarrow & T(A) \\
μ &:& T(T(A) & \rightarrow & T(A)
\end{eqnarray}
上記の式は任意の\(A\)について成り立つので、\(A\)を省くと
\begin{eqnarray}
η &:& I & \rightarrow & T \\
μ &:& T \circ T & \rightarrow & T
\end{eqnarray}
と記述することができる。そこで、圏\(\mathcal{C}\)を対象とし、関手\(T\)を射とし、モナドを表す圏\(\mathcal{D}\)をつぎのように定義できる。
圏\(\mathcal{D}\)の構成
対象:圏\(\mathcal{C}\)
射:\(T: \mathcal{C} \rightarrow \mathcal{C} \)
恒等射:\(I_\mathcal{C} \)
合成:\(\circ\)
そして、次のように、単位律、結合律を満たすものとする。
単位律:\(I_\mathcal{C} \circ T= I_\mathcal{C} = T \circ I_\mathcal{C} \)
結合律:\( (T \circ T) \circ T = T \circ (T \circ T) \)

圏\(\mathcal{D}\)は、さらに
\begin{eqnarray}
η&:& I_\mathcal{C} & \rightarrow & T \\
μ&:& T \circ T & \rightarrow & T
\end{eqnarray}
を満たすものとする。ここでは、\(η: I \rightarrow T \)から\(η: I_\mathcal{C} \rightarrow T \)に変えている。恒等射の定義域が単純な実体の領域から表層の領域まで含むようになったが、\(η: I_T \rightarrow T \circ T \rightarrow T \)であることから、矛盾なく拡張することが可能である。

圏\(\mathcal{D}\)を図で示すと以下のようになる。

f:id:bitterharvest:20181221202529p:plain
図8:モナドとしての関手\(T\)を射とした圏を構成する
ここで得たモナドの圏\(\mathcal{D}\)は、圏論の教科書で定義されているものと同一であることに気がつくことと思う。そしてこの圏の射、即ち関手\(T\)は、一般にモナドと言われる。ライプニッツモナドの概念から始めて、冪集合を用いてモナドの定義に必要とされるだろう関数\(return,join\)を求め、その関数がHaskellでのモナドの定義で用いられているものと同じであるという検証を得て、モナド\(T\)を射とする圏\(\mathcal{D}\)を定義することができた。

この圏をしばらく観察してみよう。対象\(\mathcal{C}\)を小さくし、射\(T\)、恒等射\(I_\mathcal{C}\)、そしてこれらから合成される射を描くと下図のようになる。

f:id:bitterharvest:20181221202557p:plain
図9:モナドは自己関手\(T\)を射としたモノイド圏であることが分かる
これは、その右側に描いたモノイド圏(単位律とかつ結合律を満たす二項演算子により構成された圏)と構造が同じであることが分かる。従って、モナドは、自己関手\(T\)を射としたモノイド圏であることが分かる。

1.5 精錬化する

これまでの議論でモナドの定義は出来上がったが、もう少し綺麗に纏めることにしよう。\(η, μ\)が関手から関手への射になっているので、自然変換と見なせる。

自然変換を復習しておこう。圏\(\mathcal{C}, \mathcal{D}\)があり、前者から後者へ関手\(F,G\)が存在したとする。このとき、\(F\)から\(G\)への射\(η\)が自然変換であるとは、\(\mathcal{C}\)の任意の対象\(A,B\)とその間のやはり任意の射\(f\)に対して、\(\mathcal{D}\)で\( G(f) \circ η_A = η_B \circ F(f)) \)が成り立つことである。この関係を下図に示す。

f:id:bitterharvest:20181222085042p:plain
図10:自然変換は関手から関手への射である。任意の対象\(A,B\)とその間のやはり任意の射\(f\)に対して、\( G(f) \circ η_A = η_B \circ F(f)) \)が成り立つ
それでは、自然変換\(η, μ\)を射とした圏\( \mathbf{End}_\mathcal{C} \)を構成してみよう。
圏\( \mathbf{End}_\mathcal{C} \)の構成
対象:\(I_\mathcal{C}, T, T \circ T \)
射:\( η: I_\mathcal{C} \rightarrow T, μ: T \circ T \rightarrow T \)
恒等射:\(I_ T : T \rightarrow T\) (注意:これは恒等変換である)
合成:\( \circ \)
単位律:\( μ \circ (I_T \circ η) = I_T = μ \circ (η \circ I_T) \)
結合律:\( μ \circ (I_T \circ μ) = μ \circ (μ \circ I_T) \)
となる。図で表すと以下のようになる。
f:id:bitterharvest:20181221202840p:plain
図11:モナドを最も抽象的に表した圏\( \mathbf{End}_\mathcal{C} \)で、自然変換\(η(return),μ(join)\)を射とし、モナドとしての関手\(T\)を対象とする
さらに、\(I_T\)は\(T\)と表すこともできるので、これを用いて、単位律、結合律を可換図式で表すと下図になる。
f:id:bitterharvest:20181223064508p:plain
図12:モナドとしての条件を示した可換図式。単位律、結合律に対応する

モナドの定義が出来上がったので、圏論での最も重要な概念である随伴との関係について述べておこう。ウィキペディアでは随伴は次のように定義されている。圏\(\mathcal{C}\)と\(\mathcal{D}\)との間の随伴とは、二つの関手
\begin{eqnarray}
L: \mathcal{D} \rightarrow \mathcal{C} \\
R: \mathcal{C} \rightarrow \mathcal{D}
\end{eqnarray}
の対であって、全単射の族
\begin{eqnarray}
hom_{\mathcal{C}}(L(Y),X) \cong hom_{\mathcal{D}}(Y,R(X))
\end{eqnarray}
が変数\(X,Y\)に対して自然となるものをいう。このとき、関手\(L\)を左随伴関手と呼び、\(R\)を右随伴関手と呼ぶとなっている。図で表すと、

f:id:bitterharvest:20181222203140p:plain
図13:同型なhom集合を用いての随伴の定義

しかし、上記の定義からモナドとの関係を説明するのは煩雑になるので、もう一つの定義を使うことにしよう。それは、やはりウィキペディアで次のように定義されている。

圏\(\mathcal{C}\)と\(\mathcal{D}\)の余単位・単位随伴は二つの関手
\begin{eqnarray}
L: \mathcal{D} \rightarrow \mathcal{C} \\
R: \mathcal{C} \rightarrow \mathcal{D}
\end{eqnarray}
および二つの自然変換
\begin{eqnarray}
η: I_\mathcal{D} \rightarrow R \circ L \\
ε: L \circ R \rightarrow I_\mathcal{C}
\end{eqnarray}
であって(ηは単位、εは余単位と呼ばれる)、これらの合成
\begin{eqnarray}
L =L \circ I_\mathcal{D} \xrightarrow{L \circ η} L \circ R \circ L \xrightarrow{ε\circ L} L \\
R = I_\mathcal{D} \circ R \xrightarrow{η\circ R} R \circ L \circ R \xrightarrow{R \circ ε} R
\end{eqnarray}
がそれぞれ\(L\)と\(R\)上の恒等変換\(I_L,I_R\)となることをいうとなっている。これは三角恒等式(triangle identities)と呼ばれる。これを可換図式で示そう。

f:id:bitterharvest:20181223065614p:plain
図14:余単位・単位による随伴の定義の一部である三角恒等式の可換図式
それではこの定義からモナドを導くこととしよう。圏\( \mathbf{End}_\mathcal{C} \)での射\(η,μ\)が、随伴を定めている\(η,ε\)から得られることを示せばよい。そこで、
\begin{eqnarray}
T=R \circ L
\end{eqnarray}
としてみよう。モナド側の\(η\)を得ることは次に示すように簡単である。
\begin{eqnarray}
I_\mathcal{D} \xrightarrow{η} R \circ L = T
\end{eqnarray}

それでは\(μ\)について考えよう。次のように変換して求めることができる。
\begin{eqnarray}
T \circ T = R \circ L \circ R \circ L \xrightarrow{R \circ ε \circ L} R \circ I_\mathcal{C} \circ L = R \circ L = T
\end{eqnarray}

図示すると次のようになる。

f:id:bitterharvest:20181223064622p:plain
図15:圏\( \mathbf{End}_\mathcal{C} \)での射\(η,μ\)を随伴より得る

1.6 モナドと随伴の関係

圏\( \mathbf{End}_\mathcal{C} \)の単位律、結合律を随伴から得てみよう。まず単位律から始める。
\begin{eqnarray}
L \xrightarrow{L \circ η} L \circ R \circ L \xrightarrow{ε\circ L} L \\
R \xrightarrow{η\circ R} R \circ L \circ R \xrightarrow{R \circ ε} R
\end{eqnarray}
と、およびそれぞれで左辺と右辺は恒等変換になっていることを利用すると
\begin{eqnarray}
T \circ I_\mathcal{D} = R \circ L \circ I_\mathcal{D} \xrightarrow{R \circ L \circ η} R \circ L \circ R \circ L \xrightarrow{R \circ ε \circ L} R \circ L = T \\
I_\mathcal{D} \circ T = I_\mathcal{D} \circ R \circ L \xrightarrow{η \circ R \circ L} R \circ L \circ R \circ L \xrightarrow{R \circ ε \circ L} R \circ L = T
\end{eqnarray}
を得る。またそれぞれで左辺と右辺は恒等変換になっていることもわかる。可換図式で示すと下図のようになる。

f:id:bitterharvest:20181223075707p:plain
図16:随伴の定義からモナドの単位律を得る

次は結合律だ。単位律と同様に式を展開することで得ることができる。その過程を可換図式で示しておこう。

f:id:bitterharvest:20181223082421p:plain
図17:随伴の定義からモナドの結合律を得る

1.7 冪集合をHaskellで実装する

無事にモナドを定義することができたので、考える出発点であった冪集合に戻り、これをHaskellで実現することとしよう。

ここでは、集合をリストで表すこととしよう。例えば、要素\(a,b,c\)からなる集合は\([a,b,c]\)と表すことにする。冪集合は、それぞれの要素に対して、含むか含まないかの組合せを作ることだ。リストは\((x:xs)\)と表すことができるので、\(xs\)で作られる冪集合の部分集合のそれぞれに要素\(x\)をつけたものとつけないものとの和集合となる。

\(xs\)から作られた冪集合を\(rest\)とし、これに要素\(x\)をつける操作は

rest >>= (return . (x:))

である。
確認しておこう。

Prelude> import Control.Monad
*Main Control.Monad> [[2,3],[2],[3]] >>= (return . (1:))
[[1,2,3],[1,2],[1,3]]

従って、要素\(x\)をつけるかつけないかを、ブール値\(b\)で判断するプログラムは次のようになる。

\b -> if b then rest >>= (return . (x:)) else rest

これを用いてみよう。

*Main Control.Monad> f x rest = \b -> if b then rest >>= return . (x:) else rest 
*Main Control.Monad> [True, False] >>= f 1 [[2,3],[2],[3]]
[[1,2,3],[1,2],[1,3],[2,3],[2],[3]]

少し、工夫をして、\(x\)の値を外から与えられるようにしよう。

\x -> const [True, False] x >>= \b -> if b then rest >>= (return . (x:)) else rest

確認しよう。

*Main Control.Monad> g rest = \x -> const [True, False] x >>= \b -> if b then rest >>= (return . (x:)) else rest
*Main Control.Monad> g [[2,3],[2],[3]] 1 
[[1,2,3],[1,2],[1,3],[2,3],[2],[3]]

次に\(rest\)の部分を再帰的に構成できるようにしよう。次のようになる。そして関数名を\(power set\)としよう。

powerset [] = return []
powerset (x:xs) = const [True, False] x >>= (\b -> 
               if b 
                   then powerset xs >>= (return . (x:)) 
                   else powerset xs) 

確認しよう。

*Main Control.Monad> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

今求めた関数\(power set\)の構造を圏論モナドを用いて描くと下図のようになる。

f:id:bitterharvest:20181224131956p:plain
図18:冪集合を求める関数\(power set\)をモナドを用いて記述する

Haskellでは、より汎用的な\(filterM\)が用意されているので、\(Power set\)はこれを用いて次のように定義すればよい。

powerset = filterM (const [True, False])

一応確認しておこう。

Prelude> import Control.Monad
*Main Control.Monad> powerset = filterM (const [True, False])
*Main Control.Monad> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

出来上がりだ。モナドを定義するために、冪集合から初めて、最後はまた冪集合に戻ってきた。クリスマスプレゼントとはいえ、長い記事になってしまったが、モナドを様々な面から観察することができ、新たな発見もあって、楽しむことができた。読者の方はいかがでしたか。