uehaj's blog

Grな日々 - GroovyとかGrailsとかElmとかRustとかHaskellとかReactとかFregeとかJavaとか -

List.collectManyで非決定計算

これはG*Advent callender 2016の記事です。 前日は@Ziphilさんの記事でした。明日はまた私@uehajの記事です。

出オチでタイトルオンリーです。

すごいHaksell楽しく学ぼう(以降H本)にも書かれているように、リストはモナドとみなすと「非決定計算」をあらわすものとみることができます。

つまりたとえばリスト[1,2,3]を「1か2か3のどれか」、リスト[2,3]を「2か3のどれか」をそれぞれあらわすもの、と見るってことです。その上で、[1,2,3] * [2,3] という操作を何等かの方法で表現すれば、「1か2か3のどれか」に「2か3のいずれか」を掛けたものという意味になり、結果として「1*2,2*2,3*2,1*3, 2*3,3*3]すなわち「1か4か6か3か6か9のどれか」を得ることができます。

さて、Groovyのリスト(厳密にはIterable)には、collectManyというメソッドがあって、これは上記のようにリストを非決定計算と考えたときの、任意の計算を「何等かの方法」で適用すること*1に相当します。

やってみます。

H本の例

ghci> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)  
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]  

ここでは「1,2のどっちか」と「'a','b'のどっちか」をタプル化操作したもののどれか( [(1,'a'),(1,'b'),(2,'a'),(2,'b')] )を得ています。 これをGroovyで考えると以下のようになります。

groovy:000> [1,2].collectMany{n -> ['a','b'].collectMany{ ch -> [[n, ch]] }}
===> [[1, a], [1, b], [2, a], [2, b]]

Haksellと同様の結果が得られます(Groovyにはちゃんとしたタプルが無いのでリストで代用)。

ピタゴラス数を求める

次に同様にcollectManyを使ってピタゴラス数を求めてみましょう。

ピタゴラス数とは、a^2 + b^2 == cを満たす3つの数です。aが10までの範囲で求めてみます。

(1..10).collectMany{ a ->
(1..a).collectMany{ b ->
(a..a+b).collectMany{ c ->
    return (a**2 + b**2 == c**2) ? ["a=$a, b=$b, c=$c"] : []
}}}.each {
    println it
}

実行すると

a=4, b=3, c=5
a=8, b=6, c=10

を出力します。

覆面算を解く

もう一つ応用例です。以下のような有名な覆面算を解いてみます。

   SEND
+) MORE
~~~~~~~~~~
  MONEY

上記を成立させるように、アルファベットに重複せずに数を割り当てる問題です。

この問題は、Sが「1〜9のどれか」Eが「1〜9のどれか、かつSではない」…という可能性をもった非決定的な数同士であり、それらがある条件を満すかどうかを判定する非決定計算の問題とみることができます。 これをcollectManyを使って解くと以下のようになります。

def digits = 0..9 as List

def isAnswer(S,E,N,D,M,O,R,Y) {
  (S*1000+E*100+N*10+D) + (M*1000+O*100+R*10+E) == (M*10000+O*1000+N*100+E*10+Y)
}

(digits-0).collectMany { S ->
(digits-S-0).collectMany { M->
(digits-S-M).collectMany { E->
(digits-S-M-E).collectMany { O->
(digits-S-M-E-O).collectMany { N->
(digits-S-M-E-O-N).collectMany { R->
(digits-S-M-E-O-N-R).collectMany { D->
(digits-S-M-E-O-N-R-D).collectMany { Y->
if (isAnswer(S,E,N,D,M,O,R,Y)) {
  return ["""\
  $S$E$N$D
+)$M$O$R$E
 $M$O$N$E$Y
"""]
  }
  return []
}}}}}}}}.each {
 println it
}

上記は以下を出力します。

  9567
+)1085
 10652

メタクラスさん登場

collectManyがちょっと字面上うるさいという場合、

List.metaClass.rightShiftUnsigned = { x->delegate.collectMany(x) }

のように演算子「>>>」に割り当てても良いかもしれません。

List.metaClass.rightShiftUnsigned = { x->delegate.collectMany(x) }

def digits = 0..9 as List

def isAnswer(S,E,N,D,M,O,R,Y) {
  (S*1000+E*100+N*10+D) + (M*1000+O*100+R*10+E) == (M*10000+O*1000+N*100+E*10+Y)
}

(
(digits-0) >>> { S ->
(digits-S-0) >>> { M->
(digits-S-M) >>> { E->
(digits-S-M-E) >>> { O->
(digits-S-M-E-O) >>> { N->
(digits-S-M-E-O-N) >>> { R->
(digits-S-M-E-O-N-R) >>> { D->
(digits-S-M-E-O-N-R-D) >>> { Y->
if (isAnswer(S,E,N,D,M,O,R,Y)) {
  return ["""\
  $S$E$N$D
+)$M$O$R$E
 $M$O$N$E$Y
"""]
  }
  return []
}}}}}}}}).each {
 println it
}

現場からは以上です。

余談

あとは余談ですが、「}}}}}}}}.each {」の閉じ括弧の連続が嫌ですね。これはGroovyのクロージャの記法{->}の作りが良くなくて、今回の用法ではネストが必要になるので、複数の閉じ括弧が必要になるというわけです。ここをJava8のラムダ式の記法で書ければ良いと思いませんか? つまり

(
(digits-0) >>> (S) ->
(digits-S-0) >>> (M) ->
(digits-S-M) >>> (E) ->
(digits-S-M-E) >>> (O) ->
(digits-S-M-E-O) >>> (N) ->
(digits-S-M-E-O-N) >>> (R) ->
(digits-S-M-E-O-N-R) >>> (D) ->
(digits-S-M-E-O-N-R-D) >>> (Y) -> {
if (isAnswer(S,E,N,D,M,O,R,Y)) {
  return ["""\
  $S$E$N$D
+)$M$O$R$E
 $M$O$N$E$Y
"""]
  }
  return []
}).each {
 println it
}

と書く。やってやれないことはない、どうしたら良いのか?ということは明日の記事に回したいと思います(伏線)。

参考

uehaj.hatenablog.com

すごいHaskellたのしく学ぼう!
Miran Lipovača
オーム社
売り上げランキング: 60,257

*1:Haskellで言うモナディックな操作適用演算子>>=(bind)、Scalaで言うflatMap。