title: How are lists implemented in Haskell (GHC)?
body: <p>I was just curious about some exact implementation details of lists in Haskell (GHC-specific answers are fine)--are they naive linked lists, or do they have any special optimizations?  More specifically:</p>
  
  <ol>
  <li>Do <code>length</code> and <code>(!!)</code> (for instance) have to iterate through the list?</li>
  <li>If so, are their values cached in any way (i.e., if I call <code>length</code> twice, will it have to iterate both times)?</li>
  <li>Does access to the back of the list involve iterating through the whole list?</li>
  <li>Are infinite lists and list comprehensions memoized?  (i.e., for <code>fib = 1:1:zipWith (+) fib (tail fib)</code>, will each value be computed recursively, or will it rely on the previous computed value?)</li>
  </ol>
  
  <p>Any other interesting implementation details would be much appreciated.  Thanks in advance!</p>