プログラミングHaskellをScalaで解く
1週間ほど掛けて、じっくりと取り組んだ『プログラミングHaskell』は、全ての関数型言語独学者が読むべき、と感じるほど、優れた内容と構成だった*1。
教科書として洗練しており、最初から読み進め、手を動かすことで、Haskellを通してプログラミングの基礎、関数型言語の特徴をしっかりと学ぶことが出来た。
 | プログラミングHaskell |
Haskellの簡潔さを本の中でまざまざと見せられ、ふと、他の関数型言語、ここでは試しに(最近流行の)Scalaで例や練習問題を書いてみたらどうなるのだろうと思い、やってみた。
簡単に、定義と実装のみを書く。得られる結果は『プログラミングHaskell』を参照して欲しい。
なお、現在はてなダイアリーのスーパーpre記法シンタックスハイライト対応言語にScalaは含まれていない。 このエントリィを公開した翌日対応というタイミングの良さ。
P.8 Quick sort
Haskellの簡潔さを見せる上で、よく使われるクイックソート。Haskell版だとwhereで局所関数smallerとlargerを作っているが、Scala版は外に出した。
def smaller(t:Int, ts:List[Int]):List[Int] = { for(s <- ts; if s <= t) yield s } def larger(t:Int, ts:List[Int]):List[Int] = { for(s <- ts; if s > t) yield s } def qsort(xs:List[Int]):List[Int] = { xs match { case List() => List() case y::ys => qsort(smaller(y,ys)) ::: List(y) ::: qsort(larger(y,ys)) } }
smallerとlargerの定義が冗長だと思うなら、filterを使って書くことも出来る。
def qsort(xs:List[Int]):List[Int] = { xs match { case List() => List() case y::ys => qsort(ys filter(y > _)) ::: List(y) ::: qsort(ys filter(y < _)) } }
P.12~13 リスト操作
Haskellと違って、Scalaはリスト操作のための組み込み関数が無く、大抵はリストのメソッドとして定義されている(Rubyっぽい)。
> List(3,4,5,6).head // 先頭要素 > List(3,4,5,6).tail // 先頭要素を取り除く > List(3,4,5,6)(2) // 第n番目の値 > List(3,4,5,6).take(3) // 先頭からn個の要素 > List(3,4,5,6).drop(3) // 先頭からn個の要素を取り除く > List(3,4,5,6).length // リスト長さ > List(3,4,5,6) ::: List(6,5,3,4) // リスト連結 > 1 :: List(2,3,4,5) // リストの先頭に要素追加 > List(3,4,5,6).reverse // リスト逆順
P.43 練習問題4.8.1
関数を多相関数にしたいなら、Anyを使う。
> def halve(xs:List[Any]):(List[Any],List[Any]) = {val l = xs.length / 2; (xs.take(l),xs.drop(l))}
P.45 リスト内包表記
『プログラミングHaskell』はリスト内包表記が大好きの様で、練習問題でも頻出する。Scalaではfor文/yieldを使うことで、同じ結果を得ることが出来る。
> for(x <- List(1,2,3); y <- List(4,5)) yield (x,y)
P.46 複数の生成器を用いたリスト内包表記
;で区切ること。生成器に m to n を用いると、結果は Seq.Projection になるので、Listに変換するならtoListメソッドを使う。
> var l = for(x <- 1 to 3; y <- x to 3) yield (x,y) // Seq.Projection[(Int, Int)] > l.toList
P.46 concat
concat関数をそのまま定義する方法もあるし、reduceLeftで畳み込むことも出来る。
> def concat(xss:List[List[Any]]):List[Any] = for(xs <- xss; x <- xs) yield x > xss.reduceLeft((xs, x) => xs ::: x)
P.47 正整数の約数リスト
ガードはifが必要(Haskellに慣れ過ぎるとifを忘れがちになるから注意)。
> def factors(n:Int):List[Int] = {val xs = for(x <- 1 to n; if n % x == 0) yield x; xs.toList}
P.47 素数であるかの判定
primeである数が素数であるかの判定、primesで2からある数までの範囲に含まれる素数の列挙。
> def prime(n:Int):Boolean = factors(n) == List(1,n) > def primes(n:Int):List[Int] = { val xs = for(x <- 2 to n; if prime(x)) yield x; xs.toList }
P.48 リストから隣り合う要素を組を作る
zipもリストのメソッド。
> def pairs(xs:List[Any]):List[(Any,Any)] = xs.zip(xs.tail)
P.49 目的の値がリストのどの位置にあるか
局所関数nを定義するまでもない。
> def positions(x:Any, xs:List[Any]):List[Int] = { for((x1, i) <- xs.zip((0 to xs.length - 1).toList); if x == x1) yield i }
P.49 文字列
文字列はjava.lang.Stringであり、明示的にリストにするには "Scala文字列".toList とする必要がある。
シーザー暗号の話は省略(面白いのでやってみた方が良い)。
P.55 練習問題5.7.1
累乗演算子無いのか……。^を別の目的で使っている言語は大抵こうだ。
> (for(x <- (1 to 100).toList) yield Math.pow(x, 2)).reduceLeft((sum,x) => sum + x)
P.55 練習問題5.7.2
> def replicate(n:Int, s:Any):List[Any] = for(i <- (1 to n).toList) yield s
P.55 練習問題5.7.3
もう少し効率的に書くことも出来る(あえて凡レベルで)。
> def pyths(n:Int):List[(Int, Int, Int)] = (for(x <- 1 to n; y <- 1 to n; z <- 1 to n; if Math.pow(x,2) + Math.pow(y,2) == Math.pow(z,2)) yield (x,y,z)).toList
P.55 練習問題5.7.4
sumはもう少し上手く書けないっけ……。
> def perfects(n:Int):List[Int] = for(x <- (2 to n).toList; if factors(x).init.reduceLeft((sum,x) => sum + x) == x) yield x
P.55 練習問題5.7.7
タプルの要素アクセスは不細工。
> def scalarproduct(xs:List[Int],ys:List[Int]):Int = (for(i <- xs.zip(ys)) yield i._1 * i._2).reduceLeft((sum,x) => sum + x)
今回はここまで。
-
-
- -
-
