Scalaプログラミング4 Listを使ってみる

Beginning Scala programming4

初心者ぺちぱーがGitHubでScalaレッスンを始めたぞ。4回目はコレクションクラスのListを使ってみよう。

引き続き、練習問題はここのページだ。今回の問題は素数を求めるやつだ。

Scalaスケーラブルプログラミング第2版
作者: Martin Odersky; Lex Spoon; Bill Venners
出版社: インプレスジャパン
発売日: 2011-09-27
メディア: 単行本（ソフトカバー）
価格: ￥ 4,968

Lessen 4: Sieve of Eratosthenes

素数判定

与えられた数が素数かどうか調べる

あるいは与えられた数までの素数を列挙する

素数判定に使うアルゴリズムで有名なものはエラトステネスの篩だ。今回の問題では、wikipediaに書いてある手順をScalaで実装してみようと思う。

ステップ1: 整数を最初の素数である 2 から昇順で探索リストに羅列する。

ステップ2: リストの先頭の数を素数リストに記録する。

ステップ3: 前のステップで素数リストに加えられた数の全ての倍数を、探索リストから削除する。

ステップ4: 探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。探索リストの最大値が素数リストの最大値の平方よりも大きい場合、ステップ 2 に戻る。

step 1

まず、ステップ1はScalaだと簡単よね。1回目のレッスンでも出てきたやり方で出来る。

val range = 2 to 10

このrangeの範囲から素数を探すわけだ。

step2

ステップ2は、このrangeの先頭を取り出す。これもScalaだと簡単で、headメソッドを使えばいい。

val list = List(range.head)

このlistに判明した素数が記録されていくんだな、きっと。ここで使っているListはimmutable.Listだから、実際には別のインスタンスになるんだと思う。rangeも同じくimmutable.Rangeなので、実際には同じインスタンスを使い回すわけではなくて、新しいインスタンスを作ることになるはずだ。

step3

ステップ3は、このlistの最後の要素で割り算して余りが0の要素をrangeから消す。ここの処理にはfilter()メソッドが使えそうだ。

range.filter(...)

filter()メソッドに渡す引数は、条件となる関数だ。filter()メソッドは条件が真になった要素を返すので、

余りが0の要素を消す -> 余りが0でない要素を残す

と読み替えると、こんな感じで書けるはずだ。

val last = list.last
val range1 = range.filter(i => i % last != 0)

filter

filter()の引数についてちょっと補足。この関数は高階関数なので、関数を引数にとる。引数になる関数は、

T => Boolean

のような格好をしてる。T型の引数を受け取って、Booleanを返す関数だ。今はInt型のコレクションを使っているから、Int型の引数を受け取って、Booleanを返す関数をfilter()に渡している。JavaScriptとかPythonとかPHPでも、こんなやついたよね。

Function literal

コップ本の8章を見てみよう。p.153を見ると、こんな事をやっている。

var increase = (x: Int) => x + 1

JavaScriptでもよく見かける格好してるよね。無名関数の書き方と一緒だ。

// これはScalaじゃなくてjs
var increase = function(x) { return x + 1; }

filter()に渡している引数は、この関数リテラルを使っている。関数定義して名前を付けなくてもいい場合は、便利よね。p.155にちょうどfilter()を使った例が載っている。

REPL

ちょっとREPLで試してみよう。ターミナルを起動して、scalaって打ってみよう。

scala> val range = 2 to 10
range: scala.collection.immutable.Range.Inclusive = Range(2, 3, 4, 5, 6, 7, 8, 9, 10)
 
scala> val list = List(range.head)
list: List[Int] = List(2)
 
scala> val last = list.last
last: Int = 2
 
scala> val range1 = range.filter(i => i % last != 0)
range1: scala.collection.immutable.IndexedSeq[Int] = Vector(3, 5, 7, 9)

確かにrange1から2の倍数が消えてるよね。ここまでは大丈夫そうだ。range1の型がRangeじゃなくてVectorになってるけど、これもSeq型の一つらしいぞ。後でちょっと調べてみよう。

step4

ステップ4は、ややこしそうだな。"探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。"と言っているのは、こういうことか。

val listMax = math.pow(list.max, 2) // 素数リストの最大値の平方
val rangeMax = range1.max // 探索リストの最大値
 
if (rangeMax < listMax2) {
  val primes = list ::: range1.toList // これが素数だ！
} else {
  // ...
}

最大値はmaxメソッドで取得できる。最後の条件式がelseになる場合は、ステップ2に戻って、同じことを繰り返すと。再帰関数になりそうよね、これ。

::: operator

Listの要素と、別のListの要素を合わせて、新しいListを作る場合にはコロン3つの演算子を使う。

scala> val newList = List(1, 2) ::: List(5, 6)
newList: List[Int] = List(1, 2, 5, 6)

別の型からListに変換するときはtoListメソッドを使う。

