JavaScript で List モナド - Monadic - なんとなくな Developer のメモ

Monadic は JavaScript 用のモナドライブラリです。

今回はこの Monadic を使って、以前（id:fits:20120912, id:fits:20120930）に Scalaz や Functional Java で実装したナイト移動の List モナド処理 *1 を JavaScirpt で実装してみました。

Monadic 0.0.5
Node.js v0.8.18

サンプルソースは http://github.com/fits/try_samples/tree/master/blog/20130120/

Monadic のインストール

npm install monadic でインストールするか、以下のように package.json の dependencies に monadic の設定を追加して npm install しておきます。

package.json

{
  "name": "monadic-list-sample",
  "version": "0.0.0",
  "dependencies": {
    "monadic": "*"
  }
}

実行例

> npm install

3手版

3手先のナイトの移動位置を全て列挙する処理と3手後に指定の終了位置に到達するか否かを判定する処理を実装します。

Monadic でバインド処理 *2 を行うには mbind を使います。List モナドは require('monadic').list() で取得できます。

3手版 move_knight.js

var monadic = require('monadic');
var listM = monadic.list();

// ナイトの次の移動先を列挙
var moveKnight = function(p) {
    return [
        {c: p.c + 2, r: p.r - 1}, {c: p.c + 2, r: p.r + 1},
        {c: p.c - 2, r: p.r - 1}, {c: p.c - 2, r: p.r + 1},
        {c: p.c + 1, r: p.r - 2}, {c: p.c + 1, r: p.r + 2},
        {c: p.c - 1, r: p.r - 2}, {c: p.c - 1, r: p.r + 2}
    ].filter(function(t) {
        return (1 <= t.c && t.c <= 8 && 1 <= t.r && t.r <= 8);
    });
};

// 3手先の移動位置を列挙（重複あり）
var in3 = function(start) {
    return listM.mbind(
        listM.mbind(
            // 下記の listM.mbind(・・・) は moveKnight(start) でも可
            listM.mbind(
                [start], 
                moveKnight
            ),
            moveKnight
        ),
        moveKnight
    );
};

console.log(in3({c: 6, r: 2}));

// 指定位置に3手で到達できるか否かを判定
var canReachIn3 = function(start, end) {
    return in3(start).some(function(p) {
        return (p.c == end.c && p.r == end.r);
    });
};

console.log(canReachIn3({c: 6, r: 2}, {c: 6, r: 1}));
console.log(canReachIn3({c: 6, r: 2}, {c: 7, r: 3}));

実行結果は以下の通り。

3手版の実行結果

> node move_knight.js
[ { c: 8, r: 1 },
  { c: 8, r: 3 },
  { c: 4, r: 1 },
  { c: 4, r: 3 },
  ・・・
  { c: 3, r: 4 },
  { c: 3, r: 8 } ]
true
false

do 記法 3手版

上記サンプルの in3 の処理を Monadic の do 記法を使って実装し直したのが下記です。
Monadic の do 記法は以下のように実装します。（Haskell の do に近い記述が可能になっています）

do の後にモナドオブジェクト（下記の listM） *3 を指定する
変数 <- 関数(・・・) で関数の結果を変数に束縛
return でモナド処理の結果を返す

do 記法 3手版 move_knight.mjs

var monadic = require('monadic');
var listM = monadic.list();

var moveKnight = function(p) {
    ・・・
};

var in3 = function(start) {
    // do 記法で実装
    return do listM {
        first  <- moveKnight(start)
        second <- moveKnight(first)
        third  <- moveKnight(second)

        return third
    };
};

console.log(in3({c: 6, r: 2}));

var canReachIn3 = function(start, end) {
    ・・・
};

console.log(canReachIn3({c: 6, r: 2}, {c: 6, r: 1}));
console.log(canReachIn3({c: 6, r: 2}, {c: 7, r: 3}));

do 記法を使った .mjs ファイルのオーソドックスな実行方法が分からなかったので、-e オプションを使って実行してみました。

require('monadic').transform() で 'move_knight.mjs' を純粋な JavaScript コードへ変換し eval 実行しています。

do 記法 3手版の実行結果

> node -e "eval(require('monadic').transform(process.argv[1]))" move_knight.mjs
[ { c: 8, r: 1 },
  { c: 8, r: 3 },
  { c: 4, r: 1 },
  { c: 4, r: 3 },
  ・・・
  { c: 3, r: 4 },
  { c: 3, r: 8 } ]
true
false

transform による変換結果は以下のようになります。

require('monadic').transform('move_knight.mjs') の変換結果（do の箇所）

・・・
var in3 = function (start) {
    return listM.mbind(moveKnight(start), function (first) {
        return listM.mbind(moveKnight(first), function (second) {
            return listM.mbind(moveKnight(second), function (third) {
                return function () {
                    return listM.mreturn(third);
                }.bind(this)();
            }.bind(this));
        }.bind(this));
    }.bind(this));
};
・・・

N手版

N手版は、moveKnight を使ったバインド処理（listM.mbind）を入れ子に N個連結するため reduceRight を使いました。

