読者です 読者をやめる 読者になる 読者になる

Scalaはじめました

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は素数の問題で、エラトステネスのふるいが必要になります。
が、末尾再帰にしても異様に時間がかかっているので、次回の更新までの自分への宿題ということで…