Writer Monadで気軽にMonad則を破る

Posted by YAMAMOTO Yuji(@igrep) on December 25, 2020Tags: Monad

🎅この記事は、Haskell Advent Calendar 2020 25日目の記事です。
🎄Happy Christmas!!🎄

今回は先日(といっても元の質問の投稿からもう何ヶ月も経ってしまいましたが…)StackOverflowに上がったこちら👇の質問に対する回答の、続きっぽい話を書こうと思います。長いし、質問の回答からスコープが大きく外れてしまうので記事にしました。

haskell - モナド則を崩してしまう例が知りたい - スタック・オーバーフロー

MonadMonoidにある重要な繋がりを説明した後、それを応用したWriter MonadがどうMonoidを使ってMonad則を満たしているのか証明します。そして、Writerのそうした性質を用いて簡単にMonad則を破る例を紹介することで、読者のみなさんがMonad則のみならずdo記法やMonadそのものの性質について、よりはっきりとした理解が得られることを目指します。

Link to
here
サンプルコードについて

本記事のサンプルコードは、Haskellの構文に準拠していないものを除いて、すべてreadme-testというツールの20201213日時点の開発版でテストしました。こちらのツールはまだ開発中で、今後も仕様が大きく変わる可能性がありますが、この記事のサンプルコードをテストするのに必要な機能は十分にそろっています。このreadme-test自体についてはいつか改めて共有します。

また、テストの際に用いた環境は以下の通りです:

Link to
here
MonadMonoidの切っても切り離せない関係

モナドは単なる自己関手の圏におけるモノイド対象だよ。何か問題でも?」というフレーズ(原文「A monad is a monoid in the category of endofunctors, whats the problem?」が示すとおり、モナドとモノイド、Haskellの識別子で言うところのMonadMonoidには密接な関係があります。ぶっちゃけ、このフレーズの正確な意味を私は理解していないのですが、少なくともMonadMonoidには重要な共通点があることは知っています。それは、どちらも単位元と結合則がある、ということです!

具体的にMonadMonoidの単位元・結合則を見てみましょう:

Monoidの単位元: 単位元であるmemptyは、どんな値x<>で足しても結果が変わらない!

Monadの単位元: return>>=の前に使っても後ろに使っても、mk aの結果を変えない!

Monoidの結合則: x <> y <> zの結果は、y <> zを先に計算しようとx <> yを先に計算しようと変わらない!

Monadの結合則: m >>= \x -> k x >>= h の結果は、\x -> k x >>= hを先に計算しようと、m >>= (\x -> k x)を先に計算しようと変わらない!

Monadの単位元・結合則の式についてはわかりやすさのために引用元から少し形を変えています。

HaskellにおけるMonadMonoidとは、値がそれぞれの単位元・結合則をを満たす型です1。それ以上でも、それ以下でもありません。

それぞれの単位元・結合則を表す式は、一見して異なるものに見えるかも知れませんが、表す性質自体はよく似ています。なので、式を読んでもよく分からないという方は、上記に書いた日本語の説明をざっと眺めて覚えておいてください。特に、結合則における「~を先に計算しようと、~を先に計算しようと変わらない!」の部分がこの後とても重要になります。

Link to
here
Monoidの例

ここまで読んで、Monadはなんか聞いたことがあるけどMonoidは初めて聞くよ、という方向けに補足すると、Monoidとは例えば次のような型の値(と、それに対する処理)です。

Sum: 数値Num型クラスのインスタンス)に対する、足し算を表すMonoidのインスタンス

memptyが各Monoidのインスタンスにおける単位元を返す、という点に注意してください。上記のとおり足し算の場合は0です。

Product: 数値Num型クラスのインスタンス)に対する、かけ算を表すMonoidのインスタンス

リスト型: リスト型の値に対する、結合 (++)を表すMonoidのインスタンス

All: Bool型の値に対する論理積&&を表すMonoidのインスタンス

Any: Bool型の値に対する論理和||を表すMonoidのインスタンス

このように、Monoidは他のプログラミング言語でもおなじみの、多くの二項演算を表しています。これらのインスタンスはすべて、先ほど紹介した「単位元」や「結合則」のルールを守っているので、気になった方はぜひチェックしてみてください2

