LoginSignup
2
1

More than 5 years have passed since last update.

enumerator パッケージの Iteratee (>>=) の実装

Last updated at Posted at 2012-03-16

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

では起こらない理由と同じなのかなと思っていますが……

2
1
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
1