Days on the Moon

「いやなブログ - JavaScript でソートアルゴリズムを可視化」より。何も考えずに再帰処理のクイックソートの様子を逐次描画しようとするとこうなります。

function quickSort(data, begin, end, log) {
  if (begin >= end) return data;

  var pivotPos = begin;
  var pivot = data[pivotPos];

  for (var i = begin + 1; i < end; i++) {
    if (data[i] < pivot) {
      var temp = data[i];
      data[i] = data[pivotPos + 1];
      data[pivotPos + 1] = data[pivotPos];
      data[pivotPos] = temp;
      pivotPos++;
    }
  }

  log(data);

  quickSort(data, begin, pivotPos, log);
  quickSort(data, pivotPos + 1, end, log);
  return data;
}

var array = [9, 5, 7, 3, 2, 4, 0, 1, 6, 8];
quickSort(array, 0, array.length, print);
// 5,7,3,2,4,0,1,6,8,9
// 3,2,4,0,1,5,7,6,8,9
// ...
// 0,1,2,3,4,5,6,7,8,9

しかし、ブラウザ上でアニメーション表示するためには、setTimeout などのタイマーを使う必要があります。ところが、タイマーを使って処理を分けると、その処理が終わった後で元の処理に戻ることができません。上のクイックソートでいうと、データの前半を並び替えた後、戻って後半を並び替えないといけないため、そのままではアニメーション表示ができないのです。

ではどうするか。戻らなくてはならないのが問題ならば、戻らなければいいのです。呼び出し先から戻って続きの処理をやるのではなく、続きの処理 (継続) も呼び出し先に丸投げしてしまいましょう。JavaScript ではクロージャが使えるので、続きの処理をまとめたクロージャを引数として渡すことができます。このような書き方を継続渡しスタイル (CPS, continuation passing style) というそうです。「ヒビノキロク - Javascriptで継続渡し」を参考に上のクイックソートを継続渡しスタイルに書き換えてみます。

function quickSortCPS(data, begin, end, log, cont) {
  if (begin >= end) return cont(data);

  var pivotPos = begin;
  var pivot = data[pivotPos];

  for (var i = begin + 1; i < end; i++) {
    if (data[i] < pivot) {
      var temp = data[i];
      data[i] = data[pivotPos + 1];
      data[pivotPos + 1] = data[pivotPos];
      data[pivotPos] = temp;
      pivotPos++;
    }
  }

  log(data);

  return quickSortCPS(data, begin, pivotPos, log,
    function (partiallySortedData) {
      return quickSortCPS(partiallySortedData, pivotPos + 1, end, log,
        function (entirelySortedData) {
          return cont(entirelySortedData);
        });
    });
}

function nop() {}
quickSort(array, 0, array.length, nop, print);
// 0,1,2,3,4,5,6,7,8,9

return 文に式が指定されていますが、この返り値は意味を持ちません。処理結果は関数呼び出しの返り値として受け取るのではなく、継続として渡したクロージャが引数として受け取ります。

さて、ここまで来れば後は簡単です。返す値に意味がない、すなわち戻る必要がなくなったのですから、大手を振ってタイマーが使えます。Gecko では setTimeout の引数として関数実行時の引数も渡せるので、以下のように書き換えられます。

function quickSortCPSWithTimer(data, begin, end, interval, log, cont) {
  ...

  return setTimeout(quickSortCPSWithTimer, interval,
    data, begin, pivotPos, interval, log,
    function (partiallySortedData) {
      return setTimeout(quickSortCPSWithTimer, interval,
        partiallySortedData, pivotPos + 1, end, interval, log,
        function (entirelySortedData) {
          return cont(entirelySortedData);
        });
    });
}

function plot(data) {
  ...
}
quickSortCPSWithTimer(array, 0, array.length, 20, plot, nop);

これで 20 ミリ秒ごとにソート途中のデータがプロットされることになります。実際は IE だと setTimeout で引数を渡せないので、Gecko の setTimeout と同じ動作をする関数 doLater を使います。

function doLater(func, interval) {
  var args = Array.prototype.slice.call(arguments, 2);
  return setTimeout(function () { func.apply(this, args); }, interval);
}

以上をまとめた再帰的なクイックソートの可視化です。継続渡しとは関係ありませんが、元記事のものと比べると描画がかなり軽快になっていると思います。

なお、Shibuya.js Technical Talk #2 で「ActionScript でクロージャ、継続渡し」を発表なさったとおる。さんが、「まるごとJavaScript & Ajax! Vol.1」で「FlashのActionScriptで関数型風プログラミング」という記事を書いています。継続渡しについてもいろいろと解説してくださるようで、読むのを楽しみにしています。と自分の宣伝もかねて :-)

おまけで非破壊的なクイックソートとその継続渡しスタイル版。「maoeのブログ - 末尾再帰のクイックソート」で見た Haskell のクイックソートを基にしたものです。短いけど何かごちゃっとしてしまいました。

function quickSortND(data) {
  if (!data.length) return [];
  var pivot = data[0], lt = [], gte = [];
  for (var i = 1; i < data.length; i++)
    ((data[i] < pivot) ? lt : gte).push(data[i]);
  return quickSortND(lt).concat([pivot], quickSortND(gte));
}

function quickSortND_CPS(data, cont) {
  if (!data.length) return cont([]);
  var pivot = data[0], lt = [], gte = [];
  for (var i = 1; i < data.length; i++)
    ((data[i] < pivot) ? lt : gte).push(data[i]);
  return quickSortND_CPS(lt, function (sortedLt) {
    return quickSortND_CPS(gte, function (sortedGte) {
      return cont(sortedLt.concat([pivot], sortedGte));
    });
  });
}

quickSortND_CPS(array, print);
// 0,1,2,3,4,5,6,7,8,9