Roy で List モナド

JavaScript Node.js Monad

前回に続き、今回も Roy を試してみます。

Roy ではモナドを使った do 記法を使えるようなので、JavaScript で List モナド - Monadic 等で試したチェスのナイト移動の List モナド処理を同じように実装してみました。

ソースは http://github.com/fits/try_samples/tree/master/blog/20140724/

モナドの定義

Roy では下記のように return と bind を実装してモナドを定義します。

let <モナド> {
    return: \x -> ・・・
    bind: \x f -> ・・・
}

これで Monadic と同じように do <モナド> ・・・ のような記法が使えます。

それでは、List モナドを定義して do を簡単に使ってみました。
Underscore.js に Haskell の concat と同等の処理が無さそうだったので concat を自前で定義しています。

sample.roy
let _ = require 'underscore'

let concat xs = _.reduce xs (\a b -> a.concat b) []
// リストモナド
let listMonad = {
    return: \x -> [x]
    bind: \xs f -> concat (_.map xs (\y -> f y))
}
// do 記法
let res = do listMonad
    x <- [1, 3, 5]
    y <- ['a', 'b']
    return (x * 2, y)

console.log res

do でタプル (要素1, 要素2, ・・・) を return していますが、下記のようにタプルは配列として扱われるようです。

実行結果
> roy -r sample.roy

[ [ 2, 'a' ],
  [ 2, 'b' ],
  [ 6, 'a' ],
  [ 6, 'b' ],
  [ 10, 'a' ],
  [ 10, 'b' ] ]

3手版

それでは本題に入ります。

まずは、List モナドを使って下記の処理を実装してみます。

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

Haskell と同様に type で型シノニムを定義できるので、ナイトの位置情報を表す KnightPos という型シノニムを定義しました。

関数の引数では (<引数>: <型>) のように型を指定する事も可能です。

また、複数の引数は Haskell と同様に半角スペースで区切る事になります。

move_knight.roy （3手移動版）
let _ = require 'underscore'

let concat xs = _.reduce xs (\a b -> a.concat b) []

let listMonad = {
    return: \x -> [x]
    bind: \xs f -> concat (_.map xs (\y -> f y))
}
// 型シノニムの定義
type KnightPos = {c: Number, r: Number}

let inRange (n: Number) = _.contains (_.range 1 9) n

// ナイトの次の移動先を列挙
let moveKnight (p: KnightPos) = _.filter [
    {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}
] ( \t -> (inRange t.c) && (inRange t.r) )

// 3手先の移動位置を列挙（重複あり）
let in3 (start: KnightPos) = do listMonad
    fst <- moveKnight start
    snd <- moveKnight fst
    moveKnight snd

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

// 指定位置に3手で到達できるか否かを判定
let canReachIn3 (start: KnightPos) (end: KnightPos) = _.any (in3 start) (\p -> 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})
実行結果
> roy -r move_knight.roy

[ { 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手版

先程は 3手で固定していましたが、任意の手数を指定できるようにしてみます。

こちらは do を使わず、直接 listMonad.bind を使って n 回のナイト移動処理を連結するようにしました。

move_knight_many.roy （N手移動版）
・・・
// n手先の移動位置を列挙（重複あり）
let inMany (n: Number) (start: KnightPos) = _.reduce (_.range n) (\a b -> listMonad.bind a moveKnight) [start]

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

// 指定位置に n手で到達できるか否かを判定
let canReachInMany (n: Number) (start: KnightPos) (end: KnightPos) = _.any (inMany 3 start) (\p -> 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})
実行結果
> roy -r move_knight_many.roy

[ { 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