Programming in Scala, First Edition: Chapter 23

23. For Expressions Revisited
  forはmap,flatMap,filterの組み合わせと透過。
  forの方がmap,flatMap,filterの組み合わせより読みやすい。

23.1 For expressions
  for {
    pat_g1 <- expr_g1 // 1st generator
    pat_d2 = expr_g2  // 1st definition
    if expr_f1        // 1st filter
    pat_g2 <- expr_g2 // 2nd generator
    ...
  } yield expr_y
  for {
    p <- persons              // a generator
    n = p.name                // a definition
    if (n startsWith "To")    // a filter
  } yield n
  generator
    exprはListを返す場合が多い。実際は後述の様により一般的なtypeが使える。
    patはChapter 15のpattern matchingが使える。
      matchしなかった場合はnoMatchErrorがthrowされる。
    一番多いのは単に値 x <- expr とする場合。この場合は単にexprを走査するだけ。
  definition
    val pat = expr と同じ
    一番多いのは単に値 x = expr とする場合。単に値を割り当てているだけ。
  filter
    exprはBooleanを返す。falseの場合はyieldや以降のgeneratorが実行されない。
    ifの後の()は省略可能。(if expressionでは省略できない)
  generator一つに対して、definition, filterは複数定義できる。
  generator,definition,filterの組も複数定義出来る。
    上のgeneratorの一つの要素に対して下のgenerator全体が実施される。
    上のgeneratorが外側のループで、下のgeneratorが内側のループ

23.2 The n-queens problem
  8-queens問題をNxNに一般化したn-queens問題の解法。
    縦、横、斜めに重複しない様にn個のqueenを配置する問題。
  forを使ったcombinatorial searchがポイント。
  幅優先探索を使って全ての解を求める。
  一行毎に制約を満たすような可能なqueenの配置をすべて求めていく。
    再帰的なアルゴリズムになる事を示唆している。
  新しい情報の追加はListの先頭に行うようにする。(stack)
  def queens(n: Int): List[List[(Int, Int)]] = {
    def placeQueens(k: Int): List[List[(Int, Int)]] =
      if (k == 0) List(List())
      else for {
          queens <- placeQueens(k - 1)
          column <- 1 to n; queen = (k, column); if isSafe(queen, queens)
        } yield queen :: queens
    placeQueens(n)
  }
  def isSafe(queen: (Int, Int), queens: List[(Int, Int)]) =
    queens forall (q => !inCheck(queen, q))
  def inCheck(q1: (Int, Int), q2: (Int, Int)) =
    q1._1 == q2._1 ||  // same row, it can be removed.
    q1._2 == q2._2 ||  // same column
    (q1._1 - q2._1).abs == (q1._2 - q2._2).abs // on diagonal

23.3 Querying with for expressions
  forの記法は本質的にはSQLの様なDBのqueryと同じ操作。

23.4 Translation of for expressions
  forは下記で変換できる。compilerが変換している
    一番内側のループはmap
    外側のループはflatMap
    if節はfilter
    pattern matchingはcase
  yieldなしのforについてはmap/flatMapの代わりにforeachに変換できる。

23.5 Going the other way
  map,flatMap,filterをforに変換する事も出来る。

23.6 Generalizing for
  map,flatMap,filter,foreachを実装しているdata typeならfor記法が使える。
    ranges, iterators, streams, sets等。
  自分で作ったdata typeも同じmethodを実装すればfor記法が使える。
    4つ全てではなくて一部の実装でもOK
    map: 一重ループ
    mapとflatMap: 多重ループ
    filter: filter
    foreach: yieldなしの一重、多重ループ
  for記法からmap等への変換は型チェックの前に行われる。
    for記法そのものはチェックされず、変換後のにチェックされる。
  forに対応しているclassの標準的なmethodのsignature
    abstract class C[A] {
      def map[B](f: A => B): C[B]
      def flatMap[B](f: A => C[B]): C[B]
      def filter(p: A => Boolean): C[A]
      def foreach(b: A => Unit): Unit
    }
  monad
    数多くの計算の型(type)を説明できるmonadと言う概念がある。
      collections, state, I/O, backtracking等幅広い計算を扱える。
    map,flatMap,filterとunit constructorで全てのmonadを特徴づけられる。
      unit constructorはobject-oriented languageのfactory method。
    monadのfunctional conceptのobject-oriented versionと捉えられる。
    for記法は上記のmethodの適用と等しいので、monadのsyntaxと捉えられる。
    for記法が単にcollectionを操作する以上の一般的な概念であると示唆している。
      非同期I/Oでもfor記法が使える。
      optional valuesの代替記法としても使える。
    scalaライブラリのforが使用方法が参考になる。

23.7 Conclusion
  ** haskellのmonadのdo記法と同様なものと捉える事も出来る。