title: Rewriting as a practical optimization technique in GHC: Is it really needed?
body: <p>I was reading the paper authored by Simon Peyton Jones, et al. named <a href="http://research.microsoft.com/en-us/um/people/simonpj/papers/rules.htm">&ldquo;Playing by the Rules: Rewriting as a practical optimization technique in GHC&rdquo;</a>. In the second section, namely &ldquo;The basic idea&rdquo; they write:</p>
  
  <blockquote>
    <p>Consider the familiar <code>map</code> function, that applies a function to each element of a list. Written in Haskell, <code>map</code> looks like this:</p>
  </blockquote>
  
  <pre><code>map f []     = []
  map f (x:xs) = f x : map f xs
  </code></pre>
  
  <blockquote>
    <p>Now suppose that the compiler encounters the following call of <code>map</code>:</p>
  </blockquote>
  
  <pre><code>map f (map g xs)
  </code></pre>
  
  <blockquote>
    <p>We know that this expression is equivalent to</p>
  </blockquote>
  
  <pre><code>map (f . g) xs
  </code></pre>
  
  <blockquote>
    <p>(where &ldquo;.&rdquo; is function composition), and we know that the latter expression is more efficient than the former because there is no intermediate list. But the compiler has no such knowledge.</p>
    
    <p>One possible rejoinder is that the compiler should be smarter --- but the programmer will always know things that the compiler cannot figure out. Another suggestion is this: allow the programmer to communicate such knowledge directly to the compiler. That is the direction we explore here.</p>
  </blockquote>
  
  <p>My question is, why can't we make the compiler smarter? The authors say that &ldquo;but the programmer will always know things that the compiler cannot figure out&rdquo;. However, that's not a valid answer because the compiler can indeed figure out that <code>map f (map g xs)</code> is equivalent to <code>map (f . g) xs</code>, and here is how:</p>
  
  <pre><code>map f (map g xs)
  </code></pre>
  
  <ol>
  <li><p><code>map g xs</code> unifies with <code>map f [] = []</code>.</p>
  
  <p>Hence <code>map g [] = []</code>.</p></li>
  <li><p><code>map f (map g []) = map f []</code>.</p>
  
  <p><code>map f []</code> unifies with <code>map f [] = []</code>.</p>
  
  <p>Hence <code>map f (map g []) = []</code>.</p></li>
  <li><p><code>map g xs</code> unifies with <code>map f (x:xs) = f x : map f xs</code>.</p>
  
  <p>Hence <code>map g (x:xs) = g x : map g xs</code>.</p></li>
  <li><p><code>map f (map g (x:xs)) = map f (g x : map g xs)</code>.</p>
  
  <p><code>map f (g x : map g xs)</code> unifies with <code>map f (x:xs) = f x : map f xs</code>.</p>
  
  <p>Hence <code>map f (map g (x:xs)) = f (g x) : map f (map g xs)</code>.</p></li>
  </ol>
  
  <p>Hence we now have the rules:</p>
  
  <pre><code>map f (map g [])     = []
  map f (map g (x:xs)) = f (g x) : map f (map g xs)
  </code></pre>
  
  <p>As you can see <code>f (g x)</code> is just <code>(f . g)</code> and <code>map f (map g xs)</code> is being called recursively. This is exactly the definition of <code>map (f . g) xs</code>. The algorithm for this automatic conversion seems to be pretty simple. So why not implement this instead of rewriting rules?</p>