title: Why is Haskell's default string implementation a linked list of chars?
body: <p>The fact that Haskell's default <code>String</code> implementation is not efficient both in terms of speed and memory is well known. As far as I know the <code>[] lists</code> in general are implemented in Haskell as singly-linked lists and for most small/simple data types (e.g. <code>Int</code>) it doesn't seem like a very good idea, but for <code>String</code> it seems like total overkill. Some of the opinions on this matter include:</p>
  
  <p><a href="http://book.realworldhaskell.org/read/efficient-file-processing-regular-expressions-and-file-name-matching.html" rel="noreferrer">Real World Haskell</a></p>
  
  <blockquote>
    <p>On simple benchmarks like this, even programs written in interpreted languages such as Python can outperform Haskell code that uses String by an order of magnitude.</p>
  </blockquote>
  
  <p><a href="https://stackoverflow.com/questions/576213/efficient-string-implementation-in-haskell">Efficient String Implementation in Haskell</a></p>
  
  <blockquote>
    <p>Since a String is just [Char], that is a linked list of Char, it means Strings have poor locality of reference, and again means that Strings are fairly large in memory, at a minimum it's N * (21bits + Mbits) where N is the length of the string and M is the size of a pointer (...). Strings are much less likely to be able to be optimized to loops, etc. by the compiler.</p>
  </blockquote>
  
  <p>I know that Haskell has <code>ByteString</code>s (and <code>Array</code>s) in several nice flavors and that they can do the job nicely, but I would expect the default implementation to be the most efficient one. </p>
  
  <p>TL;DR: Why is Haskell's default <code>String</code> implementation a singly-linked list even though it is terribly inefficient and rarely used for real world applications (except for the really simple ones)? Are there historical reasons? Is it easier to implement?</p>