プログラミングHaskellをScalaで解く(その2)

Scala

引き続き、『プログラミングHaskell』の例題と練習問題をScalaで書いてみる。

Graham Hutton - プログラミングHaskell

プログラミングHaskell
Graham Hutton

前回の改良

前回作った関数 halve, pairs, positions 等はリストを1つ取って値を返すので、リストのメソッドとした方がScalaらしい。

Implicit Conversion という機能を利用して、コンストラクタで既存クラスを引数として取る独自クラスを定義し、implicit def変換を定義することで暗黙的型変換が行われて、既存クラスにメソッドを追加したように見せることが出来る。

詳しくは http://dl.dropbox.com/u/261418/scala-hackathon/advanced/implicits.html などを参照すること。

class MyList[T](val xs:List[T]) {
    def halve:(List[T],List[T]) = {val l = xs.length / 2; (xs.take(l),xs.drop(l))}
    def pairs:List[(T,T)] = xs.zip(xs.tail)
    def positions(x:T):List[Int] = { for((x1, i) <- xs.zip((0 to xs.length - 1).toList); if x == x1) yield i }
}
implicit def list2MyList[T](xs:List[T]):MyList[T] = new MyList(xs)

scala> :l mylist.scala
Loading test.scala...
defined class MyList
list2MyList: [T](List[T])MyList[T]

scala> List(1,2,3,4,5,4).positions(4)  // Listという既存クラスにpositionsというメソッドは無い
res19: List[Int] = List(3, 5)          // 暗黙的型変換によってMyListのメソッドを参照した

使い過ぎると危険な気がするが、便利なので活用しよう。

ここで、Tという型を前回Anyを使った場所で使ったが、これは型推論させるための指定。classでもdefでも使える。List[Any] などと(特に返り型の指定の際に)書くと、関数が返す値が常にList[Any]となり、都合が悪い場合がある。

scala> def replicate(n:Int, s:Any):List[Any] = for(i <- (1 to n).toList) yield s
replicate: (Int,Any)List[Any]

scala> replicate(3,true)
res20: List[Any] = List(true, true, true)

scala> def replicate[T](n:Int, s:T):List[T] = for(i <- (1 to n).toList) yield s
replicate: [T](Int,T)List[T]

scala> replicate(3,true)
res21: List[Boolean] = List(true, true, true)

『プログラミングHaskell』を底本として練習問題などを解いており、あまりScalaらしい記述/技を取り入れ過ぎると、Haskellとの比較が見え難いと感じるかもしれない。

従って今後もこの「プログラミングHaskellをScalaで解く」シリーズでは、クラスのメソッドとしてでなく関数として定義する、また、(Haskellでいう a として)Anyを用いることとするが、Scalaを本格的に使う時は型推論Tを用いることをお勧めする。


P.59 リストの長さ

> def length(l:List[Any]):Int = {l match { case Nil => 0; case (x::xs) => 1 + length(xs) }}

P.60 逆順リスト

> def reverse(l:List[Any]):List[Any] = { l match { case Nil => Nil; case (x::xs) => reverse(xs):::List(x) }}

P.61 リストに要素を挿入 と Insertion Sort

Any型は <= という演算子(if文の中で使っている)を持っていないため、ここではList[Int]に限定した。

> def insert(x:Int, l:List[Int]):List[Int] = { l match { case Nil => List(x); case (y::ys) => if(x <= y) x::y::ys else y::insert(x,ys) }}
> def isort(l:List[Int]):List[Int] = { l match { case Nil => Nil; case (x::xs) => insert(x, isort(xs)) }}

P.63 フィボナッチ数列

Scalaのmatch-caseに(n + k)パターンは使えないようだ。Haskellの方でも使用不可になるかもと言われているし、使うべきではないだろう。

> def fibonacci(n:Int):Int = { n match { case 0 => 0; case 1 => 1; case _ => fibonacci(n - 2) + fibonacci(n - 1) }}

P.63 相互再帰

Scalaだと出来ないみたい。先に宣言して後で実装とか、出来る気がするけどな。

P.71 練習問題6.8.3