Link to
here
MonoidWriterの切っても切り離せない関係

実はそんなMonadMonoidの固い絆を象徴するようなMonadが、この世にはあります。そう、Writerです!WriterMonoidの単位元・結合則をそのまま活かすことによってMonadの単位元・結合則を満たしたMonadであり、WriterがどうやってMonad則を満たしているのか知れば、Monad則がどうやって成立するものなのかが、すっきりクリアになることでしょう。

手始めにWriterの定義と、WriterMonadの各メソッドをどのように実装しているか見てみましょう。「モナドのすべて」におけるWriterの紹介ページから、少しリファクタリングしつつ引用します3

タプルに対してnewtypeしていることから分かるとおり、Writerの実態はただのタプルです。ただのタプルがどうやってMonadになるのでしょう?その答えがこちら👇:

returnの定義は比較的シンプルですね。memptyを受け取った値aと一緒にタプルに入れて返すだけです。Monadの単位元であるreturnでは、Monoidの単位元であるmemptyを使うのです。

一方、>>=はどう読めばいいでしょう?let ... in ...の結果にあたるWriter (b, w1 <> w2)に注目してください。

まず、b>>=の右辺であるfが返した結果です。Writer>>=が返す、Writerがラップしたタプルの一つ目の要素は、ここでfが返した値の型と一致していなければなりません。Writerにおいて>>=の型はWriter w a -> (a -> Writer w b) -> Writer w bであり、右辺にあたるf(a -> Writer w b)という型なので、>>=全体の戻り値Writer w bfの戻り値が一致している必要があることがわかりますよね?

さらに重要なのがw1 <> w2です。ここであのMonoidの演算子<>が出てきました!Writer>>=の中で<>を使うMonadなんですね!一体何と何を<>しているのでしょう?まず、<>の左辺であるw1は、左辺にあたるWriterがタプルに保持していたMonoid型クラスのインスタンスの値です。そして右辺のw2は、>>=の右辺に渡した関数fbと一緒に返したw2です。

以上のことをまとめると、Writer>>=は、

  1. 左辺の(a, w1)におけるafに渡して、
  2. fが返した(b, w2)におけるbを、
  3. w1w2と一緒に<>でくっつけつつ返す、

という処理を行っています。Writerは、「bを返すついでにw1w2<>でくっつける」と覚えてください。

Writerは、

  • Monadの単位元returnMonoidの単位元memptyを使って、
  • Monadの結合則を満たす>>=で、これまたMonoidの結合則を満たす<>を使っているのです。

やっぱりWriterMonoidあってのMonadと言えますね。

Link to
here
do<>

さて、この「bを返すついでにw1w2<>でくっつける」というWriterの振る舞いが象徴するように、大抵のMonadのインスタンスにおける>>=は、何かしら値を返すついでに、何らかの処理を行うよう実装されています。この「ついでに行われる処理」はMonadのインスタンスをdo記法の中で扱うと、ますます静かに身を隠すようになります。

こちらもWriterを例に説明しましょう。まず、例示用にWriterを作るアクションを適当に定義します。

addLoggingmultLoggingはそれぞれ、引数として受け取った整数を足し算したりかけ算したりしつつ、「足したよ」「かけたよ」という内容の文字列を一緒に返します。Writer [String] Intにおける[String]にログとして書き込んでいるようなイメージで捉えてください。

これらをdoの中で使ってみると、よりaddLoggingmultLoggingが「足し算やかけ算をするついでに、ログとして書き込んでいる」っぽいイメージが伝わるでしょう:

⚠️申し訳なくもdo記法自体の解説、つまり>>=がどのようにdo記法に対応するかはここには書きません。お近くのHaskell入門書をご覧ください。

👆では、3 + 4した結果result1と、5 * 2した結果result2を足す処理を行っています。それに加えて、「足したよ」「かけたよ」というログを表す文字列のリスト[String]も一緒に返しています。do記法が>>=に変換されるのに従い、Writer>>=が内部で<>を使い、addLogging 3 4multLogging 5 2addLogging result1 result2が返した文字列のリスト[String]を結合することによって、あたかもaddLoggingmultLoggingが「値を返しつつ、ログとして書き込む」かのような処理を実現できるのがWriterにおけるdo記法の特徴です。

