Merge M constructors when apply fmap/<*>/>>=

[jwiegley]

There's no reason to build up several M constructors when constructing pipelines, so this change merges them at bind time.

[jwiegley]

This may not have the behavior that I wanted, so please hold off on merging this for a bit while I do some more performance analysis.

[jwiegley]

Ok, I've updated it so that it only performs the merging on bind, but now it merges M with the M produced by the function being bound to. In my testing this elides all intervening M constructors.

[michaelt]

Do you have some simple benchmark onlookers could fiddle with?

[jwiegley]

@michaelt I just instrumented toListM and runEffect so that I could see exactly how many times certain constructors are encountered:

foldLog :: Monad m => (x -> a -> x) -> x -> (x -> b) -> P.Producer a m () -> m b
foldLog step begin done p0 = go p0 begin
  where
    go p x = case p of
        P.Request v  _  -> trace "Request" $ P.closed v
        P.Respond a  fu -> trace "Respond" $ go (fu ()) $! step x a
        P.M          m  -> trace "M" $ m >>= \p' -> go p' x
        P.Pure    _     -> trace "Pure" $ return (done x)

toListMLog :: Monad m => P.Producer a m () -> m [a]
toListMLog = foldLog step begin done
  where
    step x a = x . (a:)
    begin = id
    done x = x []

runEffectLog :: Monad m => P.Effect m r -> m r
runEffectLog = go
  where
    go = \case
        P.Request v _ -> trace "Request" $ P.closed v
        P.Respond v _ -> trace "Respond" $ P.closed v
        P.M       m   -> trace "M" $ m >>= go
        P.Pure    r   -> trace "Pure" $ return r

I haven't used criterion yet, but since pipelines may be constructed once, and executed often (such as the function passed to for), my thought was that anything that can tighten up the loops in these functions would be worthwhile, so long as the semantics are unchanged.

[michaelt]

Thanks!

[michaelt]

It never occurred to me that it is a feature of the M constructor approach that monadic layers are not naturally assimilated by things like for and >->, so in e.g.

 main :: IO ()
 main = (print =<<) $ toListMLog pipe where
    pipe = each [1..100::Int] 
          >-> P.mapM newIORef 
          >-> P.chain (flip modifyIORef succ)
          >-> P.mapM readIORef

the producer that results from all the >->s can easily be much more complex than what we would get with the simpler 'correct' encoding with a monadic layer preceding each proxy action. So for the above I see

>>> main
M
M
M
Respond
M
M
M
Respond
...

With the 'correct' implementation I would just have interleaving of Responds each behind a layer of base monad. I'm not sure if that's bad or good.

[Gabriella439]

Yeah, that's right. Every time you use lift you introduce a new M constructor, which would violate the monad morphism laws for lift if you had access to the internal API. The correct-by-construction approach is to use something equivalent to FreeT, but you take a huge hit in performance by doing so