title: What is the correct way to perform constant-space nested loops in Haskell?
body: <p>There are two obvious, "idiomatic" ways to perform nested loops in Haskell: using the list monad or using <code>forM_</code> to replace traditional <code>fors</code>. I've set a benchmark to determine if those are compiled to tight loops:</p>
  
  <pre><code>import Control.Monad.Loop
  import Control.Monad.Primitive
  import Control.Monad
  import Control.Monad.IO.Class
  import qualified Data.Vector.Unboxed.Mutable as MV
  import qualified Data.Vector.Unboxed as V
  
  times = 100000
  side  = 100
  
  -- Using `forM_` to replace traditional fors
  test_a mvec = 
      forM_ [0..times-1] $ \ n -&gt; do
          forM_ [0..side-1] $ \ y -&gt; do
              forM_ [0..side-1] $ \ x -&gt; do
                  MV.write mvec (y*side+x) 1
  
  -- Using the list monad to replace traditional forms
  test_b mvec = sequence_ $ do
      n &lt;- [0..times-1]
      y &lt;- [0..side-1]
      x &lt;- [0..side-1]
      return $ MV.write mvec (y*side+x) 1
  
  main = do
      let vec = V.generate (side*side) (const 0)
      mvec &lt;- V.unsafeThaw vec :: IO (MV.MVector (PrimState IO) Int)
      -- test_a mvec
      -- test_b mvec
      vec' &lt;- V.unsafeFreeze mvec :: IO (V.Vector Int)
      print $ V.sum vec'
  </code></pre>
  
  <p>This test creates a 100x100 vector, writes 1 to each index using nested loop and repeats that 100k times. Compiling those with just <code>ghc -O2 test.hs -o test</code> (ghc version 7.8.4), the results are: <strong><code>3.853s</code></strong> for the <code>forM_</code> version and <strong><code>10.460s</code></strong> for the <code>list monad</code>. In order to provide a reference, I also programmed this test in JavaScript:</p>
  
  <pre><code>var side  = 100;
  var times = 100000;
  var vec   = [];
  
  for (var i=0; i&lt;side*side; ++i)
      vec.push(0);
  
  for (var n=0; n&lt;times; ++n)
      for (var y=0; y&lt;side; ++y)
          for (var x=0; x&lt;side; ++x)
              vec[x+y*side] = 1;
  
  var s = 0;
  for (var i=0; i&lt;side*side; ++i)
      s += vec[i];
  
  console.log(s);
  </code></pre>
  
  <p>This equivalent JavaScript program takes <strong><code>1s</code></strong> to complete, beating Haskell's unboxed vectors, which is unusual, suggesting that Haskell is not running the loop in constant space, but doing allocations instead. I've then found a library that claims to provide type-guaranteed tight loops <code>Control.Monad.Loop</code>:</p>
  
  <pre><code>-- Using `for` from Control.Monad.Loop
  test_c mvec = exec_ $ do
      n &lt;- for 0 (&lt; times) (+ 1)
      x &lt;- for 0 (&lt; side) (+ 1)
      y &lt;- for 0 (&lt; side) (+ 1)
      liftIO (MV.write mvec (y*side+x) 1)
  </code></pre>
  
  <p>Which runs in <strong><code>1s</code></strong>. That library isn't very used and far from idiomatic, though, so, <strong>what is the idiomatic way to get fast constant-space bidimensional computations?</strong> (Note this isn't a case for REPA as I want to perform arbitrary IO actions on the grid.)</p>