能書きはここまでにして、実際にどのような結果になるか見てみましょう:

はい、3 + 45 * 2の結果を足し算した結果17と、addLogging 3 4multLogging 5 2addLogging result1 result2が一緒に返していた文字列のリスト[String]が、書いた順番どおりに結合されて返ってきました。Writerdo記法の中に書いたWriterの値(a, w)のうち、Monoidのインスタンスであるw<>で都度結合させているということが伝わったでしょうか?

Link to
here
Writer Monadの結合則とMonoidの結合則

ここまでで、Writer Monadがどのように<>を使っているのか、それによって>>=do記法がどのように振る舞っているのか、具体例を示して説明いたしました。ここからは、WriterMonoid<>の結合則をどう利用することで、Monadとしての>>=の結合則を満たしているのかを示しましょう。長いので「めんどい!」という方はこちらをクリックしてスキップしてください。

そのために、Monadの結合則における>>=を、Writer>>=として展開してみます。

(0) Monadの結合則:

(1) m>>=の左辺なのでWriter (a, w1)に置き換える:

※ここからは、比較しやすくするために等式=の左辺と右辺を別々の行に書きます。

(2) 一つ目の>>=Writerにおける>>=の定義で置き換える:

(3) 等式=の右辺における一つ目の>>=も同様に変換する:

(4) 無名関数である(\x -> k x >>= h)(\x -> k x)に、aを適用する:

(5) 等式=の左辺における二つ目の>>=Writerにおける>>=の定義で置き換える:

(6) 等式=の右辺における二つ目の>>=も同様に変換する:

(7) Writerは、Writer(a, w)を切り替えるだけで実質何もしていないので削除する:

(7.5) (7)の等式をよく見ると、=の左辺においては(b, w2)(d, w3 <> w4)が、=の右辺においては(c, w3)(b, w1 <> w2)が等しい。

(8) (7.5)から、=の左辺ではb = dw2 = w3 <> w4=の右辺ではc = dw3 = w1 <> w2であることがわかる。なのでそれぞれ置き換える:

(9) adw1w4の変数名を、登場した順番に振り直す:

等式=の左辺と右辺がそっくりな式になりましたね!

ここで、Monoidの結合則を思い出してみましょう:

そう、x <> y <> zなどと書いて3つのMonoid型クラスのインスタンスの値を<>でくっつけるときは、カッコで囲って(y <> z)を先に計算しようと、(x <> y)を先に計算しようと、結果が変わらない、というものでした!

それを踏まえて、(9)の等式=の両辺をよく見比べてみてください。異なっているのはw1 <> (w2 <> w3)(w1 <> w2) <> w3)の箇所だけですね!つまり、Writer Monadにおける>>=の結合則は、w1 <> (w2 <> w3)(w1 <> w2) <> w3)が等しいから、すなわちMonoidにおける<>の結合則が成り立つからこそ成立するのです。これがまさしく「MonoidWriterの切っても切り離せない関係」なのです!

Link to
here
関係を壊してみる

それではいよいよ、「MonoidWriterの切っても切り離せない関係」を利用して、Monad則を破ってみましょう💣

Link to
here
<>Monoidの結合則

前述のとおり、Writerにおける>>=が結合則を満たすのは、WriterがラップしているMonoidな値の<>が結合則を満たしてこそ、なのでした。これは言い換えれば、その、ラップしているMonoidな値の<>が結合則を破れば、自然にWriter>>=も結合則を破るはずです。この方法は、結合則を満たさない>>=っぽい処理をゼロから探すより遥かに簡単です。>>=のようなm a -> (a -> m b) -> m bというややこしい型の関数よりも、<>のようなa -> a -> aという型の関数の方がずっと身近ですしね!