> def and(l:List[Boolean]):Boolean = { l match { case Nil => true; case (x::xs) => x && and(xs) }}
> def replicate(n:Int, m:Any):List[Any] = { n match { case 0 => Nil; case _ => m :: replicate(n - 1, m)}}
> def elem(x:Any, l:List[Any]):Boolean = { l match { case Nil => false; case (y::ys) => (x == y) || elem(x,ys) }}

concatを再帰で作れなかった。ListのListが上手くマッチしない。

scala> def concat(ll:List[List[Any]]):List[Any] = { ll match { case List(List()) => Nil; case (x::xs) => x ::: concat(xs) }}
concat: (List[List[Any]])List[Any]

scala> concat(List(1,2)::List(3,4)::Nil)
scala.MatchError: List()
        at .concat(<console>:67)
        at .concat(<console>:67)
        at .concat(<console>:67)
        at .<init>(<console>:68)
        at .<clinit>(<console>)
        at RequestResult$.<init>(<console>:3)
        at RequestResult$.<clinit>(<console>)
        at RequestResult$result(<console>)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeM...

scala> List(1,2)::List(3,4)::Nil
res47: List[List[Int]] = List(List(1, 2), List(3, 4))

P.71 練習問題6.8.4

リスト2つを引数に取るので、タプルパターンとリストパターンの合わせ技で処理することにした。

def merge(ml:List[Int], nl:List[Int]):List[Int] = {
    (ml, nl) match {
        case (ms, Nil) => ms
        case (Nil, ns) => ns
        case ((m::ms), (n::ns)) => if(m <= n) m::merge(ms, (n::ns)) else n::merge((m::ms), ns)
    }
}

P.72 練習問題6.8.5

halveは空リストを渡しても上手く処理するように改良。

def halve(xs:List[Int]):(List[Int],List[Int]) = { xs match { case Nil => (Nil, Nil); case _ => { val l = xs.length / 2; (xs.take(l),xs.drop(l)) }}}

def msort(xs:List[Int]):List[Int] = {
    xs match {
        case Nil => Nil
        case (x::Nil) => List(x)
        case _ => { var (l,r) = halve(xs); merge(msort(l), msort(r)) }
    }
}

P.73 高階関数

基数変換、通信については省略。

無限リストはStreamクラスを用いることで、生成できる。

P.87 練習問題7.8.1

> List(1, 2, 3, 4, 5, 6, 7).filter(_ < 4).map(_ + 1)

P.87 練習問題7.8.2

List[Int]限定にして横着。

> def all(f: Int => Boolean, xs:List[Int]):Boolean = xs.map(f(_)).reduceLeft(_ && _)
> def any(f: Int => Boolean, xs:List[Int]):Boolean = xs.map(f(_)).reduceLeft(_ || _)

def takeWhile(f:Int => Boolean, l:List[Int]):List[Int] = {
    l match {
        case Nil => Nil
        case (x::xs) => if(f(x)) x :: takeWhile(f, xs) else Nil
    }
}

def dropWhile(f:Int => Boolean, l:List[Int]):List[Int] = {
    l match {
        case Nil => Nil
        case (x::xs) => if(f(x)) dropWhile(f, xs) else x::xs
    }
}

P.87 練習問題7.8.4

> def dec2int(l:List[Int]):Int = l.foldLeft(0)((sum, x) => sum * 10 + x)
> def dec2int(l:List[Int]):Int = l.foldLeft(0)(_ * 10 + _)  // 見難いけど便利

P.88 練習問題7.8.7

関数の特徴からしてわざわざIntに限定する理由は特に無いが、int2binやchop8を実装するためにIntに限定した。

def unfold(p:Int => Boolean, h:Int => Int, t:Int => Int, x:Int):List[Int] = {
    if(p(x)) Nil else h(x)::unfold(p, h, t, t(x))
}

今日はここまで。

近いうちに、(長いというのが理由で)飛ばした例題をまとめてやりたい。

      • -

追記: プログラミングHaskellをScalaで解く(その1.892857) - DiaryExceptionを書きました。