8月の終わりに最寄りの本屋さんが潰れました(´・ω・`)
そこでちょっと足を伸ばして大きめのところに行くと、そこには関数脳本が。
関数型言語は、リリカルLispをちょっと触った & Haskell最速マスターを斜め読み、くらいしかしたことがなかったので、今度は真面目にやってみることに。
本の中身についてはまた後日ということで、とりあえずおなじみのProject Eulerでいろいろと書いてみることにしました。
普通に手続き型っぽく書いても面白くないので、
・できるだけ副作用の無いように
・再帰は基本的に末尾再帰になるように
という制約でやってみることにしました。
import scala.annotation.tailrec object Main { def main(args: Array[String]) { // Problem 1 println((1 until 1000).filter(n => n % 3 == 0 || n % 5 == 0).sum) // Problem 2 @tailrec def fib(ls: List[Int], n: Int, finish: Int): List[Int] = { if (ls.size > 0 && ls(0) > finish) ls.tail else { val c = n match { case 1 => 1 case 2 => 2 case _ => ls(0) + ls(1) } fib(c :: ls, n + 1, finish) } } println(fib(Nil, 1, 4000000).filter(_ % 2 == 0).sum) // Problem 3 /* @tailrec def factor(n: Long, acc: List[Long]): List[Long] = { if (n == 1) acc else { for (i <- 2L to n if n % i == 0) { return factor(n / i, i :: acc) } Nil } } */ def factor(n: Long, acc: List[Long]): List[Long] = { if (n == 1) acc else { var i = 2L while (i <= n) { if (n % i == 0) return factor(n / i, i :: acc) i += 1 } Nil } } println(factor(600851475143L, Nil).max) // Problem 4 println((for(i <- 999 to 100 by -1; j <- 999 to 100 by -1) yield(i * j)).filter(n => n.toString == n.toString.reverse).max) // Problem 5 @tailrec def gcd(a: Int, b: Int): Int = if(b == 0) a else gcd(b, a % b) def lcm(a: Int, b: Int) = a / gcd(Math.max(a, b), Math.min(a, b)) * b println((1 to 20).foldLeft(1)(lcm)) // Problem 6 println(Math.pow((1 to 100).sum, 2).toInt - (1 to 100).map{Math.pow(_, 2).toInt}.sum) } }
Problem 3はなんか負けた気がしますよね。
Long型のRangeクラスというのが無いみたいなので、2L to n でメモリ足りなくて死亡 => 仕方ないのでwhile文で、という結果に。
コメント欄で、id:kmizushimaさんにご指摘をいただきました。
RangeにはInteger.MAX_VALUE個以上の要素を持てないという制限があり、それに引っかかっていたようです。
Problem 7は素数の問題で、エラトステネスのふるいが必要になります。
が、末尾再帰にしても異様に時間がかかっているので、次回の更新までの自分への宿題ということで…