matarillo.com

The best days are ahead of us.

FAIC モナド、パート7

2018-01-19 16:49:18

原文

Srinavasa Ramanujan

Srinavasa Ramanujan

By Konrad Jacobs (Oberwolfach Photo Collection, original location) [CC BY-SA 2.0 DE], via Wikimedia Commons

1992年、私はウォータールー大学で線形代数を学んでいた。当時は双対空間を理解できずもやもやしていた。そんなある夜、代数を数時間勉強してから寝た後で双対空間の夢を見た。夢から覚めると、双対空間の概念について明快で直観的に理解できていた。寝ている間に私の脳が考えを整理してくれたに違いない。不思議な体験だった。あんなことは一度きりだ。1 歴史上、突然ひらめいて複雑な問題が解けたという人は枚挙にいとまがない。夭逝した悲劇の数学者、シュリニヴァーサ・ラマヌジャンが語ったことには、彼は夢の中で膨大な数学の巻物を読み、その内容は正確かつ著しくオリジナリティのあるものであることが後から判明したそうだ。

もちろんそんな解決策が夢に現れることを待っていてもしょうがない: そんなことがいつ起こるかなんてわかりっこない。直観力は不確かなものだから、人は手ごわい問題を解決するためにもっと確かな技を磨いてきた: 再帰的な分割統治 だ。私たちは、再帰メソッドが問題を解くのと同じ方法で問題を解いているのだ。

現在の問題は自明だろうか?もしそうなら問題を解け。そうでなければ、現在の問題を1つ以上のより小さな問題に分割せよ。小さくなった問題を再帰的に解き、それらの解を 合成 して大きな問題の解とせよ。

今日のテーマは「合成」だ。合成とは、小さな問題の2つ以上の解を組み合わせて抽象化し、1つの大きな問題を解くというものだ。コンピュータープログラムを書くときには息を吸うように合成を使っているので、もう空気のようなものだ。いつでも周りにあるけれど、それについて改めて考えることはない。ここで、2つのプロパティを1つの演算で合成する例を見てみよう; 合成の結果は3番目のプロパティとなる:

public double Area
{
  get { return this.Length * this.Width; }
}

そしてもちろん、 Rectangle 型のようなものがあれば、それは角を表す2つの Point 型の値を合成したものだろうし、同様に Point 型は座標を表す2つの double 型の値を合成したものだろう。他も同じような感じだ。現代的で実用的なプログラミング言語は必ず、小さな問題の解を大きな問題の解に簡単に合成できるようにする機構を持っているものだ。

そんなわけで、C#プログラマーにはさまざまな合成の手段がたくさん用意されている。今日はその中からとても具体的な例を1つ説明しよう: __1つの引数を受け取ってvoidでない値を返す関数__の合成だ。これは最も基本的な合成の中の1つだ。2 説明のためにバカっぽい例を挙げるが、次のような関数があったとき:

static long Cube(int x) { return (long)x * x * x; }
static double Halve(long y) { return y / 2.0; }

いつでもそれら2つを合成して3つ目の関数を作ることができる:

static double HalveTheCube(int x) { return Halve(Cube(x)); }

プログラムを書くときの典型として、プログラムのテキストにはこういった合成が山のように書かれていて、その1つひとつは上のような1引数関数の合成よりはもっと複雑なものだろう。とはいえ、やろうと思えば関数合成を動的に行うこともできる。デリゲートを使えば:

Func<int, long> cube = x => (long)x * x * x;
Func<long, double> halve = y => y / 2.0;
Func<int, double> both = z => halve(cube(z));

そしてこんなメソッドを書いて合成することだって実際にできる:

static Func<X, Z> Compose<X, Y, Z>(
  Func<X, Y> f,
  Func<Y, Z> g)
{ 
  return x => g(f(x));
}

そしたらこうなる:

Func<int, long> cube = x => (long)x * x * x;
Func<long, double> halve = y => y / 2.0; 
Func<int, double> both = Compose(cube, halve);

もちろん実際にはこんなコードは書かないだろう。C#にすでにある関数合成の構文だって十分に便利なものだし。しかし論理的には、ある関数の戻り値を次の関数に食わせるようなプログラムを書くときに毎回やっているのはこういうことだ: 2つの関数を合成して3つ目の関数を作っているのと同じなんだ。

当たり前のことだが、合成するためには「内側」の関数の戻り値の型が「外側」の関数の引数の型に暗黙的に変換可能でないといけない。これでようやく本題に戻れる: 型に関するモナド・パターンの最後のルールだ。モナド的な型のインスタンスを返す「特別」な関数についてこれまで話してきた。以下のような関数を考える:

Func<int, Nullable<double>> log = x => x > 0 ? 
  new Nullable<double>(Math.Log(x)) : new Nullable<double>();
Func<double, Nullable<decimal>> toDecimal = y => Math.Abs(y) < decimal.MaxValue : 
  new Nullable<decimal>((decimal)y) : new Nullable<decimal>(); 
Func<int, Nullable<decimal>> both = Compose(log, toDecimal);

これは動かない。toDecimaldouble を受け取るのに、logNullable<double> を返すからだ。ではどうあるべきなのか?明らかなのは、log がnullを返したときは合成関数もnullを返してほしいし、そうでなければ元の値を toDecimal に渡してほしい。しかし、まさにそのように動く関数はすでにある: ApplySpecialFunctionだ! したがってモナド的な合成のヘルパーはこのように作成できる:

static Func<X, Nullable<Z>> ComposeSpecial<X, Y, Z>(
  Func<X, Nullable<Y>> f,
  Func<Y, Nullable<Z>> g)
{ 
  return x => ApplySpecialFunction(f(x), g);
}

そしたらこう書ける:

Func<int, Nullable<decimal>> both = ComposeSpecial(log, toDecimal);

ApplySpecialFunction ヘルパーメソッドによって、どんな関数でもモナド的な型に適用できる。実にすばらしい。でもそれだけじゃなくて、その型を返す任意の2関数を合成することもできる!

前回、モナド・パターンの最後のルールを導く予定だと書いた。そしてとうとうたどり着いた。最後のルールはこれだ: ApplySpecialFunction ヘルパーは、合成がきちんと動作することを保証しなければならない。コードで表すと:

Func<X, M<Y>> f = whatever;
Func<Y, M<Z>> g = whatever;
M<X> mx = whatever;
M<Y> my = ApplySpecialFunction(mx, f);
M<Z> mz1 = ApplySpecialFunction(my, g);
Func<X, M<Z>> h = ComposeSpecial(f, g);
M<Z> mz2 = ApplySpecialFunction(mx, h);

mz1mz2 は意味的に等しいことが要求される。ある値に f を適用し、続いて g を適用した結果は、先に fg を合成してから値に適用した結果と論理的に等しい。3

これでようやく、細かな注意点をすべて詰め終わったので、C#におけるモナド・パターンを正しく記述することができるようになった:

モナドとは、以下のようなジェネリック型 M<T> である:

  • ある T を受け取ってM<T> を返す生成機構が存在すること。それは次のようなシグネチャのメソッドが存在することで表した:
static M<T> CreateSimpleM<T>(T t)
  • 次に、元の型の値を受け取る関数を、その型のモナドに適用する方法が存在すること。それは次のようなシグネチャのメソッドが存在することで表した:
static M<R> ApplySpecialFunction<A, R>(
  M<A> monad, Func<A, M<R>> function)

最後に、どちらのメソッドも以下に示す モナド則 に従わなければならない:

  • 与えられたモナドのインスタンスに対し生成関数を適用した結果は、元のモナドのインスタンスと論理的に等しい。
  • ある関数があった時に、元の値に生成関数を適用してから関数適用した結果と、元の値に直接関数適用した結果は、論理的に等しいモナドのインスタンスとなる。
  • ある値に1つ目の関数を適用して、その結果に2つ目の関数を適用した結果と、1つ目の関数と2つ目の関数を合成して、その結果得られる3つ目の関数をある値に適用した結果は、論理的に等しいモナドのインスタンスとなる。

うへぇー!これでわかったでしょう?数週間前、私がモナド則から説明し始める代わりに、実例をもとにパターンを見出すやり方で連載記事を始めた理由が。

次回のFAIC では、これらの仕組みが伝統的にどう呼ばれているかを説明する予定だ。


ラマヌジャンのパスポート写真に関する情報はWikimedia Commonsにある。


インデックスへ戻る


  1. 残念なことに、双対空間に対する直観的な理解はもう忘れてしまった。この20年、一番簡単な線形代数より難しいことは使ってこなかったからだ。必要になれば思い出せるとは思うけれど、あの時の瞬間的なひらめきはもう戻ってこないだろうな。 ↩︎

  2. そりゃあ、2つの引数なしvoid関数を合成するのが一番簡単なのは明らかだ; void M() { A(); B(); } より簡単なものはないだろう。 ↩︎

  3. 繰り返すが、参照の同一性は必要じゃない。そうできるならそれでもいいけれど、必要なのは意味的な同一性だ。 ↩︎