FAIC モナド、パート12

2018-01-19 17:29:18

いやはや、この連載は予想以上に長引いてしまった。圏論のところまでなんとかたどり着きたかったんだけど、あきらめてLINQだけ説明して終わりにしよう。圏論の基礎についてはいつか連載するかも、しないかも。

すでに何度か説明したように、SelectMany はシーケンスモナドのbind 操作なんだけれど、IEnumerable<T> の SelectMany 拡張メソッドにはもちろんオーバーロードがいくつか存在する。bind に相当するやつは前回説明したように: ¹

public static IEnumerable<R> SelectMany<A, R>(
  this IEnumerable<A> items, 
  Func<A, IEnumerable<R>> function)
{
  foreach(A outer in items)
    foreach(R inner in function(outer))
      yield return inner;
}

なので、次のようなコードを書けば、

from outer in items
from inner in function(outer)
select inner

こんな呼び出しに変換されるんじゃないかと思うかもしれない。

items.SelectMany(outer=>function(outer))

実際にはこうはならない。

どうしてだろうか？それは、最後のselectのところでも outer がスコープ内にいてほしいからだ！

from outer in items
from inner in function(outer)
select new { outer, inner }  // outer はまだスコープ内にいるべき！

2つのパラメータを同時にスコープ内に入れるにはどうすればいいだろうか ヒントは、ここで起こっているのはある種の 入れ子になった 処理だということだ。今、unit 関数が拡張メソッドになっているものとしよう: ²

static IEnumerable<T> Singleton<T>(this T t) 
{ 
  yield return t; 
}

そうすると、上のクエリーは入れ子になった2つの SelectMany で表せる！

items.SelectMany(
  outer => function(outer).SelectMany( 
    inner => new { inner, outer }.Singleton() ) )

もちろん内側の SelectMany をもっと効率よく実装できることはわかっている; Select だけでいい。³

items.SelectMany(
  outer => function(outer).Select( 
    inner => new { outer, inner }) )

さて、これでクエリ式の構文にとてもよく似た構造ができあがった。上のクエリ式をC#コンパイラが実際に変換したコードはこれで合っているんだろうか？

違う。このコードはプレリリース版のLINQが当初生成していたものだが、これは破棄された。入れ子になったラムダ式がパフォーマンスに悪影響を与えることが分かったからだ。次の例を考えてみてほしい:

from a in items
from b in f(a)
from c in g(a, b)
from d in h(a, b, c)
select new { a, b, c, d }

このコードはこんな風に変換されることになっていた。

items.SelectMany(
  a => f(a).SelectMany(
    b=> g(a, b).SelectMany(
      c => h(a, b, c).Select(
        d => new {a, b, c, d}))));

エレガントで美しい。しかし コンパイル時の解析が超大変 なのだ。数年前にブログに少し書いたことがあるが、深さO(n) で入れ子になったラムダ式があり、それぞれのラムダ式がオーバーロードを解決する際にメソッドの候補が O(m) 個あったとすると、最悪の計算量が O(mn) になってしまう; あの投稿はLINQを開発していたときに発見したことを元に書いたものだ。私が示したシナリオは、この問題が 少なくとも NP困難であることを示している。⁴

こんなスカした言い方はやめよう; やってみて分かったのは、 入れ子が8つか9つぐらいの深さになると、どうしてもコンパイラとIDEが無期限にハングして、アドレス空間が全部ぶっ壊れてしまう が、これはどうにもしょうがないということだ。これをなんとかしなきゃならないのは明らかだった。そこでやったことは問題を2つに分割することだった。1つ目は単純なケースだ; もしクエリーがこんなだったら:

from inner in items
from outer in function(items)
select projection(inner, outer)

こう変換される。

