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

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

プログラミングHaskell
Graham Hutton

前回の改良

concat

プログラミングHaskellをScalaで解く(その2) - DiaryExceptionの「P.71 練習問題6.8.3」で「concatを再帰で作れなかった。ListのListが上手くマッチしない。」と書いたが、これは単なる僕のミスだった。

scala - Why doesn't this match? - Stack Overflowですぐに間違いを指摘されて、恥ずかしかったが、勉強になった。

答えはこう。

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

そもそも、リストのリストを作るなら

List(1,2)::List(3,4)::List(Nil)

とした方が正確だった。NilはList()、あるいはList(Nothing)を指す。従って、case List(Nil)を追加しなければ、MatchErrorを起こすことが分かる。

サブタイプ指定

プログラミングHaskellをScalaで解く(その2) - DiaryExceptionの「前回の改良」で型推論をするための指定Tを利用したが、これではどの型でも当てはまることになり、都合が悪い場合がある。

例えば、関数を比較演算子を持つ型に限定したいといった場合である。プログラミングHaskellをScalaで解く(その2) - DiaryExceptionの「P.61 リストに要素を挿入と Insertion Sort」や「P.87 練習問題7.8.2」以降で、比較演算子を関数の実装の中で用いているために、Any型を使えずIntに限定していたが、もし型を限定できるなら、より正確に関数を実装できる。

Haskellで書くと、こう。

insert :: Ord a => a -> [a] -> [a]
insert n xs = ...

こういう型の指定をScalaでも書ける。

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

<% は「Aという型が、Orderedクラスを継承しているか、暗黙的型変換でOrderedクラスを継承した型になれる」ということを表現している。

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

と <: を使って書くと「Aが、暗黙的型変換を許さず、Orderedクラスを継承した型である」ということを表現する。

Haskellに比べ、見難さが露呈してきた感じがあるが、正確に実装を書ける手段が提供されていることは嬉しい。

P.50 シーザー暗号

プログラミングHaskellをScalaで解く - DiaryExceptionの中の「P.49 文字列」で飛ばした、シーザー暗号の例題を取り上げる。

簡単に言えば、"haskell is fun"の各アルファベットを3ずつずらし、"kdvnhoo lv ixq"としたい。そのために必要な関数を定義していく。

def let2int(c:Char):Int = c.toInt - 'a'.toInt    // アルファベットを整数(0~25)に
def int2let(n:Int):Char = ('a'.toInt + n).toChar // 整数(0~25)をアルファベットに

def shift(n:Int, c:Char):Char = {   // cというアルファベットをnだけずらす
    if(c.isLowerCase) { val nc = (let2int(c) + n) % 26; int2let(if(nc < 0) nc + 26 else nc) }
    else c
}

def encode(n:Int, xs:String):String = {  // 文字列の各アルファベットをnだけずらす
    (for(x <- xs.toList) yield shift(n, x)).mkString
}

shiftがHaskell版に比べ複雑になっているのは、Scalaの剰余演算子の仕様によるもの。

>>> (-1) % 3  # Python
2

Prelude> (-1) `mod` 3  -- Haskell
2

scala> (-1) % 3  // Scala
res53: Int = -1

となり、負数が来ると他の言語と結果が異なるため、if-elseによる場合分けが必要だった。

scala> encode(3, "haskell is fun")
res52: String = kdvnhoo lv ixq

P.52で文字の出現頻度表 table が与えられる。これを用いて、シーザー暗号によって暗号化された文字列の解読を試みる。

def percent(n:Int, m:Int):Double = (n.toDouble / m.toDouble) * 100 // 百分率

def lowers(xs:String):Int = (for(x <- xs; if x.isLowerCase) yield x).length  // P.50
def count(x:Char, xs:String):Int = (for(x1 <- xs; if x == x1) yield x1).length  // P.50

def freqs(xs:String):List[Double] = for(x <- ('a' to 'z').toList) yield percent((count(x, xs)), lowers(xs))
  // 文字列内の任意の文字の出現頻度リスト

def chisqr(os:List[Double], es:List[Double]):Double = (for((o,e) <- os.zip(es)) yield Math.pow(o - e, 2) / e).reduceLeft(_ + _)
  // カイ二乗検定

def rotate[T](n:Int, xs:List[T]):List[T] = xs.drop(n) ::: xs.take(n)  // リストを回転

これで解読に必要な関数の定義が完了する。

def crack(xs:String):String = {
    def table1:List[Double] = freqs(xs)
    def chitab:List[Double] = for(n <- (0 to 25).toList) yield chisqr(rotate(n, table1), table)  // 文字列を回転させて出現頻度表を生成する
    def minimum[A <% Ordered[A]](ns:List[A]):A = ns.sort(_ < _).head  // リストの最小値 小さい順に並べ先頭を取り出す
    def positions[A](x:A, xs:List[A]):List[Int] = { for((x1, i) <- xs.zip((0 to xs.length - 1).toList); if x == x1) yield i }  // P.49
    def factor:Int = positions(minimum(chitab), chitab).head  // 最も適した文字ずらし数
    encode(-factor, xs)  // 最も適した文字ずらし数の符号を反転させてencodeすることで元の文字列を得る
}

このcrack関数の中で、幾つかローカル関数を定義したが、minimumとpositionsに型推論指定Aを用いている。

つまり、tableという一般的な文字の出現頻度表が与えられているので、カイ二乗検定によって最も一般的な分布に近くなる文字ずらし数を総当たりのような手段で求める。

scala> encode(10, "list comprehensions are useful")
res56: String = vscd mywzboroxcsyxc kbo ecopev

scala> crack("vscd mywzboroxcsyxc kbo ecopev")
res57: String = list comprehensions are useful

今回はここまで。

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