LL脳がscalaの勉強を始めたよ その83
Scalaコップ本の23章にはいって行きますよー、23章ではfor式を使ってアレやコレをやっていきますネ(´・ω・｀)for式を使うことでfilterやflatMap, map等の高階関数表現を解りやすい形で書き下すことができるみたいです。内容に入る前に簡単なサンプルをやってみますよー
例えば次のようなPersonクラスで表現される母と子2人の家族関係の中で、母と子のペアを列記するような処理を考えてみます
// 人を表すケースクラスを定義します // パラメータは名前、性別（男:true, 女:false)、子供デス case class Person(name:String, isMale:Boolean, children:Person*) // まずは子供を定義しますね val lara = Person("Lara", false) val bob = Person("Bob", true) // laraとbobの母親を定義します val julie = Person("Julie", false, lara, bob) // 家族3人のリストを生成します val persons = List(lara, bob, julie)
まずはリストに対してmapやflatMap, filterを使って母と子のすべてのペアを並べる場合は次のようなコードになりますね
// 女性を抜き出して、抜き出した女性全てについて、その子供と並べる処理を行ないます persons filter(p => !p.isMale) flatMap (p => p.children map (c => (p.name, c.name))) // 結果です res0: List[(String, String)] = List((Julie,Lara), (Julie,Bob))
確かにいろいろ組み合わせになるので、ちょっと初見だとちょっぴり分かりづらいですね(´・ω・｀)それではfor式で描き直してみますよ
// for式内にfilterやらの処理を突っ込んでyieldでListを構築します for (p <- persons; if !p.isMale; c<-p.children) yield (p.name, c.name) // 結果です res3: List[(String, String)] = List((Julie,Lara), (Julie,Bob))
おお、高階関数の重ね掛け的部分がなくなるので随分シンプルになりましたな、結果も同じだし(´・ω・｀)実際のところやっている内容は同じなので、Scalaコンパイラーはfor式で書いた内容を前述のfilter, flatMap, map利用の式に置き換えてるそうデス。そんなカンジで便利なfor式をやっていきますよー
for式
まずはfor式の形式をざざっと見ていきますよ。基本的にfor式は次のような形式で表現されるみたいです
// 定義形式です for( seq ) yield expr
seqにはジェネレーター、定義、フィルターの各要素を;で区切ることで連続して記述できるみたいですね、それぞれの要素は下記のようになりますね
- ジェネレータ (pat <- exprで記述)
- exprの要素でpatにマッチするものが反復処理されます
- マッチに失敗しても処理の対象から外れるだけでMatchErrorはでません
- 定義 (pat = exprで記述)
- for式内で利用する変数を定義します
- pat = exprのみの場合はval pat = exprと同様デス(´・ω・｀)
- フィルター (if exprで記述)
- 評価式exprにマッチするものだけを処理の対象にします
- 評価式exprはBoolean型デス
なお、for式はジェネレータから始まります。そしてexprにはyieldによって構築されるリストの要素を記述しますデス。例えば前述のpersonsリストを利用するとこんな感じですかね(´・ω・｀)
for(p <- persons; n = p.name; if(n startsWith "La")) yield n // 結果です、Laraがヒットしました res7: List[String] = List(Lara)
ちなみに上記は次のように複数行で記述することも出来るみたいですね
for( p <- persons; n = p.name; if(n startsWith "La") ) yield n
ついでに7章でもやったとおり括弧の代わりに中括弧を使うことでseq内のセミコロンは省略できるデス
for{ p <- persons n = p.name if(n startsWith "La") } yield n
複数のジェネレータの利用
for式にジェネレータが複数ある場合は、後ろのジェネレータの方が前のジェネレータよりも速いペースで変化するとのことです。ループの入れ子みたいな感じですかね？ちょっとサンプル書いて確かめてみますよ
scala> for(x <- List(1, 2); y <- List("one", "two")) yield (x, y) //// 結果です // 確かに後ろのほうが先に反復処理されるみたいな感じですな(´・ω・｀) res8: List[(Int, java.lang.String)] = List((1,one), (1,two), (2,one), (2,two))
N女王問題
for式の応用としてパズルを解くサンプルをやってみますよ。今回は8女王問題の拡張であるN女王問題をfor式を利用して解いてみますです(´・ω・｀)ちなみに8女王問題はチェスの盤上で、互いに相手を取れない位置に8個の女王（チェスの役、将棋で言うと飛車＋角だっけか？）を置くというパズルらしいです。今回はコレをN×Nマス上でN個の女王を置く問題に拡張してやります(｀・ω・´)
N女王問題の解法
N女王問題ではN個の女王をN×Nのマスに置くためには各行に女王を置く必要があり、k段目のマスの女王が1~k-1段目の女王からと取られない位置を探索する必要があるわけです(´・ω・｀)
ここで再帰的アルゴリズムを使えば良さそうだ(｀・ω・´)ということで次のような手順を考えてみます。
- N×Nのマスにk個の女王を配置する解が得られていると仮定
- 各女王のの座標は(row, column)を要素として持つ長さkのリストで表現
- リストの要素はk, k-1, k-2, ... 2, 1段目の順で保持されるスタックとして表現
- k + 1段目に次の女王を置く場合
- k段目までの女王から取れない位置を探索してリストに要素を追加
- リストは長さがk + 1になる
以上のような流れをコードに落としこむと次のようになるみたいです
def queens(n:Int):List[List[(Int, Int)]] = { //// 女王をおいても良い位置かどうかを判定します // 2つ女王同士の位置関係をチェックする処理 def inCheck(q1:(Int, Int), q2:(Int, Int)) = { // 同じ段にあるかどうか q1._1 == q2._1 || // 同じ行にあるかどうか q1._2 == q2._2 || // 対角線上にあるかどうか (q1._1 - q2._1).abs == (q1._2 - q2._2).abs } // 女王をおいていいかどうかの判定処理を定義 def isSafe(queen:(Int, Int), queens:List[(Int, Int)]) = { // k段目の女王が1~k-1段目の全ての女王に対して // 配置できる位置にあるかをチェックします // # forallは全てが条件を満たせばOKだったハズ(´・ω・｀) queens forall (q => !inCheck(queen, q)) } //// 実際に配置を探索する再帰関数です def placeQueens(k: Int): List[List[(Int, Int)]] = { // 0段目の場合は初期化です if(k == 0){ List(List()) // 実際の配置処理です }else{ // 反復処理を開始します for { // 再帰的に評価を行ないますね queens <- placeQueens(k -1) // k段目の女王の位置候補を生成します column <- 1 to n queen = (k, column) // 女王から取れない位置かどうかという評価式 // フィルターとして定義します if isSafe(queen, queens) // これまで(k -1段目まで)の女王位置に条件を満たしたk段目の女王位置を // 追記したリストを要素として持つ解候補リストを構築します } yield queen :: queens } } // 処理を開始します placeQueens(n) }
Scala的に再帰処理を上手く使うことでかなりスッキリ書けているような気がしマス(´・ω・｀)それでは実際に実行してみますよ
// 2×2のときはできませんな scala> queens(2) res19: List[List[(Int, Int)]] = List() // 3×3のときもできませんな(´・ω・｀) scala> queens(3) res20: List[List[(Int, Int)]] = List() // 4×4のときはこんな感じです // パズルの解が2つあることが分かります scala> queens(4) res21: List[List[(Int, Int)]] = List(List((4,3), (3,1), (2,4), (1,2)), List((4,2), (3,4), (2,1), (1,3))) // 8×8でも…結構いっぱい候補がありますね scala> queens(8) res22: List[List[(Int, Int)]] = List(List((8,4), (7,2), (6,7), (5,3), (4,6), (3,8), (2,5), (1,1)), List((8,5), (7,2), (6,4), (5,7), (4,3), (3,8), (2,6), (1,1)), List((8,3), (7,5), (6,2), (5,8), (4,6), (3,4), (2,7), (1,1)), List((8,3), (7,6), (6,4), (5,2), (4,8), (3,5), (2,7), (1,1)), List((8,5), (7,7), (6,1), (5,3), (4,8), (3,6), (2,4), (1,2)), List((8,4), (7,6), (6,8), (5,3), (4,1), ... // 10×10です…省略されてますが…一杯ありますね(´・ω・｀) scala> queens(10) res23: List[List[(Int, Int)]] = List(List((10,7), (9,4), (8,2), (7,9), (6,5), (5,10), (4,8), (3,6), (2,3), (1,1)), List((10,8), (9,5), (8,2), (7,4), (6,10), (5,7), (4,9), (3,6), (2,3), (1,1)), List((10,5), (9,8), (8,2), (7,4), (6,10), (5,7), (4,9), (3,6), (2,3), (1,1)), List((10,6), (9,8), (8,5), (7,2), (6,4), (5,10), (4,7), (3,9), (2,3), (1,1)), List((10,7), (9,5), (8,2), (7,8), (6,1...
おおー、できた(｀・ω・´)なんだか数学チックな内容でなんだかノスタルジックな気分になりましたが、こういう解法を考えるのも面白いもんですね…ちょっぴり悩んでしまったのは秘密ですが(´・ω・｀)
