title: What container really mimics std::vector in Haskell?
body: <h3>The problem</h3>
  <p>I'm looking for a container that is used to save partial results of <code>n - 1</code> problems in order to calculate the <code>n</code>th one. This means that the size of the container, at the end, will always be <code>n</code>.</p>
  <p>Each element, <code>i</code>, of the container depends on at least 2 and up to 4 previous results.</p>
  <p>The container have to provide:</p>
  <ul>
  <li>constant time insertions at either beginning or end (one of the two, not necessarily both)</li>
  <li>constant time indexing in the middle</li>
  </ul>
  <p>or alternatively (given a <code>O(n)</code> initialization):</p>
  <ul>
  <li>constant time single element edits</li>
  <li>constant time indexing in the middle</li>
  </ul>
  <h3>What is <a href="http://en.cppreference.com/w/cpp/container/vector" rel="noreferrer"><code>std::vector</code></a> and why is it relevant</h3>
  <p>For those of you who don't know C++, <code>std::vector</code> is a dynamically sized array. It is a perfect fit for this problem because it is able to:</p>
  <ul>
  <li>reserve space at construction</li>
  <li>offer constant time indexing in the middle</li>
  <li>offer constant time insertion at the end (with a reserved space)</li>
  </ul>
  <p>Therefore this problem is solvable in <code>O(n)</code> complexity, in C++.</p>
  <h3>Why <code>Data.Vector</code> is not <code>std::vector</code></h3>
  <p><code>Data.Vector</code>, together with <code>Data.Array</code>, provide similar functionality to <code>std::vector</code>, but not quite the same. Both, of course, offer constant time indexing in the middle, but they offer neither constant time modification (<code>(//)</code> for example is at least <code>O(n)</code>) nor constant time insertion at either beginning of end.</p>
  <h3>Conclusion</h3>
  <p>What container really mimics <code>std::vector</code> in Haskell? Alternatively, what is my best shot?</p>