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

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

Graham Hutton - プログラミングHaskell

プログラミングHaskell
Graham Hutton



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...

今回はここまで。

これで、関数型言語の基本である再帰高階関数については、十分に練習出来た。次回から、これまた関数型言語から切り離せない、型を活用する話になる。

  • -

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