N手版 move_knight_many.js

var monadic = require('monadic');
var listM = monadic.list();

var moveKnight = function(p) {
    ・・・
};

// N手 (num) 先の移動位置を列挙（重複あり）
var inMany = function(num, start) {
    // num 個の moveKnight から成る配列を作成
    var items = new Array(num);
    for (var i = 0; i < num; i++) {
        items.push(moveKnight);
    }
    // num 個の moveKnight を listM.mbind で連結
    return items.reduceRight(
        function(acc, elem) {
            return listM.mbind(acc, elem);
        }, 
        [start]
    );
};

console.log(inMany(3, {c: 6, r: 2}));

// 指定位置に N手(num) で到達できるか否かを判定
var canReachInMany = function(num, start, end) {
    return inMany(num, start).some(function(p) {
        return (p.c == end.c && p.r == end.r);
    });
};

console.log(canReachInMany(3, {c: 6, r: 2}, {c: 6, r: 1}));
console.log(canReachInMany(3, {c: 6, r: 2}, {c: 7, r: 3}));

実行結果は以下の通り。

N手版の実行結果

> node move_knight_many.js
[ { c: 8, r: 1 },
  { c: 8, r: 3 },
  { c: 4, r: 1 },
  { c: 4, r: 3 },
  ・・・
  { c: 3, r: 4 },
  { c: 3, r: 8 } ]
true
false

CoffeeScript 版

最後に、3手版とN手版のサンプルを CoffeeScript で実装し直してみました。

CoffeeScript 1.4.0

Monadic の do 記法に関しては、TameJS の時（id:fits:20120415）と同様に Embedded JavaScript を使えばいけるかもしれませんが今回は調査していません。

CoffeeScript 3手版 move_knight.coffee

monadic = require 'monadic'
listM = monadic.list()

moveKnight = (p) ->
    [
        {c: p.c + 2, r: p.r - 1}, {c: p.c + 2, r: p.r + 1},
        {c: p.c - 2, r: p.r - 1}, {c: p.c - 2, r: p.r + 1},
        {c: p.c + 1, r: p.r - 2}, {c: p.c + 1, r: p.r + 2},
        {c: p.c - 1, r: p.r - 2}, {c: p.c - 1, r: p.r + 2}
    ].filter (t) -> t.c in [1..8] and t.r in [1..8]

in3 = (start) ->
    listM.mbind(
        listM.mbind(
            listM.mbind(
                [start], 
                moveKnight
            ),
            moveKnight
        ),
        moveKnight
    )

console.log in3 {c: 6, r: 2}

canReachIn3 = (start, end) ->
    in3(start).some (p) ->
        p.c == end.c and p.r == end.r

console.log canReachIn3 {c: 6, r: 2}, {c: 6, r: 1}
console.log canReachIn3 {c: 6, r: 2}, {c: 7, r: 3}

CoffeeScript 3手版の実行結果

> coffee move_knight.coffee
[ { c: 8, r: 1 },
  { c: 8, r: 3 },
  { c: 4, r: 1 },
  { c: 4, r: 3 },
  ・・・
  { c: 3, r: 4 },
  { c: 3, r: 8 } ]
true
false

N手版は以下の通りです。
[1..num].map( -> moveKnight ) で num 個の moveKnight から成る配列を作っています。

CoffeeScript N手版 move_knight_many.coffee

monadic = require 'monadic'
listM = monadic.list()

moveKnight = (p) ->
    [
        {c: p.c + 2, r: p.r - 1}, {c: p.c + 2, r: p.r + 1},
        {c: p.c - 2, r: p.r - 1}, {c: p.c - 2, r: p.r + 1},
        {c: p.c + 1, r: p.r - 2}, {c: p.c + 1, r: p.r + 2},
        {c: p.c - 1, r: p.r - 2}, {c: p.c - 1, r: p.r + 2}
    ].filter (t) -> t.c in [1..8] and t.r in [1..8]

inMany = (num, start) ->
    [1..num].map( -> moveKnight ).reduceRight (acc, elem) ->
        listM.mbind(acc, elem)
    , [start]

console.log inMany 3, {c: 6, r: 2}

canReachInMany = (num, start, end) ->
    inMany(num, start).some (p) ->
        p.c == end.c and p.r == end.r

console.log canReachInMany 3, {c: 6, r: 2}, {c: 6, r: 1}
console.log canReachInMany 3, {c: 6, r: 2}, {c: 7, r: 3}

CoffeeScript N手版の実行結果

> coffee move_knight_many.coffee
[ { c: 8, r: 1 },
  { c: 8, r: 3 },
  { c: 4, r: 1 },
  { c: 4, r: 3 },
  ・・・
  { c: 3, r: 4 },
  { c: 3, r: 8 } ]
true
false

*1:チェス盤のナイトの現在位置から次に移動可能な位置を列挙する

*2:Haskell や Scalaz の >>= に該当

*3:モナドオブジェクトには mreturn と mbind メソッドが必要