Squirrelの関数を持ち上げる

前回の続きです。
Squirrelの関数をcurry化してどうすんのって話ですが、関数を持ち上げるのに使ってみます。 というよりそれをやりたくて必要になったのでcurryを書いたのでした。

関数を持ち上げるとは?普通の関数を文脈の中で作用する関数に変換することです。
例えば、前に書いたOptionは、成功(Some)かもしれないし失敗(None)かもしれない、という文脈を表します。
その中で作用する関数とはどういうものでしょうか。実際書いてみます。

function add(a, b) {
  return a + b;
}
local r5 = add(1, 2);  // r5 = 3

addM <- liftM(add);

local r6 = addM(Some(1), Some(2));  // r6 = Some(3)

local r7 = addM(Some(1), None);  // r7 = None

addは普通の関数ですが、liftM関数によって文脈を持った値に適用できるaddMに持ち上げられています。 そこにOptionの値を渡すと、両方成功の場合は成功の結果が返り、失敗が含まれると結果も失敗となります。

型を見てみると、addの型は(Scala風に書くと) (A, B) => CaddM(M[A], M[B]) => M[C] ですね。 よってここで欲しい関数であるliftMの型は ((A, B) => C) => (M[A], M[B]) => M[C] となります。 このような関数を定義できればいい訳です。

また文脈といっても色々ある訳ですが、ここではmapflatMapが適切に実装されているもののこととします。 適切な実装とかの詳しいことは略です。

さて、mapflatMapがあればこう書けますね。2引数関数用なので名前はliftM2とします。

// ((A, B) => C) => (M[A], M[B]) => M[C]
function liftM2(f) {
  local cf = curry2(f);
  return function (ma, mb) : (cf) {
    return ma.map(cf)
      .flatMap(mb.map.bindenv(mb));
  }
}

ここで前回作ったcurry2が出てきます。文脈の中の値に1個ずつ関数を適用していきたいので、そのためには関数がカリー化されている必要がある訳です。
最初からliftM2にカリー化された関数(A => B => C)を渡すことにしてもいいんですが、普通にSquirrelを書く上では普通の関数の方が書きやすいのでカリー化は内部でやることにしました。

さて、liftM2はカリー化した関数cfmap/flatMapを使って順にma,mbに適用する関数を返します。この部分です。

function (ma, mb) : (cf) {
  return ma.map(cf)
    .flatMap(mb.map.bindenv(mb));
}

最初のaddの例を使ってこの関数がちゃんと期待した型になっているか見てみます。 まずaddcurry2でカリー化されているのでcfは次のようになっているイメージです。

// 型はA => B => C
local cf = function (a) {
  function (b) : (a) {
    return a + b;
  }
}

そしてliftM2が返す関数の中では、まずmaの中身にmapcfを適用します。
先の例ではmaSome(1)を渡しているので、そう置き換えていくと

return ma.map(cf)
  .flatMap(mb.map.bindenv(mb));
// ↓
return Some(1).map(function (a) { /* 略 */ })
  .flatMap(mb.map.bindenv(mb));
// ↓
return Some(function (b) { return 1 + b; })
  .flatMap(mb.map.bindenv(mb));

と、こうなります。mapの結果、Someの中身がcfを部分適用した関数になっているのが分かると思います。 型で言えば Option[A]A => B => C でmapしたので、Option[B => C] になっています。
そしてflatMapで中身の関数にmb.mapを適用します。ここでmbSome(2)です。

// ↓
return mb.map(function (b) { return 1 + b; });
// ↓
return Some(2).map(function (b) { return 1 + b; });
// ↓
return Some(1 + 2);

はい。Some(1)Some(2)を渡してSome(3)が得られました。 確かにこの関数は (M[A], M[B]) => M[C] という型になっているようです。MOptionA,B,C は全部 integer ですね。例が悪かったですね。

ともあれ、引数2つのliftM2は出来たので次は引数3つを書きましょう。

// ((A, B, C) => D) => (M[A], M[B], M[C]) => M[D]
function liftM3(f) {
  local cf = curry3(f);
  return function (ma, mb, mc) : (cf) {
    return ma.map(cf)
      .flatMap(mb.map.bindenv(mb))
      .flatMap(mc.map.bindenv(mc));
  }
}

引数を増やしてcurry3を使ってflatMapを一段追加して…… liftM4も引数を増やしてcurry4を使ってflatMapを一段追加して……
これは抽象化できそうです。

まず文脈内の関数を文脈内の値に適用するap関数を用意します。

// (M[A => B], M[A]) => M[B]
local ap = function (mf, m) {
  return mf.flatMap(m.map.bindenv(m));
}

カリー化関数は引数の数をキーにしてテーブルにまとめておきます。

local curryN = {
  [1] = function (f) { return f; }
};
local rt = getroottable();
for (local i = 2; "curry" + i in rt; ++i) {
  curryN[i] <- rt["curry" + i];
}

引数1つの関数というのは既にカリー化されていると言えるので、curry[1]には恒等関数を入れておきます。

すると、liftMを以下のように定義できます。

function liftM(f) : (ap, curryN) {
  return function (...) : (f, ap, curryN) {
    local r = vargv[0].map(curryN[vargc](f));
    for (local i = 1; i < vargc; ++i) {
      r = ap(r, vargv[i]);
    }
    return r;
  }
}

liftMは関数fを引数にとり、そのまま可変長引数を取る関数を返します。 その関数は呼び出し時の引数の数に合わせてfをカリー化、map/apを使って文脈内の値に関数を適用していき最終的な値を返します。

使ってみます。

function product(a, ...) {
  local r = a;
  for (local i = 0; i < vargc; ++i) {
    r *= vargv[i];
  }
  return r;
}

productM <- liftM(product);

local r8 = productM(Some(2), Some(5), Some(9));  // r8 = Some(90)

local r9 = productM(Some(4), None);  // r9 = None

local r10 = productM(Some(1));  // r10 = Some(1)

productM(Some(1), Some(2), Some(3), Some(4), Some(5));  // Error! curry5がない

元が可変長引数を取る関数のproductMは、curryNが定義されている範囲内で同様に可変長引数を取る関数として扱えます。

またOption以外でもmap/flatMapが定義されていればよいので、例えばarrayをラップするListクラスを定義すればそのまま次のような計算に使えます。

local r11 = productM(List([2, 3]), List([4, 5, 6]));  // r11 = List([8, 10, 12, 12, 15, 18])

local r12 = productM(List([2, 3]), List([]), List([4, 5, 6]));  // r12 = List([])

非常に便利、なのですが…… 例によって使う側で型を合わせなければ実行時エラーになるのはどうしようもないです。