Scalaで話すように素数 - なんたらノート第三期ベータ

最近Scalaが面白いので、例によって「話すように素数」をやってみました。

Python
話すようにプログラムするPythonチュートリアル - なんたらノート第二期
 続・話すようにプログラムするPythonチュートリアル - なんたらノート第二期

さてScalaでは…

普通に書いたもの

def is_prime_number(n:Int):Boolean = {
    !(2 until n).exists((m) => {n % m == 0})
}
def prime_number_until(n:int):Seq[Int] = {
    (1 to n).filter(is_prime_number)
}
println(prime_number_until(100))

(2 to n) とか (2 until n) は、厳密に書くと(2).to(n)という、「オブジェクトのメソッドに引数1個渡す」表現なのですが、Scalaではこのパターンの構文の場合、ドットと括弧を省略できるそうです。省略記法がRubyよりRuby的。

それをもっと短く

println(1 to 100 filter((n) => !(2 until n exists(n % _ == 0))))

ワンライナーでこの長さ(w

型指定しなくても、全部型推論でいけてしまいました。

_を使って高階関数に渡す関数を作ると、無名関数がただの式みたいになってしまいます。

(m) => n % m == 0 //これは
n % _ == 0    //これに変換できる

functionやlambdaって綴るより圧倒的に短いし、平たく読めます。

ダックタイピングなPythonと比べて、filter等の関数が素直にインスタンスのメソッドになっています。また、any+imapのテクニック(最初の1つが見つかった時点でTrueを返す)が最初からexistsという関数として提供されています。

「それ未満の素数で割れるか」で実装

メモ化とか遅延評価を気にしてみる。

import scala.collection.mutable.HashMap

def memoize[A,B](f:(A)=>B):(A)=>B = {
  val memo = HashMap[A,B]()
  (n:A) => { if (!memo.contains(n)) memo(n) = f(n); memo(n) }
}

val is_prime_number = memoize((n:Int) =>
  !(prime_number_until(n-1) exists (n % _ == 0))
)

def prime_number_until(n:Int):Seq[Int] = 2 to n filter is_prime_number
  
println(prime_number_until(100))

型あり言語だけど、型をパラメータ化できるので、一般的なメモ化を実装しやすくて素敵です。入出力をイミュータブルな特性を持った型に限定するともっといいのかな。

遅延なんですが、なんと、シーケンシャルなデータの操作結果がいきなり遅延評価プロクシ(配列コピーじゃなくてイテレータ)だったりするので、とくに工夫してないのに、シーケンスの全コピーを避けることができていました。ただし、知らない間に展開されてしまうと急に重くなるので、抽象的なオブジェクトのまま操作するよう、意識しておく必要がありそうです。なんだかPython3000先取りの気分。

まださわりたてなので、よくわかっていません。もしかしたら、もっといい方法があるかも。

ちょっとやってみた感想は、「どこで型や括弧を省略できるかを間違う」ことが多く、短く書こうとすると、すぐにコンパイラが意図しない解釈をしてしまって大変でした。わかりきっている場合以外は、まず省略せずに書いて、それから可読性のために省略表記にしていく、って感じがいいのだろうか。

追記事項:
xs.find(...) == None を !xs.exists(...) に置き換えました。