モナドの驚異
2019-03-22 07:06:19
Wes DyerのBlog “Yet Another Language Geek”に、モナドに関する記事が投稿されていたので、訳してみる。
(追記)Mike Hadlowのブログ記事も、ほぼ同じような内容を扱っている。
モナドの驚異
「継続」という単語を聞くと目がどんより曇ってしまうとするなら、「モナド」という単語を聞けば心が麻痺してしまうことになるでしょう。だからこそ、モナドに対してもっと聞こえのいい呼び方を考えようとしている人がいるのでしょう。たぶん。
最近、プログラミング言語理論においてモナドは有名人です。モナドはいくつものブログの表紙を飾り、さまざまなものと比較されていました。果物箱から果ては恋愛まで。モナドを理解する経験によって、痛 気持ちいい 心地 になるんだ、と、オタクたちは至る所で叫んでいます。
継続と同じように、モナドは噂に聞こえるよりも単純ですし、多くの状況で実に役立つものです。実際、プログラマー達は、一般的なモナドを暗黙のうちに使っている言語をいろいろ使ってコードを書いていますが、それで大変な思いをしているわけではありません。
モナドは もう 充分な ほどに 注目 されて いると いうのに、どうして私は、さらに別のモナドの説明を書いているのでしょうか?日常のよくある出来事に例えるためでもなければ、モナドを理解した経験を時系列で記録するためでもありません。私がモナドを説明するのは、私にとってモナドが必要だからです。モナドは、いくつもの言語や文脈において、プログラミング上の問題をエレガントに解決するのです。
モナドを導入する
モナドは圏論から来ています。Moggiは計算の意味論の分析を支援するため、コンピューターサイエンスの専門家たちにそれらを紹介しました。ワドラーは優れた論文、『関数型プログラミングの本質』で、モナドがコンピュータープログラムにおいて、値に作用する関数ではなく、増強された値に作用する関数を組み立てるときに通常は役に立つということを示しました。モナドはプログラミング言語Haskellにおいて厄介な一味――IO、並列性、例外と外部関数呼び出し――に取り組むための重要な部分になりました。
モナドはHaskellにおいてかなり成功しています。しかし、特定の役だけをうまく演じる俳優の様に、モナドは現在大部分のプログラマーの心の中で、純粋な遅延評価の関数型言語だけでしか役に立たないという思い込みにはまっています。これは残念なことです。なぜなら、モナドはもっと広く適用できるのですから。
複雑さを支配する
合成はソフトウェアの複雑さを支配する鍵です。『計算機プログラムの構造と解釈』で、アベルソンとサスマンは単純なパターンを合成することで複雑なシステムを美しく表現できると主張しています。
プログラム設計に関する我々の研究において、すべての複雑なシステムの設計者により用いられるのと同じ一般的なテクニックで、熟練したプログラマーが彼らの設計の複雑さを制御するのを見た。彼らは合成オブジェクトを作るために基本要素を結合し、より高水準なビルディングブロックを形成するために合成オブジェクトを抽象化し、システム構造の適切な大規模ビューを採用することによってモジュラリティーを保つ。
合成の1つの形である関数合成は、関数呼び出しの間の依存関係を簡潔に記述します。関数合成は2つの関数を受け取って、第2の関数の結果を最初の関数の入力に接続します。そして、それによって1つの関数が作られます。
public static Func<T, V> Compose<T, U, V>(this Func<U, V> f, Func<T, U> g)
{
return x => f(g(x));
}
たとえば、値 x
に g
を適用した結果に f
を適用する代わりに、 g
と f
を合成した結果を値 x
に適用します。鍵となる違いは、 f
と g
の間の依存関係の抽象化です。
var r = f(g(x)); // 関数合成なし
var r = f.Compose(g)(x); // 関数合成あり
Identity
関数が与えられた時、関数合成は3つの法則に従わなければなりません。
public static T Identity<T>(this T value)
{
return value;
}
- 左単位元
Identity.Compose(f) = f
- 右単位元
f.Compose(Identity) = f
- 結合法則
f.Compose(g.Compose(h)) = (f.Compose(g)).Compose(h)
単なる値では不十分な場合もあります。構築された型(訳注:型引数が指定されたジェネリック型)は値を増強します。型 IEnumerable<T>
は遅延評価される型 T
の値のリストを表現します。型 Nullable<T>
は、型 T
の存在しないかもしれない値を表現します。型 Func<Func<T, Answer>, Answer>
が表現しているのは、ある継続を受け取って Answer
を返す関数ですが、その継続とは1つの T
を受け取って Answer
を返すものです。これらの構築された型はどれも型 T
を増強しているのです。
値を返す関数を合成する代わりに、値を受け取って増強された値を返す関数を合成することを考えましょう。増強された値の型を M<T>
で表わします。
public static Func<T, M<V>> Compose<T, U, V>(this Func<U, M<V>> f, Func<T, M<U>> g)
{
return x => f(g(x)); // エラー。g(x)は M<U> を返すが、fはUを受け取る
}
戻り値の型と入力の型が合わないので、関数合成は失敗します。増強された値を伴う合成は、根底にある値にアクセスして次の関数にそれを供給する関数を必要とします。その関数を Bind
と呼び、それを使って関数合成を定義します。
public static Func<T, M<V>> Compose<T, U, V>(this Func<U, M<V>> f, Func<T, M<U>> g)
{
return x => Bind(g(x), f);
}
入力と出力の型が Bind
のシグネチャーを決定します。
したがって、 Bind
は増強された値 M<U>
と、 U
を M<V>
に変換する関数を受け取って、
増強された値 M<V>
を返します。
public static M<V> Bind<U, V>(this M<U> m, Func<U, M<V>> k)
Bind
の本体は増強された値 M<T>
の機構に依存します、各々の増強された型は異なる Bind
の定義を必要とします。
Bind
に加えて、増強されていない値を受け取ってそれを増強する関数を定義します。この関数を Unit
と呼びます。
public static M<T> Unit<T>(this T value)
増強された型 M<T>
と関数 Bind
と関数 Unit
を一緒にすることで、増強された値を伴う関数合成が可能になります。
モナドとの出会い
なんということでしょう、私たちは今まさにモナドを発明したのです。
モナドは型、 Unit
関数、そして Bind
関数からなる3つ組です。さらに、モナドであるために、3つ組は3つの法則を満たさなければなりません:
- 左単位元
Bind(Unit(e), k) = k(e)
- 右単位元
Bind(m, Unit) = m
- 結合法則
Bind(m, x => Bind(k(x), y => h(y)) = Bind(Bind(m, x => k(x)), y => h(y))
法則は関数合成のものと類似しています。これは偶然の一致でありません。これらの法則は、モナドが行儀良くふるまうことと、合成がきちんと動作することをを保証します。
特定のモナドを定義するには、作者は3つ組を提供します。そして、それによって増強された値の機構を指定します。
Identityモナド
最も単純なモナドは Identity
モナドです。この型は値を格納するラッパーを表現します。
class Identity<T>
{
public T Value { get; private set; }
public Identity(T value) { this.Value = value; }
}
Unit
関数は値を受け取って Identity
の新しいインスタンスを返します。そのインスタンスは元の値をラップしています。
static Identity<T> Unit<T>(T value)
{
return new Identity<T>(value);
}
Bind
関数は Identity
のインスタンスを受け取って値を開封し、開封した値でデリゲート k
を呼び出します。戻り値は Identity
の新しいインスタンスです。
static Identity<U> Bind<T,U>(Identity<T> id, Func<T,Identity<U>> k)
{
return k(id.Value);
}
2つの Identity
ラッパーを作成して、ラップされた値に対する操作を実行する単純なプログラムを考えます。まず、値 5
を保持しているラッパーの中の値に x
をバインドします。そして、値 6
を保持しているラッパーの中の値に y
をバインドします。最後に、値 x
と y
を加えます。結果は、値 11
をラップしている Identity
のインスタンスです。
var r = Bind(Unit(5), x =>
Bind(Unit(6), y =>
Unit(x + y)));
Console.WriteLine(r.Value);
これは動作しますが、やや不格好です。モナドを扱うための構文があればうれしいのですが。実はあります。
C# 3.0はクエリ内包を導入しましたが、それは実はモナド内包の変装した姿です。Identity
モナドを書き直すことでLINQが使えるようになります。おそらく、LINQはLINM(言語統合モナド)と呼ばれるべきだったのでしょう。とはいえ、言葉の響きは同じ雰囲気にはなりませんが。
Unit
メソッドを ToIdentity
に、そして Bind
メソッドを SelectMany
にリネームします。そして、それらの両方を拡張メソッドとします。
public static Identity<T> ToIdentity<T>(this T value)
{
return new Identity<T>(value);
}
public static Identity<U> SelectMany<T, U>(this Identity<T> id, Func<T, Identity<U>> k)
{
return k(id.Value);
}
この変更は、呼び出し側コードに影響を与えます。
var r = 5.ToIdentity().SelectMany(
x => 6.ToIdentity().SelectMany(
y => (x + y).ToIdentity()));
Console.WriteLine(r.Value);
LINQのために定義される標準クエリ演算子に、同等のメソッドが含まれています。ただし、パフォーマンス上の理由から、標準クエリ演算子にはちょっとだけ違った SelectMany
も含まれています。そちらは Bind
と Unit
を結合しているため、ラムダはそれほど深く入れ子になりません。メソッドのシグネチャーはほぼ同じですが、引数にデリゲートが追加されています。そのデリゲートは2つの引数を受け取って値を返す関数で、2つの値を結合するものです。こちらの SelectMany
は、ラップされた値を x
にバインドし、k
を x
に適用した結果を y
にバインドして、そして結合関数 s
を x
と y
に適用します。結果として生じる値はラップされて返されます。
public static Identity<V> SelectMany<T, U, V>
(this Identity<T> id, Func<T, Identity<U>> k, Func<T,U,V> s)
{
return id.SelectMany(x => k(x).SelectMany(y => s(x, y).ToIdentity()));
}
もちろん、 Identity
モナドについての知識を用いれば、上記の一般的なソリューションからコードの一部を削除することができます。
public static Identity<V> SelectMany<T, U, V>
(this Identity<T> id, Func<T, Identity<U>> k, Func<T,U,V> s)
{
return s(id.Value, k(id.Value).Value).ToIdentity();
}
呼び出し側は、ラムダをネストさせる必要がなくなります。
var r = 5.ToIdentity()
.SelectMany(x => 6.ToIdentity(), (x, y) => x + y);
Console.WriteLine(r.Value);
新しく定義した SelectMany
があれば、プログラマーはC#のクエリ内包構文を使うことができます。from
記法は、導入された変数を右側の式がラップしている値にバインドします。これによって、その後の式では SelectMany
を直接呼び出すことなくラップされた値を使うことができます。
var r = from x in 5.ToIdentity()
from y in 6.ToIdentity()
select x + y;
もともとの SelectMany
の定義はモナドの Bind
関数と直接対応していますし、定義を変形する一般的な方法が存在することも説明しましたから、記事の残りでは元のシグネチャーのほうを使用します。ただし、クエリ構文を使うことができるのは2番目の定義のほうであることを心にとめておきましょう。
Maybeモナド
Identity
モナドは、モナド・コンテナ型の例です。Identity
モナドはある1つの値をラップしています。1つの値か、あるいは存在しない値かのどちらかを格納するように定義を変えるならば、それは Maybe
モナドになります。
もう一度、型を定義しなおす必要があります。Maybe
型は Identity
型に似ていますが、値が存在しないかどうかを意味するプロパティが追加されています。また、あらかじめ定義されたインスタンス Nothing を持ち、それによって値が欠如しているすべてのインスタンスを表現します。
class Maybe<T>
{
public readonly static Maybe<T> Nothing = new Maybe<T>();
public T Value { get; private set; }
public bool HasValue { get; private set; }
Maybe()
{
HasValue = false;
}
public Maybe(T value)
{
Value = value;
HasValue = true;
}
}
Unit
関数は値を受け取って、 Maybe
インスタンスを生成します。そのインスタンスは元の値をラップしています。
public static Maybe<T> ToMaybe<T>(this T value)
{
return new Maybe<T>(value);
}
Bind
関数は、 Maybe
インスタンスを1つ受け取って、もし値があるならば、保持している値にデリゲートを適用します。値がなければ Nothing
を返します。
public static Maybe<U> SelectMany<T, U>(this Maybe<T> m, Func<T, Maybe<U>> k)
{
if (!m.HasValue)
return Maybe<U>.Nothing;
return k(m.Value);
}
プログラマーは、 Maybe
モナドを処理するために内包構文を使うことができます。たとえば、値5を含んでいる Maybe
のインスタンスを生成して、それに Nothing
を加えましょう。
var r = from x in 5.ToMaybe()
from y in Maybe<int>.Nothing
select x + y;
Console.WriteLine(r.HasValue ? r.Value.ToString() : "Nothing");
結果は "Nothing"
です。ヌル許容型におけるNullの伝播を明示的な言語サポートなしで実装しました。
Listモナド
もう一つの重要なコンテナ型はリスト型です。実際、List
モナドこそがLINQの中心的な存在です。型 IEnumerable<T>
は、遅延計算されるリストを意味しています。
Unit
関数は1つの値を受け取ってリストを返します。そのリストは元の値だけを含んでいます。
public static IEnumerable<T> ToList<T>(this T value)
{
yield return value;
}
Bind
関数は1つの IEnumerable<T>
と1つのデリゲートを受け取ります。そのデリゲートは、1つの T
を受け取って IEnumerable<U>
を返すものです。 そしてこの関数は IEnumerable<U>
を返します。
public static IEnumerable<U> SelectMany<T, U>
(this IEnumerable<T> m, Func<T, IEnumerable<U>> k)
{
foreach (var x in m)
foreach (var y in k(x))
yield return y;
}
さて、プログラマーはおなじみのクエリ表現を IEnumerable<T>
でも書くことができます。
var r = from x in new[] { 0, 1, 2 }
from y in new[] { 0, 1, 2 }
select x + y;
foreach (var i in r)
Console.WriteLine(i);
魔法を可能にしているのはモナドであることを忘れないでください。
継続モナド
継続モナドは前回の記事の終わりに提起された問題に答えるものです:どうすれば、プログラマーはより口に合う方法でCPSのコードを書くことができますか?
継続モナド K
の型は、(引数を受け取って答えを返す)継続が与えられたときに答えを返すデリゲートです。
delegate Answer K<T,Answer>(Func<T,Answer> k);
型 K
は、型 Identity<T>
や Maybe<T>
や IEnumerable<T>
と基本的に異なります。他のモナドはすべてコンテナ型を表現していて、コンテナよりもむしろ値に関する計算を指定できます。しかし、継続モナドは何も格納していません。その代わりに、継続モナドはユーザーが書く継続を合成するのです。
モナドであるためには、1つの T
を受け取って、答えの型を表す K<T,Answer>
を返す Unit
関数がなければなりません。
public static K<T, Answer> ToContinuation<T, Answer>(this T value)
これは何をするべきものなのでしょうか?ものごとが不確かなときは、型に目を向けましょう。このメソッドは T
を受け取って関数を返します。その関数は、 T
を Answer に変換する関数を受け取って、Answer
を返します。したがって、このメソッドは関数を返さなければなりませんし、その関数の唯一の引数は、 T
を Answer
にする関数です。この引数を c
としましょう。
return (Func<T, Answer> c) => ...
上記のラムダの本体は Answer
型の値を返さなければなりません。そのために、型 Func<T,Answer>
と型 T
の値を使うことができます。c
を value
に適用すれば、結果は Answer
型です。
return (Func<T, Answer> c) => c(value);
モナドであるためには、 Bind
は K<T,Answer>
と、T
を K<U, Answer>
にする関数とを受け取って、K<U, Answer>
を返さなければなりません。
public static K<U, Answer> SelectMany<T, U, Answer>
(this K<T, Answer> m, Func<T, K<U, Answer>> k)
ですが、メソッドの本体はどういうものになるのでしょうか?戻り値は型 K<U, Answer>
でなければならないのですが、どうすれば正しい型の戻り値を作ることができるのでしょうか?
K
の定義を展開して考察しましょう。
- 戻り値の型
Func<Func<U, Answer>, Answer>
- mの型
Func<Func<T, Answer>, Answer>
- kの型
Func<T, Func<Func<U, Answer>, Answer>>
k
を型 T
の値に適用すれば型 K<U,Answer>
の値が得られますが、利用できる型 T
の値がありません。そこで、関数を生成することで戻り値の型を直接作りましょう。その関数は U
を Answer
にする関数を受け取ります。パラメータを c
としましょう。
return (Func<U,Answer> c) => ...
Bind
の戻り値の型が K<U,Answer>
になるためには、本体は Answer
型でなければなりません。おそらく、 m
は T
を Answer
にする関数に適用するのでしょう。そうすれば、その戻り値は、 Answer
型の値です。
return (Func<U,Answer> c) => m(...)
m
の呼び出しの内側の式は、 Func<T,Answer>
型でなければなりません。その型の値は存在しないので、型 T
のパラメータ x
を持つラムダを作ることで、そのような関数を生成します。
return (Func<U,Answer> c) => m((T x) => ...)
このラムダの本体は Answer
型でなければなりません。型 T
、 Func<U,Answer>
、そして Func<T,Func<Func<U,Answer>, Answer>>
の値はまだ使われていません。 k
を x
に適用します。
return (Func<U,Answer> c) => m((T x) => k(x)...)
結果は、Func<Func<U,Answer>,Answer>
型の値です。この結果を c
に適用します。
return (Func<U,Answer> c) => m((T x) => k(x)(c));
継続モナドは計算を裏返しにします。継続を生成するのに内包構文を用いることができます。
値 7
を使って継続を実行する計算を生成します。値 6
を使って継続を実行する別の計算へ、この計算を渡します。前の2つの継続の結果を合計した結果を使って継続を実行するさらに別の計算へ、この計算を渡します。最後に、'1'
を 'a'
に置き換える継続を、この結果に渡します。
var r = from x in 7.ToContinuation<int,string>()
from y in 6.ToContinuation<int,string>()
select x + y;
Console.WriteLine(r(z => z.ToString().Replace('1', 'a'))); // a3が表示される
継続モナドは、継続を生成するという力仕事をやってくれます。
モナドの魔法
増強された値を美しく合成するにはモナドが必要です。 Identity
、 Maybe
、そして IEnumerable
モナドはコンテナ型としてのモナドの力を示します。継続モナド K
はモナドが複雑な計算をどれほど容易に表現できるかについて示します。
この後も引き続きモナドでいろいろお楽しみください。その時までには、モナドがどんなことをやってくれるかが分かるでしょう。