iterateeとは何か、何が良いのか

haskell

iterateeって良く聞くけど何が良いの、と思ってるHaskellユーザのためのメモ。iterateeについては既に日本語の紹介が複数あるが、この記事では実装の詳細に立ち入らず、何が嬉しくてあんな奇妙なインタフェースになっているかについてだけ説明する。具体的なライブラリは使わず、出てくるHaskell風のコードは全て疑似コード。

データ源と処理の分離

iterateeは何をするものかを一言で言うと、データを取得しながら回すループを簡単に書くためのものだ。典型的には、ファイルやソケットからデータを受け取り、それを加工して、画面に出力したり統計を取ったりする。これを素朴に書くと、readやrecvをして、EOFを判定し、加工し、最終的な処理をするまでを一つのループ内で行うことになる。ループが大きくなってくるとこれは嫌なので、ループを分解して、データの取得、加工、最終処理をそれぞれ別々に書いて後で組み合わせる、というのが、iterateeの基本的な考え方だ。各過程を分離することでモジュール性を高めれば、コードが読みやすくなり、変更しやすくなり、単体テストが簡単になり、あわよくば再利用を狙える、という期待である。

データ源と処理を分離するという考えは別に新しくない。最近の言語の多くがイテレータと呼ばれるものを持っている。イテレータはデータ源の抽象化で、リクエストを受けて一個づつ要素を返すもの(pull方式/外部イテレータ)であったり、データを次々読んで指定されたコールバックに渡すもの(push方式/内部イテレータ)だったりする。Google検索によればC++、Java、Pythonなどが外部イテレータを持ち、Rubyなどが内部イテレータを持つらしい。

Haskellでのiterateeプログラミングは、基本的には内部イテレータ方式と同じものである(ここのトレードオフには後で触れる)。より詳細には、例えばRubyのものと比べて以下のような特徴がある。

  • データ源(iterator)だけでなく処理(iteratee)も明示的に扱う。むしろこちらが主。
  • データ源と処理を分離するのに加えて、これらを加工したり複数合成するといった、コンビネータ的な操作を重視する。これにより、場合によっては既存の部品の組み合せだけでループが完結する。

インタフェースの導出

最も素朴には、処理/iterateeはデータを受け取って何かするもの(e -> IO ())でモデル化できる。

-- | e型の要素を扱う処理
type Iteratee e = e -> IO ()

このインタフェースに合わせてデータ源を定義し、使ってみる。なおHaskellではデータ源をイテレータと呼ばずにenumeratorと呼ぶ習慣なので、以降そのようにする。

-- | e型の要素を生産するデータ源
type Enumerator e = Iteratee e -> IO () -- 処理を受けとり、データを与えつつ繰り返し実行する

-- | Enumeratorの例。ファイルからバイト列を読む
enumBinaryFile :: FilePath -> Enumerator Word8
enumBinaryFile = ...

-- test.pngの各バイトを標準出力に表示する
main = enumBinaryFile "test.png" print -- Prelude.printはそのままIteratee Word8として使える

これで一応、データ源と処理の分離は達成できた。しかしこのままでは不便な点が多すぎる。ループからの途中脱出に対応すべきだし、iterateeはローカルな状態を持てるべきだし、EOFに達したことがiteratee側から分かる仕組みも欲しい。これらは全て、Iteratee型を複雑化させることで対応できる。例えば、途中脱出のためには、Iterateeが継続の意思をBoolで返すようにする、など。

-- | e型の要素を扱う処理
data Iteratee e = ... -- 複雑なデータ構造

これに伴ってprintをそのままIterateeとして扱うことができなくなったので、変換関数を用意する。

-- | 入力の全ての要素についてfを実行するようなiteratee
foreach :: (e -> IO ()) -> Iteratee e
foreach = ...

main = enumBinaryFile "test.png" (foreach print) -- foreachを使ってiterateeを作る

内部状態を持つiterateeも作れる。

-- | 内部状態bを更新しつつ処理するiteratee
foldI :: (b -> e -> IO b) -> b -> Iteratee e
foldI updater initialState = ...

ここまでの拡張で、普通のアプリケーションで必要になるループはほとんど全て、データ源と処理を分離した形で書けるようになった。

Iterateeの逐次合成

いよいよ合成に入る。「xというiterateeを実行してからyというiterateeを実行する」という処理はやはりiterateeになるべきである。

-- | 二つのiterateeの逐次合成。まず左辺を実行し、左辺が終了(つまり途中脱出)したら続けて右辺を実行する
(>>) :: Iteratee e -> Iteratee e -> Iteratee e

これは次のように使う。

-- | n個の要素を読み捨て、その後終了するiteratee
dropI :: Int -> Iteratee e

-- PNGのファイルヘッダ(先頭8バイト)を無視し、それ以降を表示する。
main = enumBinaryFile "test.png" (dropI 8 >> foreach print)

iterateeが終了に際して値を返せるようになれば、逐次合成はずっと柔軟になる。前のiterateeの結果に応じて次のiterateeを決めることができ、これは要するにモナドである。

