ScalaのForループ

MapやFilterを使った高階操作はわかりづらい場合もあるので、Scalaでは従来の手続き型スタイルのForループに近い記法も用意されている。その記法では、
persons filter (p => p.age > 20) map (p => p.name)
を
for (p <-persons if age > 20) yield p.name
という風に書くことができる。形式的には、
for ( s ) yield e
このようなになり、sはGenerators, Definitions, Filtersの並びで構成されるらしい。
Generatorsとは、 val x <- e で、eがList値の式であるようなもの。Definitionsは通常の定義と同じで、以後の式で使うことができる。FiltersはBoolean型の式。普通は関数になるハズ。
sはGeneratorsではじまる必要があり、Generatorが複数記述された場合はネストされたような動きになる。つまり、先行するGeneratorが1度評価されるたびに、後続のGeneratorはすべて評価される。
for ( s )の記法ではGeneratorsとDefinitions,Filtersの間はセミコロンで区切らないといけないが、()の代わりに{}を使う記法、つまり for { s }の記法を使った場合、セミコロンは省略することができる。

The N-Queen Problem
レイトン教授でもよく出題されていた、N-Queen問題を例として、For-Comprehensionの使い方を見ていく。N-Queen問題は、N行・N列のチェス盤にQueenを置くゲームで、Queenは互いにチェック状態にならないようにする、というもの。Queenは同じ行・列・斜めの直線状のコマをチェックできるので、お互いが同じ行・列・斜め線に並ばないように配置しなければならない。
これを解く方法としては、新たに置いたQueenが今まで置いたQueenにチェックされないかを確認しながら、1列ずつQueenを置いていく、というものが考えられる。このコードは、以下のように書ける。
def queens(n: Int): List[List[Int]] = {
  def placeQueens(k: Int): List[List[Int]] =
    if (k == 0) List(List())
    else for { queens <- placeQueens(k - 1)
      column <- List.range(1, n + 1)
       if isSafe(column, queens, 1) } yield column :: queens
    placeQueens(n)
}
def queens(n: Int) : List[List[Int]]は、N-Queen問題の「n」、つまりQueenを置く盤のサイズを受け取り、すべての解をListで返すというもの。
内部のList[Int]はそれ自体が1つの解を表すようになっており、1～nのそれぞれの行（列）でのQueenの位置（列または行）を表す。
実際にこの問題を解いているのはdef placeQueens(k: Int): List[List[Int]]の部分で、再帰になっている。queensはこの内部メソッドを呼んでいるだけだ。

では、placeQueensを見ていく。
「k == 0」の場合は、空ListのListを返している。List(List())の部分。「k >= 1」の場合にFor-Complehensionが出てきている。

「k >= 1」の場合、まずｋ－１の解のセットをすべて取得（これはplaceQueens(k - 1)で取得）し、ここから解を1つ取り出す。この1つの解ごとにList.range(1, n + 1)でIntのList（1～n、これは盤の列の数、すなわちk番目のQueenの置き場所の候補）を生成する。
で、k-1の解と、k列でのQueenの配置をisSafeに渡して、Safeだったらこの2つを結合してk列までの解として返す。これを解とk列の置き場所の組み合わせの数だけ実行すれば、すべての解が得られることになる。

k-１の解とkの解の総当りを試すところは、二重ループになっている。ScalaのForの表記的は多重ループがわかりづらいので、最初見た時には混乱してしまった。

Querying with For-Comprehensions
For記法は、データベースクエリ言語の基本的な部分と本質的には同じらしい。例えば、書籍データベースを以下のようにBookクラスのListとして表現したとする。
case class Book(title: String, authors: List[String])

