これは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 }
と書く。やってやれないことはない、どうしたら良いのか?ということは明日の記事に回したいと思います(伏線)。