Monoid<>のようなa -> a -> aという型の関数で、結合則を満たさない処理 — といえば、引き算-や割り算/を思い浮かべる方が多いのではないでしょうか。と、いうわけでMonoidの例で紹介したSumProductのように、数値に対する引き算を表すnewtypeDifferenceを定義してみましょう:

それから、Difference(実際には間違いですが)Monoidのインスタンスにします。最近のGHCでは、Monoidのインスタンスを定義する前にSemigroupのインスタンスにする必要があるのでご注意ください。説明しやすさのために敢えてこれまで触れてきませんでしたが、これまで何度も使った<>は実際のところMonoidの関数ではなくSemigroupの関数なんですね。Monoidは「<>で(結合則を備えた)二項演算ができるだけでなく、memptyという単位元もある」という性質の型クラスなので、「単に『<>で(結合則を備えた)二項演算ができる』だけの型クラスも欲しい!」というニーズから、Monoid<>Semigroupの関数となり、MonoidSemigroupのサブクラスという関係に変わったのでした。

何はともあれ、DifferenceSemigroupのインスタンスにしましょう:

はい、単に両辺を-で引き算するだけですね。

今度こそDifferenceMonoidのインスタンスにします。本記事ではmemptyを直接使うことはないので何でもいいはずですが、とりあえずSumと同様に0ということにしておきます:

😈これで<>が結合則を満たさないおかしなMonoidのインスタンス、Differenceができました!早速試して結合則を破っていることを確認してみましょう:

バッチリ破れてますね!このように<>における結合則は、引き算などおなじみの演算で、簡単に破ることができます💪

Link to
here
>>=Monadの結合則

<>における結合則を破ることができたと言うことは、Writer>>=による結合則も、もはや破れたも同然です。先ほど定義したDifference型を使えば、>>=は途端に結合則を満たさなくなるでしょう。

例を示す前に、Writerを使う際しばしば用いられる、ユーティリティー関数を定義しておきます。実践でWriterを使いたくなったときにも大変便利なので、是非覚えておいてください:

このtell関数は、受け取ったMonoidな値をそのまま「ログとして書き込む」関数です。結果として返す値はただのユニット()なので、気にする必要がありません。tellのみを使ってWriterを組み立てれば、「ログとして書き込む」値のみに集中することができます。これから紹介する例でもやはり関心があるのは「ログとして書き込む」値だけなので、ここでtellを定義しました。

それではtellを使って、Writer>>=における結合則も破ってみましょう:

予想どおり一つ目のWriterと二つ目のWriterとで異なる結果となりました。1 - (2 - 3)(1 - 2) - 3Writerを使って遠回しに言い換えているだけなので、当然と言えば当然です。

しかしtell (Difference 1) >>= (\_ -> tell (Difference 2) >>= \_ -> tell (Difference 3))などのWriter型の式がMonadの結合則m >>= (\x -> k x >>= h) = (m >>= (\x -> k x)) >>= hにどう対応するのか、ちょっと分かりづらいですかね?(式も長いし)一つずつ注釈を加えます:

ラムダ式の引数xは実際には使われていない点に注意してください。これでもconstを使って\x -> const (tell (Difference 2)) xと書き換えれば、const (tell (Difference 2))kに厳密に対応するので、上記の二組の式は>>=の結合則を破るペアだと言えます。

Link to
here
do記法とMonadの結合則

前の節では、Monoidの結合則を守っていない値をラップしているWriterを作ることで、>>=の結合則を破る例を簡単に作り出せることを紹介しました。ここでは本記事の最後として、>>=の結合則を破った結果、do記法がいかに直感に反する挙動となるか紹介して、>>=の結合則を守ることが私たちにどのようなメリットをもたらすのか解説します。

例として、先ほど>>=の結合則を破るのに使った1 - 2 - 3を再利用しましょう。DifferenceをラップしたWriter1 - 2 - 3を計算させると、次のような式になります:

これをdo記法に変換すると、次のようになります:

do記法における各行の間に>>=が隠れたことで、すっきりしましたね!

この状態から、do記法を使って1 - (2 - 3)(1 - 2) - 3を表すWriterの式にするには、次のように書き換えます:

