Adler-32: 関数scanlを使ってみる

はじめに

Haskellにはfoldrという関数がある。この関数は、たたみこみ関数と呼ばれるものだ。これに類する関数は、たくさんある。たとえば関数foldlあたりが有名だ。そのようなバリエーションのひとつとして、関数scanrやscanlというものがある。scan*系の関数の使い道として、いい例があったので、紹介する。

対象読者

Haskellの基本的な文法はわかる。関数foldrやfoldlについては理解している。型ByteStringは使ったことがある。

関数scanlとは

関数foldlはつぎのような計算をする。

foldl (+) 1 [2, 3, 4] == ((1 + 2) + 3) + 4

左結合でリストの要素を、つぎつぎに演算子でつないでいく。ここで、計算途中の値がほしいとする。そんなときに関数scanlを使う。

scanl (+) 1 [2, 3, 4] == [1, 1 + 2, (1 + 2) + 3, ((1 + 2) + 3) + 4

このように関数foldlにおける、「途中の値」をすべて集めたリストをかえすのが、関数scanlだ。

関数scanl'とは

ここではくわしくは説明しないが、関数foldlを使うと空間効率が悪くなる。途中の計算が遅延されるためだ。関数foldl'はその問題を解決したバージョンだ。おなじように関数scanl'も、関数scanlの空間効率を改善したものだ。

Adler-32とは

Adler-32は、zlib形式で圧縮されたファイルに負荷されるチェックサムをもとめるアルゴリズムだ。zlib形式での圧縮はPNG形式の画像ファイルに使われている。計算自体は簡単で、A, Bふたつの値を計算し、それを結合する。値Aはデータの全バイトの総和に1たしたものの、65521を法とした剰余である。値Bは値Aの計算途中の値の総和となっている。

くわしくはWikipedia: Adler-32を参照のこと。

コードの全体

adler32.hs

{-# OPTIONS_GHC -fno-warn-tabs #-}

import Control.Arrow
import Data.List
import Data.Bits
import Data.Word

import qualified Data.ByteString as BS

add :: Integral a => Word32 -> a -> Word32
add w1 w2 = (w1 + fromIntegral w2) `mod` 65521

adler32 :: BS.ByteString -> BS.ByteString
adler32 bs = BS.pack $ map fromIntegral [
        b `shiftR` 8, b .&. 0xff, a `shiftR` 8, a .&. 0xff ]
        where
        (b, a) = foldl' (flip $ \k -> (`add` k) *** const k) (0, 0)
                . tail $ scanl' add 1 $ BS.unpack bs

コードの説明

関数add

関数addは、65521を法とする剰余の世界における足し算だ。

関数adler32

関数adler32の本体を、もういちど示す。

adler32.hs

adler32 :: BS.ByteString -> BS.ByteString
adler32 bs = BS.pack $ map fromIntegral [
        b `shiftR` 8, b .&. 0xff, a `shiftR` 8, a .&. 0xff ]

この部分では求めた値Aと値Bとを結合したバイト列をつくっている。関数shiftRで上位8ビットを取り出し、演算子(.&.)で下位8ビットを取り出している。つまり、つぎのようになる。

[Bの上位8ビット, Bの下位8ビット, Aの上位8ビット, Aの下位8ビット]

関数adler32のwhere節を、もういちど示す。

adler32.hs

(b, a) = foldl' (flip $ \k -> (`add` k) *** const k) (0, 0)
        . tail $ scanl' add 1 $ BS.unpack bs

これは、よりわかりやすく書くと、つぎのようになる。

ns = tail $ scanl' add 1 $ BS.unpack bs
a = last ns
b = foldl' add 0 ns

したのような形だと、リストnsの全体を2回、走査しているので、効率が悪くなる。なので、実際のコードでは、タプルにまとめて、1回の走査で評価している。

したのほうの形で説明する。まずリストnsは初期値1から、データのバイトをつぎつぎに加算していった計算の、途中結果を集めたリストである。初期値は使わないので、関数tailではじめの値を落としている。値aは、リストnの最後の要素であり、これがデータのバイトの総和を加算したものに、1加えたものだ。bは途中結果をすべて加算したものである。

効率の改善 - 剰余の計算の回数を減らす

(あとで書く)