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) => C
、addM
は (M[A], M[B]) => M[C]
ですね。
よってここで欲しい関数であるliftM
の型は ((A, B) => C) => (M[A], M[B]) => M[C]
となります。
このような関数を定義できればいい訳です。
また文脈といっても色々ある訳ですが、ここではmap
とflatMap
が適切に実装されているもののこととします。
適切な実装とかの詳しいことは略です。
さて、map
とflatMap
があればこう書けますね。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
はカリー化した関数cf
をmap/flatMap
を使って順にma
,mb
に適用する関数を返します。この部分です。
function (ma, mb) : (cf) { return ma.map(cf) .flatMap(mb.map.bindenv(mb)); }
最初のadd
の例を使ってこの関数がちゃんと期待した型になっているか見てみます。
まずadd
がcurry2
でカリー化されているのでcf
は次のようになっているイメージです。
// 型はA => B => C local cf = function (a) { function (b) : (a) { return a + b; } }
そしてliftM2
が返す関数の中では、まずma
の中身にmap
でcf
を適用します。
先の例ではma
にSome(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
を適用します。ここでmb
はSome(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]
という型になっているようです。M
は Option
、A,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([])
非常に便利、なのですが…… 例によって使う側で型を合わせなければ実行時エラーになるのはどうしようもないです。