Iteratee の Monad インスタンス定義の (>>=) のナイーブな実装は以下のようになります。
instance Monad m => Monad (Iteratee a m) where
m >>= f = Iteratee $ runIteratee m >>= \r1 ->
case r1 of
Continue k -> return (Continue ((>>= f) . k))
Error err -> return (Error err)
Yield x (Chunks []) -> runIteratee (f x)
Yield x extra -> runIteratee (f x) >>= \r2 ->
case r2 of
Continue k -> runIteratee (k extra)
Error err -> return (Error err)
Yield x' _ -> return (Yield x' extra)
この実装は比較的理解しやすいので好きなのですが、これには space leak があるそうで、
enumerator 0.4.7 (bzr revno 98) で不動点コンビネータを使った以下のような定義に修正されたそうです。
instance Monad m => Monad (Iteratee a m) where
m0 >>= f = ($ m0) $ fix $
\bind m -> Iteratee $ runIteratee m >>= \r1 ->
case r1 of
Continue k -> return (Continue (bind . k))
Error err -> return (Error err)
Yield x (Chunks []) -> runIteratee (f x)
Yield x extra -> runIteratee (f x) >>= \r2 ->
case r2 of
Continue k -> runIteratee (k extra)
Error err -> return (Error err)
Yield x' _ -> return (Yield x' extra)
前者の実装で space leak が起こり、後者では大丈夫な理由が良くわからないので誰か教えてください。
なんとなく
fix f = f (fix f)
では space leak が起こり
fix f = let x = f x in x
では起こらない理由と同じなのかなと思っていますが……