「JavaScriptでの非同期関数合成」を継続モナドで

お題:

複数個の関数があって、関数を呼び出した結果を使って関数を呼び出して…っていうのを1個の関数にします。

JavaScriptでの非同期関数合成 - monjudoh’s diary

関数の形を見てみます。

// 1を足す
function add1(callback,arg){
  callback(arg+1);
}

コールバック関数を渡して、戻り値ではなくコールバック関数を呼び出してもらう事で結果を取得する……これって「CPS(継続渡し形式)」！CPSなら分かるわ！(本当か？)

参考にしたサイト:

• http://www.h4.dion.ne.jp/~unkai/js/js12.html
• http://practical-scheme.net/docs/cont-j.html
• JSDeferredで考えるモナド - JavaScriptで遊ぶよ - g:javascript
• Haskellの継続モナド(Continuation Monad)を理解するポイント - よくわかりません
• http://d.hatena.ne.jp/terazzo/20110723/1311447111

ということで継続モナドを使って書いてみる。

継続モナド

例によって「モナドのすべて」を見ながら写経します。

// 継続モナド
function Cont(f) { // f: a -> r -> r
   this.run = f;
}
// a.k.a. '>>='
Cont.prototype.bind = function(f) { // f: a -> Cont r b
   var run = this.run;
   return new Cont(function(k) { return run(function(a) { return f(a).run(k) }) });
}
// a.k.a. 'return'
Cont.unit = function(a) {
   return new Cont(function(k) { return k(a) });
}
Cont.callcc = function(f){ // f: a -> Cont r b -> Cont r a
   return new Cont(function(k) { return f(function(a) { return new Cont(function(x) { return k(a) }) }).run(k) })
}

「return」は「unit」に、「>>=」は「bind」に名前を変えています。

使い方の前に、ちょっとおさらいをしてみる。
例として、「数を2乗して印字する」という処理を考える。
通常の書き方では、たとえば、「引数の値を2乗して戻す」関数を用意し、その戻り値を取得して印字する、というのが考えられる。

function square(x) { return x * x }
log.console(square(3)); // 9

CPSというのは、値を戻り値で返すのではなく、用意した別の関数を呼び出してもらうことで結果を受け取る方式のこと。

function squareCps(x, cont) { cont(x * x) }
squareCps(3, console.log); // 9

継続モナドというのは、このCPSの関数を複数組み合わせて使用しやすいようにしたもの、と考えればいいだろう。

// 上の方で定義したContを使うよ
var squareCont = function (x) { return Cont.unit(x * x) }
squareCont(3).run(console.log); // 9

では、実際に複数組み合わせてみる。「3に1を足して2乗して印字」という処理は次のように書ける。

var add1Cont = function (x) { return Cont.unit(x + 1) }
// 「3に」「1を足して」「2乗して」「印字」
Cont.unit(3).bind(add1Cont).bind(squareCont).run(console.log); // 16
// ↑と↓は同じ意味
// add1Cont(3).bind(squareCont).run(console.log);

bindという関数*1を使うことで、数を受け取ってContを返すような関数たちをつなげて使うことができる。

これの何が嬉しいの？というと……単体で使っても多分あんまり意味なそう。とりあえず、処理を中断したり、ショートカットしたりできます。
例えば、一連の処理の途中で「逆数を取る」という処理が挟まっていて、その時点で0だったらエラーにしたい場合は、次のように書ける。

var n = -1;
Cont.callcc(function(exit) {
   // 数に1を足して逆数を取って二乗する。但し逆数を取る際に0の場合はエラー
   return Cont.unit(n)
      .bind(add1Cont)
      .bind(function(x) { return (x != 0) ? Cont.unit(1.0 / x) : exit("*** error: Division by zero.") })
      .bind(squareCont);
}).run(console.log); // "*** error: Division by zero."

Cont.callccで渡す関数の引数として渡されたexitという関数を呼ぶことで、以降の処理をスキップして、console.logにエラーメッセージを渡している。

関数の合成

