Building a ListT in a library-agnostic way takes quadratic time

[jberryman]

In playing with the approach described here I found that the resulting stream was quadratic in the number of elements when instantiated as a ListT from pipes.

I was consuming and measuring with:

test l = runEffect (enumerate l >-> drain)

Gabriel reduced it to the following test case:

nats :: MonadPlus m => Int -> m Int
nats 10000 = mzero
nats n     = do
    n' <- return n
    return n' `mplus` (nats $! n + 1)

...and mentioned a couple rewrite rules that could recover linear behavior, and that the work will entail some careful control of the ordering of existing rewrite rules to guarantee it fires. Maybe related to #124 and #111

[agrue]

Was there ever any progress made on this? I'm trying to use the following example to demonstrate streaming lines from a file:

fromHandle' :: Handle -> ListT IO String
fromHandle' h = go
  where
    go = do
      eof <- liftIO (hIsEOF h)
      if eof then empty else liftIO (hGetLine h) <|> go

I wanted to show that this streams in constant space... unfortunately it appears to still leak a little bit (if my approach of looking at GC stats via +RTS -S is reliable). It's also way slower than the very similar Producer-based implementation in Pipes.Prelude. I assume this has something to do with poorly-associated binds in the underlying Proxy, but I don't know enough to pinpoint the exact problem.

The reason I want to use ListT instead of Producer is to introduce my team to simple streaming constructs without exposing them to the full complexity of pipes. Is there anything I can do here to build a more efficient ListT-based version, or am I out of luck?

(Incidentally, I tried the same thing with LogicT instead and it was very fast - I assume this has something to do with the CPS(?)-like encoding? https://hackage.haskell.org/package/logict-0.7.0.2/docs/Control-Monad-Logic.html#g:2)

[Gabriella439]

@agrue: No, I haven't made any progress on this since then