Scalaを使ってみる: (7) immutable MultiSetを定義する - 屯遁のパズルとプログラミングの日記

Scalaを勉強している．勉強中の身ではあるが，以下を例題として，Scalaプログラムの作り方について説明してみる．

テキストファイル中に現れる英単語の出現回数を数えて，出現回数の多い語から表示する．

入力のテキストファイルとしては，Project Gutenberg 中のHalmet を用いる(ファイル名を hamlet.txt，改行はLFにした)．
なお利用している環境は，Ubuntu 8.04 LTS上の Scala 2.8.0 RC2 (2010年5月10日リリース)， Java 1.6.0である．

リンク

新しいcollectionの定義

immultableなマルチ集合を定義したいわけだが，どうせなのでScalaの他のcollectionと同様に動作するようにしよう．
Scala 2.8で，新しいcollectionを定義する方法については，以下のWebページが参考になる．

Creating Custom Traversable implementations

Scalaのcollectionは，基本的にはscala.collection.Traversable を継承しているようだ． Traversable なクラスを作成するには，foreach メソッドのみを実現すれば良い．
Traversable のサブクラスとしてscala.collection.Iterable がある． Traversable に対して iterator などのメソッドが追加されている．今回は，こちらを用いることにする．
mutable版の時と同様に case class とし，また constructor を companion object 以外からは隠したいので case class MS[A] private(val amap: Map[A,Int]) と定義する．
スーパークラスとして Iterable[A] だけを継承すると， MS[A] オブジェクトに対して drop(1) などの結果が MS[A] にならない．そこで，上のWebページを参考に GenericTraversableTemplate[A,MS] と IterableLike[A,MS[A] ] をmix-inし， companion object を定義する．

case class MS[A] private(val amap: Map[A,Int]) extends Iterable[A]
with GenericTraversableTemplate[A,MS] with IterableLike[A,MS[A]] {
  override def companion = MS
  def iterator = ....
}

object MS extends TraversableFactory[MS] {
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, MS[A]] =
    new GenericCanBuildFrom[A]
  def newBuilder[A] = .....
}

あとは，iterator と newBuilder を実装すれば，最小限のプログラムとして実行できるはずだ．

iteratorの実装

iterator は Iterable の実装に必須である．ここでは，マルチ集合の要素に対して繰り返しを行うように実装すれば良い．たとえば，以下のようになる．

  def iterator = amap.keysIterator.flatMap{
    elem => Iterator.fill[A](amap(elem))(elem)
  }

newBuilderの実装

newBuilder は，与えられた collection から新しいマルチ集合を生成するためのscala.collection.mutable.Builderオブジェクトを返すメソッドである．たとえば，以下のように定義できる．

  def buildMap[A](elems: List[A]) =
    elems.foldLeft(Map[A,Int]())((m,x) => m + (x -> (m.getOrElse(x,0)+1)))
  def newBuilder[A] =
    new ListBuffer[A] mapResult (elems => new MS(buildMap(elems)))

上では，与えられた collection に対し ListBuffer で一旦 List を生成し，次に生成された List の elems から buildMap を利用して Map を生成し，最後にその Map からマルチ集合を生成している．
このままだと，immutable Map の複製が何度も実行され効率が悪そうなので，以下のように直接 Builder を実装することにする．

  def newBuilder[A] = new Builder[A,MS[A]] {
    private var amap = collection.mutable.Map[A,Int]()
    def clear = amap.clear
    def += (elem: A) = {
      amap += (elem -> (amap.getOrElse(elem,0)+1))
      this
    }
    def result = new MS(amap.toMap)
  }

Builder では，与えられた collection の要素は += で追加される．最終的な生成結果は result の返り値である．
上では，効率のため collection の要素を一旦 mutable Map に登録した後， toMap で immutable な Map に変換してマルチ集合を生成している．

最小限のプログラム

以上を，まとめたものが以下の通りである(apply, toMap を追加している)．

import scala.collection._
import scala.collection.generic._
import scala.collection.mutable.Builder

case class MS[A] private(val amap: Map[A,Int]) extends Iterable[A]
with GenericTraversableTemplate[A,MS] with IterableLike[A,MS[A]] {
  override def companion = MS
  def iterator = keysIterator.flatMap{
    elem => Iterator.fill[A](amap(elem))(elem)
  }
  def apply(elem: A) = amap.getOrElse(elem, 0)
  def toMap = amap
}

object MS extends TraversableFactory[MS] {
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, MS[A]] =
    new GenericCanBuildFrom[A]
  def newBuilder[A] = new Builder[A,MS[A]] {
    private var amap = collection.mutable.Map[A,Int]()
    def clear = amap.clear
    def += (elem: A) = {
      amap += (elem -> (amap.getOrElse(elem,0)+1))
      this
    }
    def result = new MS(amap.toMap)
  }
}

実行

上記のプログラムを REPLで :load するのはエラーになる(companion object の MS を前方参照しているため)．そのため，scalac でコンパイルしてから実行する必要がある．

  scala> val ms = MS("a", "b", "b")
  ms: MS[java.lang.String] = MS(a, b, b)

  scala> ms("b")
  Int = 2

  scala> ms.toList
  List[java.lang.String] = List(a, b, b)

  scala> ms.size
  Int = 3

  scala> ms ++ List("a", "c")
  MS[java.lang.String] = MS(a, a, c, b, b)

  scala> ms.map(x => "c")
  MS[java.lang.String] = MS(c, c, c)

  scala> ms.map(x => "c").toMap
  scala.collection.Map[java.lang.String,Int] = Map((c,3))