Scala Tips / Streamで脱出

関数型プログラミングでは、遅延評価を用いて大量データを処理するのが定番のテクニックになっています。パズルを解く問題のアルゴリズムによく出てきますね。

ただ、業務アプリケーションではパズルを解くようなロジックを書くことは稀なので、こういったテクニックの存在は知っていても、なかなか使う機会はないのではないでしょうか。

とはいえ、この手のテクニックの引き出しはできるだけ多いにこしたことはありませんし、来るべきメニーコア時代の並列プログラミングでは必須のテクニックになりそうな予感もあります。このため、機会があれば使って慣れておくのが得策ですが、これに適した普段使いできるテクニックが欲しいところです。

問題

関数fは引数のIntをそのまま返す関数です。実行の確認をするためにprintln関数で、受け取ったIntをコンソールに表示します。

val f = (x: Int) => {
  println(x)
  x
}

次に、Seq[Int]を引数に取り、関数を適用した結果が条件似合うものが見つかったら、計算前の値を返すという関数legacyを定義します。

ループ内でif式で条件判定してreturnで強制的に関数から脱出しています。returnによる強制復帰は手続き型としてはごく普通の書き方です。

def legacy(xs: Seq[Int], f: Int => Int): Option[Int] = {
  for (x <- xs) {
    if (f(x) == 3) return Some(x)
  }
  return None
}

実行結果は以下になります。

scala> legacy(List(1, 2, 3, 4, 5), f)
1
2
3
res3: Option[Int] = Some(3)

関数型

Scalaで関数型的なプログラミングに慣れてくると、returnで強制脱出するようなコーディングに違和感が出てきます。そして、コンビネータを使った以下のようなコーディングを多用するようになります。

scala> List(1, 2, 3, 4, 5).map(f).find(_ == 3)
1
2
3
4
5
res33: Option[Int] = Some(3)

実行の結果無事、正しい結果が帰ってきました。コーディングも簡潔なので万々歳に思えますが、問題がひとつあります。

正しい結果を返すということに関して、List内の4, 5を関数fで評価することは不要ですが、上記の処理では評価が行われています。この例は要素数が5つしかないので実用上は問題ありませんが、1万件のデータに対して3件目で条件がヒットするにもかかわらず、残り9997件の評価が行われるようになってしまうとなると、これはちょっとした事件です。

遅延評価

ここで登場するのが遅延評価です。

ListをStreamに変えると、Steram内の要素に対してmapメソッドで関数fが適用されるタイミングが変わり、不要な要素に対する評価が行われないようになります。

scala> Stream(1, 2, 3, 4, 5).map(f).find(_ == 3)
1
2
3
res34: Option[Int] = Some(3)

関数legacyと同様の動きですね。要素1, 2, 3への評価は行われるものの、要素4, 5への評価は行われずに済みました。

Streamは、ListやVectorと同様にSeqなので使い方は難しくありません。普通にSeqとして使っていけばよいわけですが、コンビネータで値が評価されるタイミングが事前一括評価ではなく、必要時の個別評価になる点が異なります。

今回は普段使いのプログラミングでこの性質を利用するパターンを見つけました。他にも色々あるはずなので、うまくパターンとして採取していきたいと思います。

諸元

• Scala 2.10.0-RC1