使用するライブラリ
javascriptは拡張性が高いのでライブラリひとつでガラッとコードの書き方が変わります。個人的にはこの辺を使ってコードを書くのが好み。
Matches.js is deprecated. Please check out sparkler, a native pattern matching engine built using sweet.js macros. It does everything matches.js does and more, except it isn't a hideous hack!
Matches.jsが非推奨っぽいですが、sparklerがsweet.jsを使っているためマクロ変換が必要なので、個人的にはMatches.jsを使いたいんですよね～
クイックソートを書く
n行で書くクイックソートなんて話題がたまに出ますが、ネタを書く側からすると出しやすいんですよね。
で、コード。
var _ = require('lodash');
var pattern = require('matches').pattern;
var sort = pattern({
'[]' : function() { return []; },
'[x]' : function(x) { return [x]; },
'[x, ...xs]' : function(x, xs) {
var lt = _.filter(xs, function(n) { return n < x; });
var gt = _.filter(xs, function(n) { return n > x; });
return sort(lt).concat([x]).concat(sort(gt));
}
});
console.log(sort([5,3,2,7,9,8,6,4,1]));
あまり短くないですが、パターンマッチを使うと抽象度が一段上がって理解しやすいと思います。
解説
処理は単純なので主にmatches.jsの説明です。
var pattern = require('matches').pattern;
今回のキモとなるpattern関数です。引数にパターンと実行すべき関数の組を持つオブジェクトを指定します。
で、そのパターンですが、
'[]' : function() { return []; },
このように文字列で指定します。上記の例は、「空の配列」というパターンが来たら、空の配列を返す関数を実行しなさいという指定。
'[x]' : function(x) { return [x]; },
これは、「要素が１つの配列」というパターンが来たら、取り出した要素xを配列にして返す関数を実行しなさいという指定。
最後はちょっと長いので、まずはパターン部分
'[x, ...xs]' : function(x, xs) {
「...xs」という箇所が見慣れない形ですが、ここでは配列と考えておいて問題ないです。パターン全体の意味としては、配列を先頭要素と残りに分割して、先頭要素はx、残りの部分配列はxsとするって感じです。
ここまで来たら、あとはクイックソートのアルゴリズムです。
var lt = _.filter(xs, function(n) { return n < x; });
var gt = _.filter(xs, function(n) { return n > x; });
return sort(lt).concat([x]).concat(sort(gt));
配列を先頭要素xより小さいものと大きいものに分割して、分割したそれぞれを更にソートし、ソート済み配列(小さい方)と分割に使った要素xとソート済み配列(大きい方)を連結すれば配列全体のソートが完了となります。
蛇足
記事の趣旨はパターンマッチでコードがすっきり書けるぜーってだけなんですが、クイックソートのアルゴリズムが手抜き(データに左右されまくる)とか、パターンマッチの[...xs]は配列のコピーを作るので、パフォーマンスを考えたら
'xs@Array' : function(xs) {
var x = xs[0];
// 以下略
とした方が無駄がないんじゃないかと思いますが、見た目重視ということで…
あと、著者がjavascriptのド素人なので、酷い間違いがあるかもしれません。