人気ブログランキング | 話題のタグを見る

RWH の読み方(36) 第4章

Real World Haskell 第4章 Functional Programming

The Left Fold その3

Adler-32 チェックサム

まず、チェックサムとは何かということを、
IT用語辞典から引用してみた。 

データを送受信する際の誤り検出方法の一つ。送信前にデータを分割し、それぞれのブロック内のデータを数値とみなして合計を取ったもの。求めたチェックサムはデータと一緒に送信する。受信側では送られてきたデータ列から同様にチェックサムを計算し、送信側から送られてきたチェックサムと一致するかどうかを検査する。両者が異なれば、通信系路上でデータに誤りが生じていることになるので、再送などの誤り訂正手続きをとる。

Adler-32 チェックサムは上の原始的なチェックサムを改良したもので、Wikipedia に記述してあるアルゴリズムは次のようになる。

Adler-32 チェックサムは、まず2つの16ビットのチェックサム A と B を計算し、それらを連結して32ビットの整数にする。Aは全てのバイトの総和に1を加えた値、B は A を計算している各ステップの値を累積した総和である。

初期状態では、A は 1 に初期化され、B は 0 に初期化される。これらの総和は modulo 65521 で保持される(65521 は 216 未満の最大の素数)。これらのバイトはネットワークオーダー(ビッグエンディアン)で格納され、B が最上位バイト側に位置する。

式で表すと、以下のようになる。

A = 1 + D1 + D2 + ... + Dn (mod 65521)
B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
   = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)

Adler-32(D) = B × 65536 + A

ここで D はチェックサム計算対象のバイト列の各バイトを意味し、n はバイト数を意味する。

Java のプログラム

RWH に紹介してある Adler-32 チェックサムの java プログラムは次のようになる。

public class Adler32
{
    private static final int base = 65521;

    public static int compute(byte[] data, int offset, int length)
    {
        int a = 1, b = 0;

        for (int i = offset; i < offset + length; i++) {
            a = (a + (data[i] & 0xff)) % base;
            b = (a + b) % base;
    }

    return (b << 16) | a;
    }
}

詳しい説明は RWH の本文にあるので省略するが、このプログラムの for ループの中の変数 a が Wikipedia の A に、b が B に相当する。このプログラムを Haskell の末尾再帰で記述したのが次のプログラムだ。

Haskell の末尾再帰プログラム

-- file: ch04/Adler32.hs
adler32_try2 xs = helper (1,0) xs
    where helper (a,b) (x:xs) =
              let a' = (a + (ord x .&. 0xff)) `mod` base
                  b' = (a' + b) `mod` base
              in helper (a',b') xs
          helper (a,b) _     = (b `shiftL` 16) .|. a

この末尾再帰関数の第1引き数のペアの a と b がそれぞれ Wikipedia の A と B に相当する。

Haskell の foldl のプログラム

ところで、前回の記事で示したように foldl は末尾再帰の一般形になっている。すなわち、

foldl f z (x:xs) = foldl f (f z x) xs

だ。したがって上の末尾再帰関数 helper (a,b) (x:xs) は foldl に書き換えることができるはずだ。実際に、RWH に記述されたプログラムは次のようになっている。

-- file: ch04/Adler32.hs
adler32_foldl xs = let (a, b) = foldl step (1, 0) xs
                   in (b `shiftL` 16) .|. a
    where step (a, b) x = let a' = a + (ord x .&. 0xff)
                          in (a' `mod` base, (a' + b) `mod` base)

上下のコードを比較すると、再帰関数の helper を foldl に変換しているのがわかる。

helper (a, b) [] = (b `shiftL` 16) .|. a
helper (a, b) (x:xs) = helper (a',b') xs

という再帰的定義が、

foldl step (1, 0) xs

に置き換えられている。

(1, 0) はどこから出てきたのかと思うかもしれないが、helper 関数を実際に使うときは

helper (1, 0) [1,2,3,4,5]

のように第1引き数に初期値を指定して利用する。

また foldl のコードに見られる step は foldl step (a, b) (x:xs) = foldl step (a_next, b_next) xs

という還元 (reduction) が起きるときの (a, b) -> (a_next, b_next) を計算するための関数だ。上の定義式の右辺に step 関数を使うと、

foldl step (a, b) (x:xs) = foldl step (step x (a,b)) xs

と書くことができる。これは、末尾再帰関数である helper が foldl という末尾再帰関数に逐語的に置き換えられたことを示している。

パターン (xs:x) で定義されるプログラム

今度は、見方を変えて、上の helper 関数を仮想的なパターン (xs:x) を使った再帰関数で定義してみよう。すると、上の定義と同じ step 関数を使って、

helper [] = (1, 0)
helper (xs:x) = step (helper xs) x

adler-32 xs = checksum $ helper xs
  where
    checksum (a, b) = (b `shiftL` 16) .|. a

と書くことができる。そうすると foldl を使って上の定義は、

foldl step (1,0) xs

で置き換えることができる。

したがって、末尾再帰関数あるいは仮想的な (xs:x) というパタンで記述された再帰関数は、逐語的に foldl に変換できることが分かる。

foldr は右再帰型の汎用の再帰関数で、foldl は左再帰型の汎用の再帰関数ととらえるとよいのではないか。そう考えると、この二つの関数で Haskell のリストを引数とするほとんどのループは記述できる。

addler32 を左再帰でプログラム設計した実際のコードは次のようになる。

import Data.Char (ord)
import Data.Bits (shiftL, (.&.), (.|.))

base = 65521

adler32 xs = shift $ helper xs
  where
    -- helper is right recursive
    -- helper [] = (1, 0)
    -- helper (xs:x) = (helper xs) `step` x
    helper xs = foldl step (1, 0) xs
    
    step (a, b) x = (a', b')
      where
        a' = (a + (ord x .&. 0xff)) `mod` base
        b' = (a' + b) `mod` base
    
    shift (a, b) = b `shiftL` 16 .|. a
by tnomura9 | 2012-04-21 08:14 | Haskell | Comments(0)
<< RWH の読み方(37) 第4章 RWH の読み方(35) 第4章 >>