プログラミングHaskellをScalaで解く(その2.9431818)
引き続き、『プログラミングHaskell』の例題と練習問題をScalaで書いてみる。
プログラミングHaskell |
P.83 文字列の変換器
文字列を0/1のビット列に変換して送信、受信側でビット列を文字列に復号化することを考える。
type Bit = Int
分かり易くするために、Intに別名を与える。Haskellと同じ書き方だから問題無い。
def bin2int(bits:List[Bit]):Int = bits.foldRight(0){(x,y) => x + 2 * y} def int2bin(n:Int):List[Bit] = { n match { case 0 => Nil; case _ => n % 2 :: int2bin(n / 2) }}
P.83の通り、2進表記は逆順に書くこととする。
それぞれ、ビット列と整数を相互変換するための関数になる。bin2intはビット列を逆順にしたお陰で、右畳み込みで簡単に書けていることが分かる。
def repeat[A](a:A) = Stream.const(a) def make8(bits:List[Bit]):List[Bit] = (bits ::: repeat(0).take(8).toList).take(8)
ここで、Haskellでいう無限リストを生成するために、Streamクラスを用いる。
repeatはA型(実行時に型推論される)のaという値を無限に連ねるリストのようなものを生成する。Haskellの様に、lazyなリストではないので、用いる範囲が決定してから(make8内の.take(8)で8個まで使うことを指定している)、toListでリストに変換している。
前の、bin2intも、無限リストStreamを用いれば以下のように書ける。
def iterate[A](f:A => A, x:A):Stream[A] = Stream.cons(x, iterate(f, f(x))) def bin2int(bits:List[Bit]):Int = { val weights = iterate((x:Int) => (x * 2), 1) (for((w,b) <- weights.take(bits.length).toList.zip(bits)) yield w * b).reduceLeft(_ + _) }
iterateもHaskellの実装のほぼそのまま。
def concat[A](xss:List[List[A]]):List[A] = xss.reduceLeft((xs, x) => xs ::: x) def encode(xs:String):List[Bit] = { concat(xs.toList.map((x:Char) => make8(int2bin(x)))) }
文字列をencode関数に与え、Charのリストに分解してからそれぞれをビット列に変換する。通信を想定しているのだから、List[List[Bit]]ではおかしいので、List[Bit]にするための(最早説明不要な)concat関数を定義している。
def chop8(bits:List[Bit]):List[List[Bit]] = { bits match { case Nil => Nil; case _ => bits.take(8) :: chop8(bits.drop(8)) }} def decode(bits:List[Bit]):String = chop8(bits).map((xs:List[Bit]) => bin2int(xs).toChar).mkString
decode側はencode側のほぼ逆のことをしているだけ。List[Char]はmkStringで文字列に変換出来る。この辺はHaskellより融通が利かない。
def channel(bits:List[Bit]):List[Bit] = bits def transmit(xs:String):String = decode(channel(encode(xs)))
あまり面白くはないが、通信のシミュレーションはこう書ける。P.88の練習問題7.8.9はchannelの中身を bits.tail にするだけで良い。
P.88 練習問題7.8.8
チェックビットを付与するためには、ビット列要素が8個から9個になることだけを意識して改良すれば、以下のように書ける。
def make9(bits:List[Bit]):List[Bit] = { (bits.count(_ == 1) % 2) :: (bits ::: repeat(0).take(8).toList).take(8) } def encode2(xs:String):List[Bit] = { concat( xs.toList.map( (x:Char) => make9(int2bin(x)) ) ) } def chop9(bits:List[Bit]):List[List[Bit]] = { bits match { case Nil => Nil case _ => { val bits9 = bits.take(9) if(bits9.tail.count(_ == 1) % 2 == bits9.head) bits9.tail :: chop9(bits.drop(9)) else throw new Exception("check error") } } } def decode2(bits:List[Bit]):String = chop9(bits).map((xs:List[Bit]) => bin2int(xs).toChar).mkString
bits9.tail.count(_ == 1) % 2 が重複しているので、関数1つに纏めるのも手だろう。
errorの投げ方は、Javaを意識してか、throw new 何々Exceptionとなる。このプログラムの場合でエラーが投げられると、以下のようにメッセージを出してプログラムが停止する。
java.lang.Exception: check error at .chop9(<console>:15) at .<init>(<console>:7) 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(NativeMethodAccessorImpl.java:39) at sun.reflect.Del...
今回はここまで。
これで、関数型言語の基本である再帰や高階関数については、十分に練習出来た。次回から、これまた関数型言語から切り離せない、型を活用する話になる。
- -