S-JIS[2011-04-30] 変更履歴

Scala 検索実験

Scalaでコレクション内の値を1つ検索する方法を考えてみる。

単純な検索

コレクション（Seq等）に条件を満たす値が入っているかどうかを調べるメソッドはいくつか提供されている。

val seq = Seq(1,2,3,4,5,6,7,8,9,10)
seq.メソッド

scala> seq.find(_%4 == 0)
res1: Option[Int] = Some(4)

scala> seq.findIndexOf(_%4 == 0)
res2: Int = 3

scala> seq.indexWhere(_%4 == 0)
res4: Int = 3

scala> seq.exists(_%4 == 0)
res8: Boolean = true

変換して判定し、それを取得

コレクション（Seq等）内の要素を変換して、その変換結果が条件を満たす、最初の変換結果を受け取りたい場合はどうすればよいか？

単純に考えれば、変換はmapメソッドを使うので、それとfindを組み合わせればいい。

case class C(n: Int) {
  def p = { n%4 == 0 }
}

val seq = Seq(1,2,3,4,5,6,7,8,9,10)

scala> seq.map(new C(_)).find(_.p)
res16: Option[C] = Some(C(4))

しかしこの方法だと、全ての要素に対してCのインスタンスを生成することになってしまう。
変換が軽い処理ならそれでもいいかもしれないが、重い処理では無駄が大きい。

findやexistsの様に、見つかったら途中で中断する方法を流用してみるのはどうだろう。こいつらどうやって実装しているのかな？
と思ってScala2.8.1のソースを見てみた。

def find(p: A => Boolean): Option[A] = {
  var result: Option[A] = None
  breakable {
    for (x <- this)
      if (p(x)) { result = Some(x); break }
  }
  result
}

def indexWhere(p: A => Boolean, from: Int): Int = {
  var i = from
  var it = iterator.drop(from)
  while (it.hasNext) {
    if (p(it.next())) return i
    else i += 1
  }

  -1
}

def find(p: A => Boolean): Option[A] = {
  var res: Option[A] = None
  while (res.isEmpty && hasNext) {
    val e = next()
    if (p(e)) res = Some(e)
  }
  res
}

ライブラリーの中は結構てんでんばらばらだし、varとかループとか剥き出しだな(苦笑)
まぁそれが隠蔽できていればいいのか。

という訳でこれを参考にすると、

implicit def seqMapFind[A](seq: Seq[A]) = new {
  def mapFind[B](f: A=>B)(p: B=>Boolean): Option[B] = {
    var res: Option[B] = None
    val i = seq.iterator
    while (res.isEmpty && i.hasNext) {
      val e = f(i.next())
      if (p(e)) res = Some(e)
    }
    res
  }
}

scala> seq.mapFind(new C(_))(_.p)
res20: Option[C] = Some(C(4))

それから、例によって再帰関数を試してみる。

implicit def seqMapFind[A](seq: Seq[A]) = new {
  def mapFind[B](f: A=>B)(p: B=>Boolean): Option[B] = {

    @scala.annotation.tailrec
    def loop(s: Seq[A]): Option[B] = {
      if (s.isEmpty) None
      else {
        val e = f(s.head)
        if (p(e)) Some(e) else loop(s.tail)
      }
    }

    loop(seq)
  }
}

scala> seq.mapFind(new C(_))(_.p)
res26: Option[C] = Some(C(4))

再帰関数を作るのに慣れてくると、これも分かりやすいかもしれないって気がしてきた…(笑)

そこまでして関数を作るのも面倒なので、出来合いのメソッドで何とかする方法も考えてみる。

scala> var res: Option[C] = None
res: Option[C] = None

scala> seq.exists{ e=> val a = new C(e); if(a.p){ res = Some(a); true }else false }
res29: Boolean = true

scala> res
res30: Option[C] = Some(C(4))

うへ、出来たけど、なんか酷い(爆)
existsを呼び出して副作用が発生しているというのが最悪だよね。

ふと、最初のパターンをIteratorで試してみた。

分かりやすいように、呼び出し時のデバッグ出力を入れてみる。

case class C(n: Int) {
  println("C:" + n)

  def p = { println("p:" + n); n%4 == 0 }
}

seq.map(new C(_)).find(_.p)

seq.iterator.map(new C(_)).find(_.p)

おおっ、これは！
単なるSeqのmap・findだと、予想通り最初に全要素に対して変換をかけてから条件判定を行っているが、
Iteratorにすると、判定ごとに変換が実行されている。

今回の要件では、これが一番シンプルな解答かな。