Hatena::ブログ(Diary)

みずぴー日記 Twitter

2010-12-25(土)

リストモナドを使ってみる

| リストモナドを使ってみるを含むブックマーク

このエントリはScala Advent Calendar jp 2010 : ATNDの25日のものです。

メリークリスマス! クリスマスは楽しくみんなでパズルを解いて遊びましょう。

パズルみたいな探索問題をScalaで解く場合は、リストモナドを使うとキレイに書けます。

例: SEND+MORE=MONEY

例として覆面算を解いてみましょう。

f:id:mzp:20101225212219g:image

各アルファベットに異なる数字が割り当てれる。その数字は何か?

ただし最上位桁が0ではない。

普通にforループを使って解くと、ネストの深さが酷いことになります:)。

// int(1,2,3)を123にする関数
def int(xs : Int*) : Int =
  xs.foldLeft(0)( _ * 10 + _)

// SEND+MORE=MONEYの答えを探索する
def solve : (Int,Int,Int) = {
  for( s <- 0 to 9)
    for( e <- 0 to 9)
      for( n <- 0 to 9)
          ................
                for( y <- 0 to 9)
                  if(s != 0 && m != 0 && int(s,e,n,d) + int(m,o,r,e) == int(m,o,n,e,y))
                    return (int(s, e, n, d) , int(m, o, r, e) , int(m, o, n, e, y))
}

これをリストモナドを使って書くと次のようになります。あいかわらずforを使ってるように見えるかもしれませんが、それは幻想です:)。

def solve : Seq[(Int, Int,Int)] = {
  val digits = 0 to 9
  for {
    // sは0〜9のどれか
    s <- digits
    // eは0〜9からsをのぞいたもののどれか
    e <- digits diff List(s)
    // nは0〜9からsとeをのぞいたもののどれか
    n <- digits diff List(s, e)
    // dは(ry
    d <- digits diff List(s, e, n)
    m <- digits diff List(s, e, n, d)
    o <- digits diff List(s, e, n, d, m)
    r <- digits diff List(s, e, n, d, m, o)
    y <- digits diff List(s, e, n, d, m, o, r)
    // sは0ではない
    if s != 0
    // mも0ではない
    if m != 0
    // SEND+MORE == MONEYを満すかどうかをチェック
    if int(s, e, n, d) + int(m, o, r, e) == int(m, o, n, e, y)
  } yield (int(s, e, n, d) , int(m, o, r, e) , int(m, o, n, e, y))
}

ネストが浅くなって超クール!

適当な解説

  • 「sは0〜9のどれか」のようなあいまい性を含んだままプログラムが書ける非決定計算というパラダイムがあります。
  • リストモナドを使うと、この非決定計算をScalaに持ち込むことができます。
  • しかもfor構文のおかげて、わりと自然な感じに書くことができます。

まとめ

Scalaで探索問題を書くときはリストモナドが便利だよ!

selvaggioselvaggio 2010/12/26 03:22 こういうのみるといつも思うんだけど、探索効率とかどうなの?

mzpmzp 2010/12/26 09:42 あわせてよみたい http://www.itpl.co.jp/ocaml-nagoya/?%A5%CD%A5%BF%B5%AD%CF%BF%B8%CB%2FSEND%2BMORE%3DMONEY
Prologはつよかった。

selvaggioselvaggio 2010/12/30 20:13 ぱねぇっす