title: Why the Haskell sequence function can't be lazy or why recursive monadic functions can't be lazy
body: <p>With the question <a href="https://stackoverflow.com/questions/14474545/">Listing all the contents of a directory by breadth-first order results in low efficiency</a>I learned that the low efficiency is due to a strange behavior of the recursive monad functions.</p>
  <p>Try</p>
  <pre><code>sequence $ map return [1..]::[[Int]]
  sequence $ map return [1..]::Maybe [Int]
  </code></pre>
  <p>and ghci will fall into an endless calculation.</p>
  <p>If we rewrite the sequence function in a more readable form like follows:</p>
  <pre><code>sequence' []     = return []
  sequence' (m:ms) = do {x&lt;-m; xs&lt;-sequence' ms; return (x:xs)}
  </code></pre>
  <p>and try:</p>
  <pre><code>sequence' $ map return [1..]::[[Int]]
  sequence' $ map return [1..]::Maybe [Int]
  </code></pre>
  <p>we get the same situation, an endless loop.</p>
  <p>Try a finite list</p>
  <pre><code>sequence' $ map return [1..]::Maybe [Int]
  </code></pre>
  <p>it will spring out the expected result <code>Just [1,2,3,4..]</code> after a long time waiting.</p>
  <p>From what we tried,we can come to the conclusion that although the definition of sequence' seems to be lazy, it is strict and has to make out all the numbers before the result of sequence' can be printed.</p>
  <p>Not only just sequence', if we define a function</p>
  <pre><code>iterateM:: Monad m =&gt; (a -&gt; m a) -&gt; a -&gt; m [a]
  iterateM f x = (f x) &gt;&gt;= iterateM0 f &gt;&gt;= return.(x:)
  </code></pre>
  <p>and try</p>
  <pre><code>iterateM (&gt;&gt;=(+1)) 0
  </code></pre>
  <p>then endless calculation occurs.</p>
  <p>As we all know,the non-monadic iterate is defined just like the above iterateM, but why the iterate is lazy and iterateM is strict.
  As we can see from above, both iterateM and sequence' are recursive monadic functions.Is there some thing strange with recursive monadic functions</p>