List comprehension
Scala の for 式で覆面算を解いているエントリを見つけたので同じように Haskell と Groovy で解きながらリスト内包表記について考える。
リスト内包表記は Groovy にもいずれ実装されるのか？
共通部分
def num(int... xs) { xs.inject(0) { acc, x -> acc * 10 + x } } def digits = 0..9
for ループで解く
def solve1 = { def yield = [] for (s in digits) if (s != 0) for (e in digits - [s]) for (n in digits - [s, e]) for (d in digits - [s, e, n]) for (m in digits - [s, e, n, d]) if (m != 0) for (o in digits - [s, e, n, d, m]) for (r in digits - [s, e, n, d, m, o]) for (y in digits - [s, e, n, d, m, o, r]) if (num(s, e, n, d) + num(m, o, r, e) == num(m, o, n, e, y)) yield << [num(s, e, n, d), num(m, o, r, e), num(m, o, n, e, y)] return yield }
- ネストしないで記述 *1
- このぐらいループすると for 式も一行で記述できなくなるので、ネストしないループと変わらない
List のメソッドで解く
『Scala スケーラブルプログラミング』の第 23 章によれば Scala コンパイラは for 式を map, flatMap, filter 呼び出しの組合せに変換しているそうだ。*2
Groovy で変換後の形を記述する。
class ListOps { static def concat(List self) { self.inject([]) { acc, v -> acc + v } } static def map(List self, Closure f) { self.collect { f(it) } } static def concatMap(List self, Closure f) { concat(map(self, f)) } } def solve2 = { use (ListOps) { digits.findAll { s -> s != 0 }.concatMap { s -> (digits - [s]).concatMap { e -> (digits - [s, e]).concatMap { n -> (digits - [s, e, n]).concatMap { d -> (digits - [s, e, n, d]).findAll { m -> m != 0 }.concatMap { m -> (digits - [s, e, n, d, m]).concatMap { o -> (digits - [s, e, n, d, m, o]).concatMap { r -> (digits - [s, e, n, d, m, o, r]).findAll { y -> num(s, e, n, d) + num(m, o, r, e) == num(m, o, n, e, y) }.map { y -> [num(s, e, n, d), num(m, o, r, e), num(m, o, n, e, y)] } } } } } } } } } }
List モナドで解く
まずは Haskell の do 式で
-- ghci import Data.List import Control.Monad :{ let { digits = [0..9]; num = foldl ((+).(*10)) 0 } in do { s <- digits; guard (s /= 0); e <- digits \\ [s]; n <- digits \\ [s, e]; d <- digits \\ [s, e, n]; m <- digits \\ [s, e, n, d]; guard (m /= 0); o <- digits \\ [s, e, n, d, m]; r <- digits \\ [s, e, n, d, m, o]; y <- digits \\ [s, e, n, d, m, o, r]; guard (num [s, e, n, d] + num [m, o, r, e] == num [m, o, n, e, y]); return (num [s, e, n, d], num [m, o, r, e], num [m, o, n, e, y]) } :}
- 次のエラーが発生するので ; 区切りで記述した
- The last statement in a 'do' construct must be an expression
do 式から bind へ変換した形で Groovy で記述する。
class ListMonad { static def rightShiftUnsigned(List self, Closure f) { ListOps.concat(self.collect { f(it) }) } static def return_(_, x) { [x] } static def rightShift(List self, List other) { ListOps.concat(self.collect { other }) } // guard :: MonadPlus m => Bool -> m () // guard p = if p then return () else mzero static def guard(_, boolean p) { // guard(条件) >> リスト // 条件が真の場合は、要素が1つのリストを返す -> 要素は使われない。ループは1回 // 条件が偽の場合は、空リストを返す -> ループ終了 if (p) return_(_, null) else ListMonadPlus.mzero(_) } } class ListMonadPlus { static def mzero(_) { [] } static def mplus(List self, List other) { self + other } } def solve3 = { use (ListMonad) { digits >>> { s -> guard (s != 0) >> digits - [s] >>> { e -> digits - [s, e] >>> { n -> digits - [s, e, n] >>> { d -> digits - [s, e, n, d] >>> { m -> guard (m != 0) >> digits - [s, e, n, d, m] >>> { o -> digits - [s, e, n, d, m, o] >>> { r -> digits - [s, e, n, d, m, o, r] >>> { y -> guard (num(s, e, n, d) + num(m, o, r, e) == num(m, o, n, e, y)) >> return_([num(s, e, n, d), num(m, o, r, e), num(m, o, n, e, y)]) } } } } } } } } } }
- Haskell の >>= は >>> に対応している
- Monad、MonadPlus、guard の定義は The Haskell 98 Library Report: Monad Utilities を参照した
- 第4回 「取り出し可能な値」のみを持つListモナド（2ページ目） | 日経 xTECH（クロステック）
- Parser に当てはめれば mzero は failure で mplus は or に当たる
Haskell のリスト内包表記で解く
-- ghci import Data.List :{ let { digits = [0..9]; num = foldl ((+).(*10)) 0 } in [(num [s, e, n, d], num [m, o, r, e], num [m, o, n, e, y]) | s <- digits, s /= 0, e <- digits \\ [s], n <- digits \\ [s, e], d <- digits \\ [s, e, n], m <- digits \\ [s, e, n, d], m /= 0, o <- digits \\ [s, e, n, d, m], r <- digits \\ [s, e, n, d, m, o], y <- digits \\ [s, e, n, d, m, o, r], num [s, e, n, d] + num [m, o, r, e] == num [m, o, n, e, y]] :}
デカルト積で解く
// USE VERY LARGE MEMORY def solve4 = { def yield = [] ([digits] * 8).combinations().each { s, e, n, d, m, o, r, y -> if (s != 0 && m != 0 && [s, e, n, d, m, o, r, y].unique().size() == 8) if (num(s, e, n, d) + num(m, o, r, e) == num(m, o, n, e, y)) yield << [num(s, e, n, d), num(m, o, r, e), num(m, o, n, e, y)] } yield }
- 実行できないのでバグがあるかもしれない
問題点
- 10 ** 8 サイズのリストを生成している
- 途中で枝刈りができない
- ループの順序が違う
list.reverse().combinations() { it.reverse() }
404 Blog Not Found:perl & javascript - nested list comprehension
// 生成された js にインデントを加えた function anonymous(cond) { var _list_ = []; for (var i0 = 1, l0 = 4; i0 < l0; i0++) { for (var i1 = 2, l1 = 5; i1 < l1; i1++) { for (var i2 = 3, l2 = 6; i2 < l2; i2++) { if (cond(i0, i1, i2)) { _list_.push([i0, i1, i2]); } } } } return _list_; }
- デカルト積を求めてから絞り込んでいる
- List#combinations と違って callback になっているのでリスト全体は必要にならない
Groovy で解く
def solve5 = { def combs = { list, n -> if (n == 0 || n > list.size()) return [] if (n == 1) return list.collect { [it] } def (x, xs) = [list.head(), list.tail()] call(xs, n-1).collect { [x, *it] } + call(xs, n) } def yield = [] combs(digits, 8)*.eachPermutation { s, e, n, d, m, o, r, y -> if (s != 0 && m != 0) if (num(s, e, n, d) + num(m, o, r, e) == num(m, o, n, e, y)) yield << [num(s, e, n, d), num(m, o, r, e), num(m, o, n, e, y)] } yield }
- 8 種類の数字を使用することが分かっているので組合せを決めてから順列を求める
- 順列は callback で呼び出せる
- s != 0 の条件は、最内に入っているが combs().findAll で外に出すことは可能
- *. は展開ドット演算子
// 『Groovy イン・アクション』から list*.member list.collect { item -> item?.member }
追記 2011-04-07
withFilter
id:xuwei 氏から Scala は withFilter にも変換されると教えてもらった。
scala> List(1,2,3).filter{ (i)=>println(i);i%2==1 } 1 2 3 res0: List[Int] = List(1, 3) scala> List(1,2,3).withFilter{ (i)=>println(i);i%2==1 } res1: scala.collection.generic.FilterMonadic[Int,List[Int]] = scala.collection.TraversableLike$WithFilter@173a0067
withFilter までで 1 つの List のように扱い filter のためだけのループを行わないようにしているんだと思う。
scala.tools.ast.parser.TreeBuilder#makeFor に答えがありそうだが調べられていない。
Scala for実体メモ(Hishidama's Scala for-convert Memo) のベンチマークも参考にした。
guard
型クラスでHaskellのguardを定義してみる(未完) - papamitra
似たようなことをしている人を発見。
Listモナドではなくモナドで挑戦されているようだ。
guard の動作原理を考える - あどけない話
プログラミング Haskell の訳者である山本氏のエントリを発見。
過程も含めて解説されている。
