メニュー

Blog
News
.NET

Misc

モナドの驚異

Wes DyerのBlog “Yet Another Language Geek”に、モナドに関する記事が投稿されていたので、訳してみる。

モナドの驚異

原文

「継続」という単語が目をどんよりと曇らせる原因になるならば、「モナド」という語は精神的な麻痺を引き起こします。これがおそらく、モナドに比較的無害な名前を発明しようとし始めた人がいる理由です。

この所、モナドはプログラミング言語論の有名人です。モナドはいくつものブログの表紙を飾り、果物箱から恋愛まで、さまざまなものと比較されていました。オタクたちは至る所で、モナドを理解する経験が心地よい痛みを伴う精神的な感覚を引き起こすと叫んでいます。

継続と同様に、モナドは聞こえるよりも単純ですし、多くの状況で非常に役立ちます。実際、プログラマーは一汗かくことさえなく、暗黙のうちに一般的なモナドを使っているいろいろな言語でコードを書いています。

モナドは注目を手に入れているというのに、なぜ、私がさらにもう一度モナドの説明を書くのでしょうか？普段のいくつかの出来事に対して比較するのではなく、そして、理解へ至る私の旅行を時系列で記録するのでもなく。私はモナドが必要なのでモナドを説明するのです。モナドは、いくつもの言語と文脈でエレガントにプログラミング上の問題を解決します。

モナドを導入する

モナドは圏論から来ています。Moggiは計算の意味論の分析を支援するため、コンピューターサイエンスの専門家たちにそれらを紹介しました。ワドラーは優れた論文、関数型プログラミングの本質で、モナドがコンピュータープログラムにおいて、通常は値よりもむしろ拡大された値に作用する関数を組み立てるために役立つことを示しました。モナドは厄介な一味――IO、並列性、例外と外部関数呼び出し――に取り組むプログラミング言語Haskellの重要な部分になりました

モナドは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;
}

1. 左単位元

Identity.Compose(f) = f

2. 右単位元

f.Compose(Identity) = f

3. 結合法則

f.Compose(g.Compose(h)) = (f.Compose(g)).Compose(h)

しばしば、値では十分ではありません。構築された型は値を拡大します。型 IEnumerable<T> は遅延評価される型 T の値のリストを表現します。型 Nullable<T> は、型 T の存在しないかもしれない値を表現します。型 Func<Func<T, Answer>, Answer> は関数を表現します。そして、それは1つの T を受け取って Answer を返す継続を与えられると、 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つの法則を満たさなければなりません：

1. 左単位元

Bind(Unit(e), k) = k(e)

2. 右単位元

Bind(m, Unit) = m

3. 結合法則

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を使うことができます、おそらく、それは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 モナドが値をラップしたモナド・コンテナ型の例です。値または存在しない値を含むために定義を変えるならば、それは 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 はモナドが複雑な計算をどれほど容易に表現できるかについて示します。

この後も引き続きモナドでいろいろお楽しみください。その時までには、モナドがどんなことをやってくれるかが分かるでしょう。

Last Update: 2012-01-03 16:33:09