-- | e型の要素を扱い、最終的にaを生成する処理
data Iteratee e a = ...

-- iterateeは逐次合成に関してモナドをなす
instance Monad (Iteratee e) where
  -- 入力を消費せず、xを最終結果として即座に終了するiteratee
  return x = ...
  -- xを実行し、それが結果vで終了したなら続けてf vを実行するiteratee
  x >>= f = ...

instance MonadIO (Iteratee e) where
  -- 入力を消費せず、アクションaを実行し、
  -- その返り値を最終結果として即座に終了するiteratee
  liftIO a = ...

iterateeが値を返せるようになったので、これを活かすために次のような小さなiteratee群を用意しておく。

-- | 先頭要素を読み、それを返すiteratee。EOFが来たら例外でも投げておく
haedI :: Iteratee e e
headI = ...

-- | 先頭n要素を読む
takeI :: Int -> Iteratee e [e]
takeI n = replicateM n headI

-- | 内部状態bを更新しつつ処理するiteratee。最終状態を返す
foldI :: (b -> e -> IO b) -> b -> Iteratee e b
foldI updater initialState = ...

これを使うと、たとえば次のようなことができる。

-- | PNGの画像サイズを取得するiteratee
pngSizeI :: Iteratee Word8 (Int, Int)
pngSizeI = do
  dropI 8 -- ファイルヘッダを読み飛ばす
  dropI 8 -- IHDRチャンクヘッダを読み飛ばす
  !width <- int32beI
  !height <- int32beI
  return (width, height)

-- | 32bit, big-endian整数を読むiteratee
int32beI :: Iteratee Word8 Int
int32beI = foldl' make 0 <$> takeI 4
  where
    make acc byte = acc * 256 + fromIntegral byte

-- test.pngのサイズを表示する
main = enumBinaryFile "test.png" (pngSizeI >>= liftIO . print)

つまり、headIやtakeIなどの小さなiterateeをモナディックに連結することで、逐次的・手続き的スタイルでiterateeを記述できる。これはforeachやfoldIを使った一括処理スタイルと自由に混合できる。

Enumeratorの逐次合成

iterateeが値を返すことを考慮すると、Enumeratorは次のような定義になる。

-- | e型の要素を生産し、aを最終結果とするiterateeに食わせるデータ源
type Enumerator e a = Iteratee e a -> IO a

次にEnumerator同士の合成を考える。このEnumeratorの定義のままだとちょっとやりにくい(できないことはないが)ので、Enumerator自体がEOFを生成しないように変更する。Enumeratorがデータを生成し終わったら、iterateeにEOFを与えてループを完結させることをせず、その時点のiterateeを返す。

-- | e型の要素を生産し、aを最終結果とするiterateeに食わせるデータ源
type Enumerator e a = Iteratee e a -> IO (Iteratee e a)

実際にループを完結させて最終結果を取りだす関数が必要になる。

-- | iにEOFを送り、結果を取得する
run :: Iteratee e a -> IO a
run i = ...

これは次のように使う。

-- 最終的な実行にはrunが必要
main = enumBinaryFile "test.png" (foreach print) >>= run

Enumeratorの定義を変更したことで、Enumeratorの逐次合成が可能になる。

-- | aからデータを取り出し、それが終わったらbからデータを取り出すEnumerator
cat :: Enumerator e a -> Enumerator e a -> Enumerator e a
cat a b = \iter -> a iter >>= b

これで、小さいEnumeratorを定義し、それを結合するスタイルが可能になる。

-- | 0個の要素を生成する
enumZero :: Enumerator e a
enumZero = return

-- | 一個の要素を生成する
enumOne :: e -> Enumerator e a
enumOne = ...

-- | 指定されたリストを生成する
enumList :: [e] -> Enumerator e a
enumList xs = foldr cat enumZero $ map enumOne xs

ストリームの変換

データ源と処理の二層に分割するだけでなく、データを加工する中間層を持ちたいこともある。これは上の枠組の範囲内で導入できる。データの加工なので直感的にはEnumerator -> Enumeratorの関数にしたくなるが、Iteratee -> Iterateeにした方が単純になる。アイディアは、「加工済みのデータを要求するiteratee、A」を「未加工のデータを要求してAと同じことをするiteratee」に変換できれば、実質的にデータを加工しているのと同じ、というものだ。

-- | output型の入力を要求するiterateeをinput型の入力で駆動できるようにする変換
-- 気分としては、input型のストリームをoutput型のストリームに変換している
type Enumeratee input output a = Iteratee output a -> Iteratee input a
  -- Enumerateeという名称は謎だが、これが慣習

代表的なEnumerateeとしてmapやfilterが書ける。

mapE :: (a -> b) -> Enumeratee a b z
mapE = ...

filterE :: (a -> Bool) -> Enumeratee a a z
filterE = ..

他にも、バイト列を行の列に変換したり、zlib圧縮されたデータを伸長したりといった、ありとあらゆるストリーム変換がEnumerateeの形で書ける。