val books: List[Book] = List(
Book("Structure and Interpretation of Computer Programs",
List("Abelson, Harold", "Sussman, Gerald J.")),
Book("Principles of Compiler Design",
List("Aho, Alfred", "Ullman, Jeffrey")),
Book("Programming in Modula2",
List("Wirth, Niklaus")),
Book("Introduction to Functional Programming"),
List("Bird, Richard")),
Book("The Java Language Specification",
List("Gosling, James", "Joy, Bill", "Steele, Guy", "Bracha, Gilad")))
このデータベースに対して、authorが"Ullman"から始まるBookのtitleを取り出すには、こう書ける。
for (b <- books; a <- b.authors if a startsWith "Ullman") yield b.title
titleに"Program"が含まれるものについては、こう。
for (b <- books if (b.title indexOf "Program") >= 0) yield b.title
少なくとも2冊の本を書いている著者の名前を取り出す場合には、こう書ける。
for (b1 <- books; b2 <- books if b1 != b2; a1 <- b1.authors; a2 <- b2.authors if a1 == a2) yield a1
これは完全ではなく、著者が二重にカウントされてしまう。重複した著者を取り除く関数は、以下のように書ける。
def removeDuplicates[A](xs: List[A]): List[A] =
 if (xs.isEmpty) xs
 else xs.head :: removeDuplicates(xs.tail filter (x => x != xs.head))
これをFor-Comprehensionで書くと、こうなる。
xs.head :: removeDuplicates(for (x <- xs.tail if x != xs.head) yield x)

For-Comprehensionの変換
For-Comprehensionは、結局はmap/flatMap/filterの組み合わせに変換できる。
for (x <- e) yield e’
このようなFor-Comprehensionは、
e.map(x => e’)
こう変換できる。
for (x <- e if f; s) yield e’
これは、
for (x <- e.filter(x => f); s) yield e’
こう。fはフィルタ（Boolean式）で、sはGeneratorとFilterらしい。が、ForでDefinition使った例見たことないし、if f の後のGeneratorってどうなるのかもよくわからないぞ。
for (x <- e; y <- e’; s) yield e’’
これは、
e.flatMap(x => for (y <- e’; s) yield e’’)
こうなる。

もう少し具体的な例をあげると、
for { i <- range(1, n) j <- range(1, i) if isPrime(i+j)} yield {i, j}
これが…
range(1, n)
 .flatMap(i =>
   range(1, i)
     .filter(j => isPrime(i+j))
       .map(j => (i, j)))
こうなる。まぁ、そうだよね。

For-Loop
For-ComrehensionではListを構築して返す形になるが、繰り返し処理では必ずしもListを構築したいとは限らない。こういう場合にはFor-Loopが使える。
for (xs <- xss) for (x <- xs) print(x + "\t") println() }
Bloggerでなぜかインデントできなかったけど、インデントすればおなじみのForループ。

Generalizing For
Forは、Listに対して以外にも使うことができる。実際のところ、以下のようなメソッドが実装されているクラスCであれば、For-ComprehensionやFor-Loopを使うことができるらしい。
  • def map[B](f: A => B): C[B]
  • def flatMap[B](f: A => C[B]): C[B]
  • def filter(p: A => Boolean): C[A]
というわけで、しょぼいながら試してみた。
class ListLike[+A](x : Seq[A]) {
 val internal = x.toList

 def map[B](f: A => B): ListLike[B] = {
   new ListLike(internal.map[B](f).toSeq)
 }
 def flatMap[B](f: A => ListLike[B]): ListLike[B] = {
   new ListLike(null)
 }
 def filter(p: A => Boolean): ListLike[A] = {
   new ListLike(null)
 }
}
で、呼び出し。
val list = new ListLike(List(1, 2, 3, 4))
val ret = for (i <- list) yield 1; println(ret)
結果。
List(1, 1, 1, 1)
というわけで、一応動いている模様。mapしか使われていないけど、他はちゃんと実装するのが面倒くさかったので飛ばしてしまう。
さらに、For-Loopを試してみたが、実際にやってみると、以下のようなコンパイルエラーが出る。
value foreach is not a member of sample.for_example.ListLike[Nothing]
どうやら、For-Loopではforeachというメンバが必要らしい。foreachを定義してみたところ、コンパイルエラーは消えた。
def foreach(f: A => Unit) {
 internal.map(f)
}
実行してみる。
for (i <- list) { println("aaa") }
結果。
aaa
aaa
aaa
aaa
というわけで、あまりにもしょぼいけど一応動くことは確認。foreachは内部のブロックを引数として取る形になってるらしい。デバッグしてみたらFuction1だった。ということで、Forも終わり。なんだか長かったなぁ。

コメント

コメントを投稿