モナドの驚異

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 はモナドが複雑な計算をどれほど容易に表現できるかについて示します。

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

matarillo.com

The best days are ahead of us.

モナドの驚異

2019-03-22 07:06:19