title: Haskell: List fusion, where is it needed?
body: <p>Lets say we have the following:</p>
  
  <pre><code>l = map f (map g [1..100])
  </code></pre>
  
  <p>And we want to do:</p>
  
  <pre><code>head l
  </code></pre>
  
  <p>So we get:</p>
  
  <pre><code>head (map f (map g [1..100]))
  </code></pre>
  
  <p>Now, we have to get the first element of this. <code>map</code> is defined something like so:</p>
  
  <pre><code>map f l = f (head l) : (map f (tail l))
  </code></pre>
  
  <p>So then we get:</p>
  
  <pre><code>f (head (map g [1..100]))
  </code></pre>
  
  <p>And then applied again:</p>
  
  <pre><code>f (g (head [1..100]))
  </code></pre>
  
  <p>Which results in</p>
  
  <pre><code>f (g 1)
  </code></pre>
  
  <p>No intermediate lists are formed, simply due to laziness.</p>
  
  <p>Is this analysis correct? And with simple structures like this:</p>
  
  <pre><code>foldl' ... $ map f1 $ map f2 $ createlist
  </code></pre>
  
  <p>are intermediate lists ever created, even without "list fusion"? (I think laziness should eliminate them trivially).</p>
  
  <hr>
  
  <p>The only place I can see a reason to keep a list is if we did:</p>
  
  <pre><code>l' = [1..100]
  l = map f (map g l')
  </code></pre>
  
  <p>Where we might want to keep <code>l'</code>, if it is used elsewhere. However, in the <code>l'</code> case above here, it should be fairly trivial for the compiler to realise its quicker just to recalculate the above list than store it.</p>