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
    Use the mathematical definitions for true vectors. Here's a vector space library for you hackage.haskell.org/package/vector-space-0.8.7/docs/… – Thomas Eding Jul 11 '14 at 22:50
  • 3
    Where do those requirements for Vector come from? I know multiple definitions of the term 'vector' and only one of them has such requirements (C++'s std::vector). – Bart van Ingen Schenau Jul 12 '14 at 7:19
  • To some extend in the same way as how to store a value in register in say C or C++, or you free memory in GC language - compiler is free to rearrange data, put the values in register etc. or expose the things by (extensions)[tinyurl.com/ovvxtqt]/(libraries)[http://hackage.haskell.org/… to programmers if they really need them - but assumption is that they don't care in most cases. In similar way Haskell programmers don't care in most cases if the data is packed in sequential region of memory instead of, for example eliminating the need for evaluation entirely. – Maciej Piechotka Jul 12 '14 at 21:49

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:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.