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

Beginning Scala programming4

初心者ぺちぱーがGitHubでScalaレッスンを始めたぞ。今回は、4回目の問題をリファクタリングしてみよう。

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

Lessen 4: Sieve of Eratosthenes

前回はこんなobjectを作ってみた。

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)
    }
  }
}

テストコードはこんなのを書いてみた。

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 Sieve of Eratosthenes

まずは、val宣言しているところが冗長な気がするので、一度しか参照されてない部分については、ちょっと直してみよう。

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

toList(max)の7行目のList(range.head)は、初回は2であることが自明だから、List(2)でも良さそうだ。

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

じゃあ、テストしてみよう。クラス名を変えただけで、テストコードの中身は一緒だ。

class MyFirstPrimeNumber2Test 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))(MyFirstPrimeNumber2.toList(20))
  }
}

テスト結果

Testing started at 18:19 ...
- Prime numbers ranging from 2 to 20 are 2, 3, 5, 7, 11, 13, 17, 19
 
Process finished with exit code 0

よし。ちゃんと動いてそうだな。

Remember FizzBuzz

eratosthenesSieve(list, range)メソッドをよく見ると、ステップ3で作ったrange1というコレクションに対して、ステップ4で別のコレクションを作っている。これって、2回目のFizzBuzzで見たコードとよく似てるコードだ。ステップ4もif式じゃなくて、パターンマッチにしてみると、rangeに対して、filterした後、続けてmatchと書けそうだ。

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

Placeholder syntax

コップ本のp.155を見てみよう。関数リテラルを簡潔にするプレースホルダー構文というのがあるらしい。

パラメーターが関数リテラル内で1度しか使われない場合には、1個以上のパラメーターのプレースホルダー（場所を用意していることを示す記号）として、アンダースコアを使うことができる。

例として載っているのは、0よりも大きい数字を返す処理だ。

sumNumbers.filter(_ > 0)
//実は下の表現を簡略化したもの
sumNumbers.filter(x => x > 0)

ということは、MyFirstPrimeNumber3の11行目はちょっと簡単になる。

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

テストしてみよう。テストコードは中身が一緒でクラス名をMyFirstPrimeNumber3に変えただけなので省略。

テスト結果

Testing started at 18:49 ...
- Prime numbers ranging from 2 to 20 are 2, 3, 5, 7, 11, 13, 17, 19
 
Process finished with exit code 0

よし。大丈夫だ。

List operation

さて、コップ本をまた開いてみよう。今度はp.324だ。表17.1 集合の一般的な操作をよく見てみると、++演算子というのがある。

val nums = Set(1, 2, 3)
num ++ List(5, 6) // => Set(1, 2, 3, 5, 6)

型が違うコレクションでも自動的に変換して要素を追加したコレクションを作っているように見えるね。ちょっと試してみよう。

scala> val list = List(1, 2)
list: List[Int] = List(1, 2)
 
scala> val range = 5 to 7
range: scala.collection.immutable.Range.Inclusive = Range(5, 6, 7)
 
scala> val newList = list ++ range
newList: List[Int] = List(1, 2, 5, 6, 7)

おお！動いた！左側の型に合わせて、要素を追加したコレクションを作る操作なのかな。

そうすると、MyFirstPrimeNumber3の14行目の

list ::: range1.toList

この部分もtoListする必要はなくて++すればいいんだな。

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

Use head instead of last

コップ本のp.297を見てみよう。

headやtailはともに一定の時間で実行されるが、initとlastはリスト全体をたどらないと結果値を計算できないので、リストの長さに比例する計算時間を要する

と書いてある。11行目のlist.lastというのは、追加された値を示すわけだから、これも引数で渡すようにしてみよう。

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

テストーー

テスト結果

Testing started at 19:24 ...
- Prime numbers ranging from 2 to 20 are 2, 3, 5, 7, 11, 13, 17, 19
 
Process finished with exit code 0

よしよし。ちゃんと動いてるぞ。

1 is not prime number

そういえば、1って素数じゃなかったよね。

1を渡したときのテストコードを追加してみよう。

test("1 is not prime number") {
    expectResult(List())(MyFirstPrimeNumber4.toList(1))
  }

テスト結果

Testing started at 19:29 ...
- Prime numbers ranging from 2 to 20 are 2, 3, 5, 7, 11, 13, 17, 19
 
empty.max
java.lang.UnsupportedOperationException: empty.max
    …略
 
Process finished with exit code 0

あー。。なんか例外出てきた。14行目のrange1.maxがいけないみたいだ。要素が空の場合はmax使えないよ？ってことか。

1以下の場合は素数の計算をする必要はなくて、List()を返せばいいし、2の場合はList(2)を返せばいいわけだから、toList(max)を変更すれば良さそうだ。これはパターンマッチで出来そうだな。

object MyFirstPrimeNumber5 {
  def toList(max: Int): List[Int] = max match {
    case max if max <= 1 => List()
    case max if max == 2 => List(2)
    // step1
    // step2
    case _ => eratosthenesSieve(2, List(2), 2 to max)
  }
 
  private
  def eratosthenesSieve(last: Int, list: List[Int], range: Seq[Int]): List[Int] = range.filter {
    // step3
    _ % last != 0
  } match {
    // step4
    case range1 if range1.max < math.pow(list.max, 2) => list ++ range1
    // back to step2
    // step3
    case range1 => eratosthenesSieve(range1.head, list ::: List(range1.head), range1)
  }
}

テストコードにも、2と0と-1の場合を追加してみよう。

class MyFirstPrimeNumber5Test 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))(MyFirstPrimeNumber5.toList(20))
  }
 
  test("2 is prime number") {
    expectResult(List(2))(MyFirstPrimeNumber5.toList(2))
  }
 
  test("1 is not prime number") {
    expectResult(List())(MyFirstPrimeNumber5.toList(1))
  }
 
  test("0 is not prime number") {
    expectResult(List())(MyFirstPrimeNumber5.toList(0))
  }
 
  test("-1 is not prime number") {
    expectResult(List())(MyFirstPrimeNumber5.toList(-1))
  }
}

テスト結果

Testing started at 19:57 ...
- Prime numbers ranging from 2 to 20 are 2, 3, 5, 7, 11, 13, 17, 19
- 2 is prime number
- 1 is not prime number
- 0 is not prime number
- -1 is not prime number
 
Process finished with exit code 0

よし。なんとかなったぞ。

Tail recursion

IntelliJ IDEAを使っていると、今回作ったeratosthenesSieveの左側に、サンジのグルグル眉毛みたいなマークが出ていないだろうか。

これは、この関数が末尾再帰だということを表すマークらしい。

のp.166を読んでみよう。最適化されるみたいね。

Scalaコンパイラーは末尾再帰を検出したら、パラメーターを新しい値に更新した後、再帰呼び出しを関数の冒頭にジャンプするコードに書き換えるのである。

以上からわかるように、問題を解決するために再帰アルゴリズムを使うことを躊躇してはならない。再帰による解は、ループを使った解よりも優美で簡潔になることがよくある。解が末尾再帰になっていれば、実行時に余計なオーバーヘッドがかかったりはしない。

Conclusion

前回書いたコードと比べると、ずいぶんScalaっぽくなったんじゃないか！？どうだろうか。次回はtoList()を使ったcontains()メソッドを作ってみようと思う。

まとめ！

関数リテラルのプレースホルダー構文いいよ！
++演算子でListとRangeから要素を合わせたコレクションを作れる
末尾再帰はScalaコンパイラーで最適化される