Haskell の Iteratee

Question

Iteratee のデータ構造は簡単にすれば次のような感じになっています。

data Iteratee i o = Done o | Next (i -> Iteratee i o)

getOne :: Iteratee a a
getOne = Next Done

c = Char の時を考えると、getOne は入力から1文字だけ取ってくることを表してるわけですが、当然入力から1文字消費されます。
入力を消費せずに先頭の文字を取ってくるようなものって書けないですかね？ 言い換えれば取ってきた文字をそのまま押し戻すみたいな。正規表現で言う先読みみたいなもんです。型は getOne と同じ Iteratee a aになってほしいです。

絶対できないのか、やろうと思えばできるのかが知りたいです。

Answer 1

conduitなどで使われているポピュラーな方法は、以下のようにIterateeのコンストラクタを追加し、値を戻す挙動を表現するものです。

data Iteratee i o = Done o | Next (i -> Iteratee i o) | Leftover i (Iteratee i o)

peek :: Iteratee i i
peek = Next $ \i -> Leftover i (Done i)

しかし、継続モナドを使えば、Iterateeの定義を変更せずに値を戻すこともできます。ContTでもいいですがここではkan-extensionsのCodensityを使います。

newtype Codensity m a = Codensity
  { runCodensity :: forall b. (a -> m b) -> m b
  }

peek :: Codensity (Iteratee i) i
peek = Codensity $ \cont -> Next $ \i -> case cont i of
    Next k -> k i
    Done o -> Done o

contにiを渡すと、peekの次に実行されるIterateeが返ってきます。それにiを再び押し込めばよいというわけです。しかし、次がDoneの場合は値が捨てられてしまうので、そこを気にする場合はDoneにフィールドを追加して余った値を残せるようにするとよいでしょう。

Iterateeのような構造をモナドにする際、>>=の計算量が深さに比例するという難点がありますが、Codensityモナドならばデータ構造を走査する必要がないため、パフォーマンスの面でも有利です。この技法はConduitTの定義でも利用されています。