Enumerateeは変換を表すデータなので、関数的合成が定義できる。

-- | gで変換したストリームをさらにfで変換するような変換
(<><) :: Enumeratee b c z -> Enumeratee a b z -> Enumeratee a c z
f <>< g = g . f

これで、任意の数のデータ加工レイヤを使うことができる。

さらにEnumerateeの逐次合成も考えられる。これはEnumeratorの逐次合成と同じアイディアで、内側の(加工済みデータを要求する)iterateeにEOFを与えず、それを返すようにすることで実現される。

-- | output型の入力を要求するiterateeをinput型の入力で駆動し、EOFを送らずに返す
type Enumeratee input output a = Iteratee output a -> Iteratee input (Iteratee output a)

-- | Enumerateeを使って単純にiterateeを変換する
(=$) :: Enumeratee input output a -> Iteratee output a -> Iteratee input a
enee =$ iter = enee iter >>= liftIO . run

iterateeの並置合成

iterateeの合成にはもう一つある。複数の独立なiterateeを、同一の入力に対して並行して実行する。

-- | 入力をxでもyでも処理するような処理。xとyの両方が終了した時点で終了する。
pairI :: Iteratee e a -> Iteratee e b -> Iteratee e (a, b)
pairI x y = ...

これを使うと、たとえばDouble列の平均を計算するiterateeは次のように書ける。

meanI :: Iteratee Double Double
meanI = make <$> pairI sumI lengthI -- 和と長さを別々に計算し、最後にまとめる
  where
    make (total, size) = total / fromIntegral size

sumI :: (Num a) => Iteratee a a
sumI = foldI (+) 0

lengthI :: Iteratee a Int
lengthI = foldI (\c _ -> c + 1) 0

もっと沢山のiterateeを並置合成することもできる。

-- | 入力をxsのすべてで処理するような処理。xsがすべて終了した時点で終了する。
listI :: [Iteratee e a] -> Iteratee e [a]
listI xs = ...

個人的には、この並置合成を簡単に書ける点こそがHaskell式のiterateeの最大の旨味だと思う。

実際のライブラリインタフェース

http://hackage.haskell.org/package/iteratee、http://hackage.haskell.org/package/enumerator、http://hackage.haskell.org/package/iterIOのインタフェースについて簡単に述べる。

これらのライブラリでは、iterateeはIOに限らず任意のモナド上で動作するようになっている。このため、Iterateeがもう一つの型引数mをとる。

-- | モナドm上でe型の要素を扱い、最終的にaを生成する処理
data Iteratee e m a = ...

instance MonadTrans (Iteratee e) where ...

iterateeとiterIOでは、効率のためにiterateeはチャンク単位でデータを受け取る。チャンクは要素のコレクションで、ListLikeクラスのインスタンスであることが要求される。[a]やByteStringがチャンクの型としてよく使われる。

-- | sは要素がelである列を表現するデータである
class ListLike s el | s -> el where ...

-- | モナドm上でs型のチャンクを扱い、最終的にaを生成する処理
data Iteratee s m a = ...

-- | 先頭要素を読み、それを返すiteratee
headI :: (ListLike s el) => Iteratee s m el
headI = ...

ライブラリによってはさらに機能がある。たとえばiterateeが例外を投げられたり、iterateeからenumeratorへ制御メッセージ(たとえばseek request)を送ることが可能だったり、iterateeを別スレッドで並行に実行することが可能だったりする。しかしこれはインタフェースに大して影響しない。

設計のトレードオフ

ここからは個人的な考察。

他の言語のイテレータ機構と比べてHaskellのものはかなり複雑。これはたぶん、コンテナ走査の手段としてよりもIOの手段として考えられていて、アプリケーションのかなり大きな部分を一つのiteratee-enumeratorの枠組で書くことが想定されているので、そのぶん柔軟性が求められているからだろう。コンテナ走査については、Haskellには既にfold(内部イテレータ相当)とtoList(外部イテレータ相当)がある。

内部イテレータ形式、つまりループがiteratee側でなくenumerator側にあるので、enumeratorに結び付いたリソース(ファイルハンドルとか)の管理が簡単。逆にiterateeに結び付いたリソースがあるならちょっと面倒。

iterateeの並置合成が可能な反面、enumerateeの並置合成、つまり複数の独立なデータ源から一度に一個ずつ要素を取って来るようなenumerateeが書けない。外部イテレータ形式だとこれは逆になる。

結局どうなのか

Hackageだとiterateeスタイルのプログラミングはほぼ事実標準と言ってよいと思う。少なくともenumeratorとiterateeの両パッケージが既に実用レベルに達していることは間違いない。しかし改善の余地はまだあると思っている。

一つのデータ源を独立に二通りの方法で加工し、その両方を一つの処理に渡すような形は実現できない。これについては外部イテレータ形式でもできない。実際にこれができなくて困ることが結構あるので、なんとかするべき。

インタフェースが非常に複雑で嫌になる。仕方ない部分もあるが、Enumerator a m bのbパラメタとか要らないような気がする。