title: Left recursion of >>= in Haskell
body: <p>I've just read this very interesting article about an alternative implementation for the <em>Prompt</em> Monad : <a href="http://joeysmandatory.blogspot.com/2012/06/explaining-prompt-monad-with-simpler.html" rel="noreferrer">http://joeysmandatory.blogspot.com/2012/06/explaining-prompt-monad-with-simpler.html</a></p>
  
  <p>Here is a simplified code that can be run :</p>
  
  <pre><code>data Request a where
      GetLine  :: Request String
      PutStrLn :: String -&gt; Request ()
  
  data Prompt p r
       = forall a. Ask (p a) (a -&gt; Prompt p r)
      | Answer r
  
  instance Monad (Prompt p) where
      return              = Answer
      Ask req cont &gt;&gt;= k  = Ask req (\ans -&gt; cont ans &gt;&gt;= k)
      Answer x &gt;&gt;= k      = k x
  
  prompt :: p a -&gt; Prompt p a
  prompt req = Ask req Answer
  
  runPromptM :: Monad m =&gt; (forall a. p a -&gt; m a) -&gt; Prompt p r -&gt; m r
  runPromptM perform (Ask req cont) = perform req
                              &gt;&gt;= runPromptM perform . cont
  runPromptM _       (Answer r)     = return r
  
  handleIO :: Request a -&gt; IO a
  handleIO GetLine = return ""
  handleIO (PutStrLn s) = putStrLn s
  
  req :: Prompt Request ()
  req = do
    answers &lt;- sequence $ replicate 20000 (prompt GetLine)
    prompt $ PutStrLn (concat answers)
  
  main = runPromptM handleIO req
  </code></pre>
  
  <p>A comment in the article mentions that :</p>
  
  <blockquote>
    <p>it has a problem that left recursion of >>= takes quadratic time to evaluate (it's the same as the left-recursion of ++ problem!)</p>
  </blockquote>
  
  <p>I don't understand where the quadratic time (which I checked experimentally) come from. Is it related to lazy evaluation ?</p>
  
  <p>Can someone explain me <strong>why</strong> ?</p>