上で見たように、値を取ってContを返すような関数は、bindで連結することで連続して適用できることは分かった。でもこれって関数合成！(ｷﾘｯと言い切るにはちょっと回りくどいような？
たとえば、add1ContとsquareContを連続して適用するような関数add1squareContを書こうとすると、

var add1squareCont = function(x) { return Cont.unit(x).bind(add1Cont).bind(squareCont) }

いちいちfunctionを書くのがまどろっこしい。

そこで、「値を取ってモナド(この場合はCont)を返すような関数」*2同士を直接合成できるようにする仕組みで、Kleisliというのがあるので、ちょっと真似してみる。
Kleisliについては、この辺参照

• Modegramming Style: 関数型とデータフロー(4)
• ひなたねこ: Kleisli

深遠な数学的背景があるそうですが、よくわかってないので、自分も「KleisliはA => M[B]の形の関数で、合成ができて、☆という印象。」です。

では実装。
https://github.com/scalaz/scalaz/blob/master/core/src/main/scala/scalaz/Kleisli.scalaから部分的にパクってくる。

// 「>=>」のみの手抜き実装
function Kleisli(f){
   this.apply = f;
}
Kleisli.prototype = {
   compose: function(k) {
      var apply = this.apply;
      return new Kleisli(function(a) { return apply(a).bind(function(b){ return k.apply(b) }) });
   }
}

「>=>」*3の名前をcomposeにしています。元々composeという関数があるので紛らわしいのですが、「>=>」の方です。

使ってみる。

// Kleisli化
var add1ContK = new Kleisli(add1Cont);
var squareContK = new Kleisli(squareCont);

// 合成する
var add1squareContK = add1ContK.compose(squareContK);

add1squareContK.apply(3).run(console.log);

functionを書かなくても処理同士を連結できるようになった。

お題のサンプルを実装してみる

「コールバックと数字を引数に取って何かの処理をしコールバックを呼ぶ関数」を合成可能し、合成した結果も同じ形になるようにしたい。

// 1を足す
function add1(callback,arg){
  callback(arg+1);
}
// 2をかける
function mul2(callback,arg){
  callback(arg*2);
}

function log(result){
  console.log(result);
}

関数の型や順番を合わせる為に、変換関数を用意する。

// make fun Cont-resultic
function inCont(f) {
   return function(a) { return new Cont(function(callback) { return f(callback, a) }) };
}
// make fun composable
function composable(f) { return new Kleisli(inCont(f)); };

これを使うと、「4をadd1してmul2してadd1した結果を印字する」処理はこう書ける。

var add1K = composable(add1);
var mul2K = composable(mul2);

add1K.compose(mul2K).compose(add1K).apply(4).run(log); // 11

「.apply(4).run(log)」の部分が……。元の関数と型が異なっているので、ここも変換して合わせる。

function kleisi2fun(kleisi) {
   var fun = function(k, a) { return kleisi.apply(a).run(k) };
   fun.apply = function(a) { return kleisi.apply(a) };
   fun.compose = function(k){ return kleisi2fun(kleisi.compose(k)) };
   return fun;
}
// make fun composable
function composable(f) { return kleisi2fun(new Kleisli(inCont(f))); };

合成もできるし、関数としても呼べるようになった。

var add1K = composable(add1);
var mul2K = composable(mul2);

add1K.compose(mul2K).compose(add1K)(log, 4); // 11

// 合成したものをさらに合成
var composed = composable(add1).compose(composable(mul2));
composed.compose(composed)(log, 4);  // 22

JavaScriptでObjectを関数に偽装する方法が分からなかったので関数の方をオブジェクトに偽装してみたけど、結構コスト高そう。

Scalazでも書いてみた

練習なので。

import scalaz._,Scalaz._

sealed trait Cont[R, A] extends NewType[(A => R) => R] {
   val value: (A => R) => R
   def run = value

   def flatMap[B](f: A => Cont[R, B]): Cont[R, B] = new Cont[R, B] {
      val value = (k: B => R) => Cont.this.value(a => {f(a).value(k)})
   }
}

object Cont {
   def cont[R, A](f: (A => R) => R) = new Cont[R, A] {
      val value = f
   }
   implicit def ContPure[R]: Pure[PartialApply1Of2[Cont, R]#Apply] =
      new Pure[PartialApply1Of2[Cont, R]#Apply] {
         def pure[A](a: => A) = new Cont[R, A] {
            val value = (k: A => R) => k(a)
         }
      }
   implicit def ContBind[R]: Bind[PartialApply1Of2[Cont, R]#Apply] =
      new Bind[PartialApply1Of2[Cont, R]#Apply] {
         def bind[A, B](r: Cont[R, A], f: A => Cont[R, B]) = r flatMap f
      }

/* 今回は使わないけど、↓こんな感じ？*/
/*
   implicit def ContFunctor[R]: Functor[PartialApply1Of2[Cont, R]#Apply] =
      new Functor[PartialApply1Of2[Cont, R]#Apply] {
         def fmap[A, B](r: Cont[R, A], f: A => B) = new Cont[R, B] {
            val value = (k: B => R) => r.value(k <<< f)
         }
      }
   import Monad._
   implicit def ContMonad[R]: Monad[PartialApply1Of2[Cont, R]#Apply] =
      monad[PartialApply1Of2[Cont, R]#Apply](ContBind, ContPure)
*/

   def callcc[R, A, B](f: (A => Cont[R,B]) => Cont[R, A]) = new Cont[R, A] {
      val value = (k: A => R) => f(a => new Cont[R, B] {
         val value = (x: B => R) => k(a)
      }).value(k)
   }
}

使う側:

import scalaz._,Scalaz._
import Cont._

      // 1を足す
      def add1(x: Int) = (x + 1).pure[PartialApply1Of2[Cont, Unit]#Apply]
      // 2をかける
      def mul2(x: Int) = (x * 2).pure[PartialApply1Of2[Cont, Unit]#Apply]
      // log
      val log = (arg: Int) => println(arg)

      val add1ContK = kleisli[PartialApply1Of2[Cont, Unit]#Apply, Int, Int](add1)
      val mul2ContK = kleisli[PartialApply1Of2[Cont, Unit]#Apply, Int, Int](mul2)
      (add1ContK >=> mul2ContK) apply(4) run(log) // 10

      val composed = add1ContK >=> mul2ContK
      (composed >=> composed) apply(4) run(log) // 22

ScalazにはContモナドは無いですが、Freeあるから要らない的な意見もあるようですが、どうやってFreeで書けば良いのか良くわからない。

*1:とりあえずFunction.prototype.bindとは関係ないよ

*2:M-resulticな関数というらしい。cf: http://d.hatena.ne.jp/m-hiyama/20060421/1145613700

*3:Kleisli composition operatorと言うらしい