title: Reasonably efficient pure-functional matrix product in Haskell?
body: <p>I know Haskell a little bit, and I wonder if it's possible to write something like a matrix-matrix product in Haskell that is all of the following:</p>
  
  <ol>
  <li><strong>Pure-functional</strong>: no <code>IO</code> or <code>State</code> monads in its type signature (I don't care what happens in the function body. <em>That is, I don't care if the function body uses monads, as long as the whole function is pure</em>). I may want to use this matrix-matrix product in a pure function.</li>
  <li><strong>Memory-safe: no malloc or pointers</strong>. I know that it's possible to "write C" in Haskell,
  but you lose memory safety. Actually writing this code in C and interfacing it with Haskell also loses memory safety.</li>
  <li><strong>As efficient as, say, Java.</strong> For concreteness, let's assume I'm talking about a simple triple loop, single precision, contiguous column-major layout (<code>float[]</code>, not <code>float[][]</code>) and matrices of size 1000x1000, and a single-core CPU. (If you are getting 0.5-2 floating point operations per cycle, you are probably in the ballpark.)</li>
  </ol>
  
  <p>(I don't want this to sound like a challenge, but note that Java can satisfy <strong>all</strong> of the above easily.)</p>
  
  <p>I already know that</p>
  
  <ol>
  <li><strong>The triple loop implementation is not the most efficient one</strong>. It's quite cache-oblivious. It's better to use a well-written <a href="https://en.wikipedia.org/wiki/Basic_Linear_Algebra_Subprograms" rel="noreferrer">BLAS</a> implementation in this particular case. However, one can not always count on a C library being available for what one is trying to do. I wonder if reasonably efficient code can be written in normal Haskell.</li>
  <li><strong>Some people wrote whole research papers that demonstrate #3</strong>. However, I'm not a computer science researcher. I wonder if it's possible to keep simple things simple in Haskell.</li>
  <li><strong>The Gentle Introduction to Haskell has a matrix product implementation</strong>. It wouldn't satisfy the above requirements though.</li>
  </ol>
  
  <p>Addressing comments:</p>
  
  <blockquote>
    <p>I have three reasons: first, the "no malloc or pointers" requirement
    is as yet ill-defined (I challenge you to write any piece of Haskell
    code which uses no pointers);</p>
  </blockquote>
  
  <p>I saw plenty of Haskell programs not using <code>Ptr</code>. Perhaps it refers to the fact that at the machine instruction level, pointers will be used? That's not what I meant. I was referring to the abstraction level of the Haskell source code.</p>
  
  <blockquote>
    <p>second, the attack on CS research is out of place (and furthermore I
    can't imagine anything simpler than using code somebody else has
    already written for you); third, there are many matrix packages on
    Hackage (and the prep work for asking this question should include
    reviewing and rejecting each).</p>
  </blockquote>
  
  <p>It seems that your #2 and #3 are the same ("use existing libraries"). I'm interested in the matrix product as a simple test of what Haskell can do on its own, and whether it allows you to "keep simple things simple". I could have easily come up with a numerical problem that doesn't have any ready libraries, but then I'd have to explain the problem, whereas everyone already knows what a matrix product is.</p>
  
  <blockquote>
    <p>How can Java possibly satisfy 1.? Any Java method is essentially
    <code>:: IORef Arg -&gt; ... -&gt; IORef This -&gt; IO Ret</code></p>
  </blockquote>
  
  <p>This goes to the root of my question, actually (+1). While Java does not claim to track purity, Haskell does. In Java, whether the function is pure or not is indicated in the comments. I can claim that the matrix product is pure, even though I do mutation in the function body. <strong>The question is whether Haskell's approach (purity encoded in the type system) is compatible with efficiency, memory-safety and simplicity.</strong></p>