コメントに書いたとおり、do_1minus'2minus3'1 - (2 - 3)do_'1minus2'minus3(1 - 2) - 3と同等なWriterです。Haskellはシングルクォートを変数の名前に含めることができるので、シングルクォートでカッコを表すことにしました(まさかこんなところで役に立つとはね!)

上記の二つの式では、カッコ()で囲う代わりにもう一つのdo記法に収めることで、do記法における各行を実行する順番をいじっています。

本当にこれで1 - (2 - 3)(1 - 2) - 3と同等な式になっているのでしょうか?試しにrunWriterして結果を確かめてみましょう:

バッチリ👌想定どおり、do_1minus'2minus3'1 - (2 - 3) = 2を計算し、do_'1minus2'minus3(1 - 2) - 3 = -4を計算していますね!

さてこれまでで、Writer MonadMonoidの結合則を利用することで>>=の結合則を満たしていることを示し、ラップしているMonoidな値が結合則を満たしていなければ、必然的にWriterも結合則を破ってしまうことを、>>=do記法を使って具体的に示しました。それでは今挙げた、do記法で結合則を破った例は、一体何を示唆しているのでしょうか?普通にHaskellでコードを書いていて、前述のような書き換え、すなわち、

から、

への書き換え(あるいはその逆)は、一見するとそんな機会ないように思えます。しかしこれが、do記法をカッコ代わりに使うという変な方法ではなく、次のように変数に代入することで切り出していた場合、いかがでしょうか?

上記👆のような三つのWriterの値を、下記👇の三つの値にリファクタリングする場合です。

あるいは、たった3行しかありませんし、一つの値に統合する方がいいかも知れません:

これらの書き換えは、いずれもdo記法が内部で使っている>>=の結合則を前提とすれば、可能であってしかるべきです。do記法は、適当にMonadのインスタンスの値(「アクション」などとも呼ばれます)を上から下まで列挙すれば、自動で>>=を使ってつなげてくれる、というものです。なので、適当に並べたアクションがどういう形に結合されるのか気にする必要があるのでは、安心して使えません。一方、上記の3組の式は、Writer Difference、すなわち引き算を表す「偽Monoid」をラップしているが故に、>>=の結合則を満たしておりません。結果、do記法に変えたときに並べたアクションをどこで切り出すかで、結果が変わってしまいます。これでは安心して列挙できません!

Link to
here
まとめ

以上です。これまでで、Monad則のうち結合則がなぜ重要なのか、結合則を実際に破ってみることを通じて説明しました。Monadと同様に結合則を持ったMonoidは、Monad以上にインスタンスを見つけるのが簡単で、なおかつ、例えば引き算のように「二項演算だけど結合則を満たしていない」処理を見つけるのが簡単です。本記事ではMonoidのそうした性質と、Monoidの性質でもってMonad則を満たしているWriter Monadに注目することで、簡単にMonad則を破る例を提示することができました。それから、Monadの結合則を実際に破った例を使って、Monadの結合則がdo記法を自然に書けるようにするために必要であることを示しました。これらの実例から主張したいことを一般化すると、次のとおりです:

  • do記法の各行の間で、値を返すついでに何かを行うのがMonadのインスタンス
  • do記法の各行の間で、値を返すついでに行っている処理が結合則を満たす型が、Monad則を満たすと言える
  • Monad則を守らない型をdo記法で使うと、do記法の結合を気にして書かなければならなくなる

それでは、2021年も🎁Happy Haskell Hacking with Monad🎁!


  1. 一応、MonadについてはそのスーパークラスであるApplicativeの則、Functorの則がありますが、Monad則を満たしていればそれらは自動的に満たせるので、ここでは省略します。

  2. 残念ながら実際のところ、Float型・Double型などの浮動小数点数に対するSumProductは結合則を満たさない場合があります。これは他の多くのプログラミング言語にもある、浮動小数点数の悩ましい問題です。詳しくは「情報落ち」で検索してみてください。

  3. ここでの定義は、実際に使われているtransformersパッケージWriterの定義とは大きく異なっているのでご注意ください。実際のWriterはパフォーマンス上の都合やMonad Transformerとの兼ね合いで、幾分工夫された定義となっています。