How could a true Vector type be implemented in Haskell? In order for something to be a Vector, it has to be stored sequentially in memory, with O(1) random access. But Haskell hides its memory management, and its datatypes describe trees! So how could you express that kind of requirement?
3
Not all data types in Haskell are trees. There are also the builtin types like functions or Int. Among those you find the type Array which gives you O(1) access to its elements.
Some compilers, like GHC, also provide unboxed arrays. Those use less memory and per element access is faster, but that does not change the complexity of course.
On top of those arrays one can build data types similar to std::vector in C++. An example is the vector library.
You should look at Data.Vector.Unboxed and Data.Vector.Mutable in the vector package:
https://hackage.haskell.org/package/vector