items.SelectMany( 
  inner => function(items), 
  (inner, outer) => projection(inner, outer)

実装はこんな感じ。

public static IEnumerable<C> SelectMany<A, B, C>(
  this IEnumerable<A> items,
  Func<A, IEnumerable<B>> function,
  Func<A, B, C> projection) 
{
  foreach(A outer in items)
    foreach(B inner in function(outer))
      yield return projection(outer, inner);
}

結構効率的だ。

複雑なケースは、2つの from 句の直後に select 以外のものが来るシナリオだ。そのようなケースでは、ラムダの入れ子が深くなるのを避けるために、C#コンパイラは「透過識別子」と匿名型を使ってもっと複雑な変換を行う。この件の詳細を説明し始めるとどんどん脱線してしまう; 連載を片付けてしまいたいのに。透過識別子の話は別の機会にしよう。

閑話休題、一般的なモナドの話に戻そう。モナド M<T> と拡張メソッドがあるとしよう:

static M<T> Unit<T>(this T item) 
{ ... }
static M<R> Bind<A, R>(
  this M<A> monad, 
  Func<A, M<R>> function) 
{ ... }

このモナドの増幅機構に関する知識 がなくても、LINQに必要な SelectMany 拡張メソッドを定義できる:

static M<C> SelectMany<A, B, C>(
  this M<A> monad, 
  Func<A, M<B>> function,
  Func<A, B, C> projection)
{
  return monad.Bind(
    outer => function(outer).Bind(
      inner => projection(outer, inner).Unit()));
}

もちろんその機構について何か知っているのであれば、たとえばシーケンスモナドと同じように、もっとうまい定義もできる。しかしこの定義で十分だと示すために、このままやってみよう。

struct Maybe<T> 
{
  public static Maybe<T> Null = default(Maybe<T>);
  public bool HasValue { get; private set; }
  private T value;
  public T Value 
  {
    get
    {
      if (!HasValue) throw new Exception();
      return value; 
    }
  }
  public Maybe(T value) : this()
  { 
    this.HasValue = true;
    this.value = value;
  }
  public override string ToString()
  {
    return HasValue ? Value.ToString() : "NULL";
  }
}
static class Extensions
{
  public static Maybe<T> Unit<T>(this T value) 
  { return new Maybe<T>(value); }
  public static Maybe<R> Bind<A, R>(
    this Maybe<A> maybe,
    Func<A, Maybe<R>> function)
  {
    return maybe.HasValue ? 
      function(maybe.Value) :
      Maybe<R>.Null;
  }
  public static Maybe<C> SelectMany<A, B, C>(
    this Maybe<A> maybe, 
    Func<A, Maybe<B>> function,
    Func<A, B, C> projection)
  {
    return maybe.Bind(
      outer => function(outer).Bind(
        inner => projection(outer, inner).Unit()));
  }
  public static Maybe<short> AsSmall(this int x)
  {
    return 0 <= x &amp;&amp; x <= 100 ? 
      ((short)x).Unit() : 
      Maybe<short>.Null;
  }
  public static Maybe<short> QuerySyntax(this Maybe<int> maybe)
  {
    return from outer in maybe
           from inner in outer.AsSmall()
           select inner;
  }
}
class P
{
  static void Main()
  {
    System.Console.WriteLine(1.Unit().QuerySyntax());
    System.Console.WriteLine(1000.Unit().QuerySyntax());
    System.Console.WriteLine(Maybe<int>.Null.QuerySyntax());
  }
}

そして想定通り、このクエリー内包は AsSmall 関数をMaybeモナドにバインドする。最初の呼び出しでは (short) 1 が得られるし、２番目と３番目の呼び出しではnullになる。ふう。６週にわたる蓄積の結果が出たのが嬉しい。

さて、まるっと全体の最終結論は？

１点目: モナド・パターンは型を「増幅」するという、びっくりするほど一般的なパターンであり、元の型のインスタンスに対して関数を適用するという能力は維持されている。

２点目: その能力のおかげで、「バインド」操作は高階プログラミングにおける十徳ナイフとなっている。C# と VB の開発チームは、unit操作とbind操作の組み合わせだけでLINQを作ることだって可能だった; その結果は、実際にわれわれが作ったような、最適化された特殊目的のヘルパー関数ほど効率的にはならなかっただろうが、実装は可能だ。

３点目: C# と VB のLINQはひとつのモナド、すなわちシーケンスモナドを使うときだけとても便利になるように設計されている。しかしすでに見たように、LINQの「複数選択(select many)」の文法は、実際には既存のモナド的ワークフローに新しいワークフローを結合するための遠回りな道にすぎない。

やばいな……これで終わりにすると、キッパリ言ったばかりなのに……スマン、ありゃウソだった。 次回のFAIC は、私の元同僚であるStephen Toubがタスク・コモナドについて少し話してくれる。

インデックスへ戻る

エラーチェックは説明のため省いた。 ↩︎
分かっている。どんな型でも動く拡張メソッドを書いてしまうのは最悪のスタイルだ。でも教育の意味でも構文的にも便利だから、本エピソードでは何度か使う。 ↩︎
この連載の前の方で言及したように、SelectMany と unit 操作で Select を実装できるけど、もちろん実際には性能の問題によりそうしなかった。 ↩︎
-SAT問題の解探索と等価という意味で、これは少なくともNP困難だ; C#のオーバーロード解決が実際に3-SAT問題より難しいということはないんじゃないかと思う。たとえば、それが決定不能であるべきだとする理由も思いつかないが、断言する根拠も持ち合わせていない。 ↩︎

matarillo.com

The best days are ahead of us.

FAIC モナド、パート12

2018-01-19 17:29:18