scala> val range = 2 to 10
range: scala.collection.immutable.Range.Inclusive = Range(2, 3, 4, 5, 6, 7, 8, 9, 10)
 
scala> range.toList
res2: List[Int] = List(2, 3, 4, 5, 6, 7, 8, 9, 10)

Create function

まずは、ここまでの手順をまとめてみよう。

// step1
val range = 2 to 10
 
// step2
val list = List(range.head)
 
// step3
val last = list.last
val range1 = range.filter(i => i % last != 0)
 
// step4
if (range1.max < math.pow(list.max, 2)) {
  list ::: range1.toList
} else {
  // back to step2
  val list1 = list ::: List(range1.head)
  // step3
  // ...
}

最後のステップ2に戻るところで、新しく作った素数リストのlist1と、探索リストのrange1を関数に渡さないといけないだろうから、この2つを引数にした方が良さそうだ。ちょっと書いてみよう。

def eratosthenesSieve(list: List[Int], range: Seq[Int]): List[Int] = {
  // step3
  val last = list.last
  val range1 = range.filter(i => i % last != 0)
 
  // step4
  if (range1.max < math.pow(list.max, 2)) {
    list ::: range1.toList
  } else {
    // back to step2
    val list1 = list ::: List(range1.head)
    // step3
    eratosthenesSieve(list1, range1)
  }
}

これだけだと、最初にステップ1とステップ2を実行するところがないから、その関数も追加してみよう。

def toList(max: Int): List[Int] = {
  // step1
  val range = 2 to max
 
  // step2
  val list = List(range.head)
 
  eratosthenesSieve(list, range)
}

これで、toList(max)を実行すると、maxまでの素数を求める部分が出来たんじゃないか！？

Test your code!

どうも不格好な気もするけれど、ここまでの段階で書いたコードを整理してみたのが、このobjectだ。eratosthenesSieve()メソッドは外部から呼ばれる事はないはずだから、privateを付けてみた。このオブジェクトが公開するのはtoList()メソッドだけだ。

object MyFirstPrimeNumber {
  def toList(max: Int): List[Int] = {
    // step1
    val range = 2 to max
 
    // step2
    val list = List(range.head)
 
    eratosthenesSieve(list, range)
  }
 
  private
  def eratosthenesSieve(list: List[Int], range: Seq[Int]): List[Int] = {
    // step3
    val last = list.last
    val range1 = range.filter(i => i % last != 0)
 
    // step4
    if (range1.max < math.pow(list.max, 2)) {
      list ::: range1.toList
    } else {
      // back to step2
      val list1 = list ::: List(range1.head)
      // step3
      eratosthenesSieve(list1, range1)
    }
  }
}

よし。じゃあテストしてみよう。はて？ところで、Scalaのユニットテストって何を使うんだろう。コップ本の14章を読んでみると、Scala向けのテスティングフレームワークって、いくつかあるらしい。

最初はxUnit使うのが無難だろうか。ScalaTest 1.9.1 (for 2.10.0+ and 2.9.0+)が現時点の最新版だったので、これを使ってみる。ScalaTestではいくつかのスタイルでテストコードが書けるらしい。xUnitっぽい書き方をするのは、FunSuiteかな。

Getting started with FunSuiteを参考に、テストコードを書いてみよう。

import org.scalatest.FunSuite
 
class MyFirstPrimeNumberTest extends FunSuite {
  test("Prime numbers ranging from 2 to 20 are 2, 3, 5, 7, 11, 13, 17, 19") {
    val expect = List(2, 3, 5, 7, 11, 13, 17, 19)
    val actual = MyFirstPrimeNumber.toList(20)
    assert(expect == actual)
  }
}

IntelliJ IDEAでの実行結果

Testing started at 9:41 ...
- Prime numbers ranging from 2 to 20 are 2, 3, 5, 7, 11, 13, 17, 19

おお！エラーが出てないってことはうまく動いたんじゃないか！？やったね！Scalaでテストできるようになったよ！

FunSuiteのScalaDocを見てみると、assert()だけじゃなくて、expectResult()()も使えるみたいだ。これを使って、テストコードを書き換えてみよう。

import org.scalatest.FunSuite
 
class MyFirstPrimeNumberTest extends FunSuite {
  test("Prime numbers ranging from 2 to 20 are 2, 3, 5, 7, 11, 13, 17, 19") {
    expectResult(List(2, 3, 5, 7, 11, 13, 17, 19))(MyFirstPrimeNumber.toList(20))
  }
}

最初の引数に期待値を渡して、次の括弧の引数に実行結果を渡す書き方なんだな。

Refactor

少し長くなってしまったので、リファクタリングは次回やろうと思う。

Conclusion

今回も色々出てきたな。まとめ。

head、 last、 max、 :::、 toListなど、ListやRangeの基本操作
filter()メソッドの使い方
関数リテラルの使い方
ScalaTest, FunSuiteでユニットテスト