Vectors

Vectors combine the performance characteristics of arrays with the simpler API of lists. Let's see how they work!

If you're looking for additional code examples and some practice problems with these data structures, look no further than our Data Structures In-Depth eBook!

What are Vectors good for?

Vectors are similar to arrays in a lot of ways. They allow for constant time access of elements by an integer index. They aren't flexible in the index type the way arrays are, but they're API works more like lists, which can make them easier to work with. In particular, vectors have a richer variety of accessing functions than arrays. They're the only core Haskell type that allows for slicing. Extending vectors is easier API-wise than arrays, though it is still an inefficient operation.

Like arrays, vectors use memory-efficient storage. Unlike arrays, they use a performance improvement called "fusion". If you have successive "loops" over the same vector (maps, folds, traverses, etc.), this code can often be optimized at compile-time to be a single loop.

What are Vectors not as good for?

Vectors have the same general shortcomings as arrays. While they can be "modified" in the Haskell sense of the term, modification is inefficient, because all the elements of the vector must be copied to maintain the good memory performance. As with arrays, vectors can also come in a truly "mutable" flavor, but that requires monadic behavior outside the scope of this chapter.

Vector Parameters and Constraints

Vectors have a single type parameter for the contained type. There are no constraints on this type.

How do I create a Vector?

With vectors, we get a return to our common initialization pattern of empty, singleton, and fromList.

empty :: Vector a
singleton :: a -> Vector a
fromList :: [a] -> Vector a

How do I get the size of a Vector?

Vectors have a length function that works in constant O(1) time.

length :: Vector a -> Int

How do I add elements to a Vector?

You can "add" an element to either end of a vector, but these are both O(n) operations, requiring the creation of a completely new vector and copying of elements. To add an element to the front, use the cons function:

cons :: a -> Vector a -> Vector a

Then to add an element to the back, you can use the snoc function ("snoc" is the reverse of "cons").

snoc :: Vector a -> a -> Vector a

Incidentally, vectors also have the same update operator as arrays: (//). You can supply a list of integer/element pairs that should be updated. Of course, this also requires a full O(n) copy of the list.

(//) :: Vector a -> [(Int, a)] -> Vector a

How do I access Vectoor elements?

Vectors have two "bang" operators to access elements by their numeric index. When using the question mark though, it is a "safe" operation, returning a Maybe value. The first operator will throw an error if the index is out of bounds, like its cousins from map and array types.

(!) :: Vector a -> Int -> a
(!?) :: Vector a -> Int -> Maybe a

Like lists, you can also use head to get the first element, or last to get the final element. These throw errors if the vector is empty. Unlike lists, both these operations take constant O(1) time.

head :: Vector a -> a
last :: Vector a -> a

You can also take the first X elements of a vector. This operation is also constant time.

take :: Int -> Vector a -> Vector a

Finally, in their most unique action, vectors allow you to take a "slice". This means you can specify a starting index, and length of the slice, and then the vector, and you'll get a new vector containing those specific elements. This is a constant time operation, working on the original vector's memory. (Once you understand that this operation is constant time, it will make more sense why a lot of these other operations are as well).

slice :: Int -> Int -> Vector a -> Vector a

Slicing will throw an error if your vector is not long enough to complete the slice, so be careful!

How do I delete elements from a Vector?

Vectors have a few functions for removing elements, especially the first and last element. As with lists, the tail function exists to "remove" the first element, giving the remainder. This takes constant time, but will crash if the vector is empty.

tail :: Vector a -> Vector a

Like lists, they also have init, removing the last element. While this took O(n) time for lists, it is O(1) for vectors!

init :: Vector a -> Vector a

We also have a drop function, removing any number of initial elements you specify. This will simply yield an empty vector if the number is too high.

drop :: Int -> Vector a -> Vector a

Finally, we have a couple safer functions that both access an element and yield the remainder of the vector. The uncons function will give a tuple of the first element and the "tail" of the vector. This is wrapped in Maybe - if the vector is empty, you get Nothing.

uncons :: Vector a -> Maybe (a, Vector a)

Similarly, we have unsnoc, the reverse of uncons. Both these operations take constant O(1) time.

unsnoc :: Vector a -> Maybe (Vector a, a)

How do I combine Vectors?

Two vectors can be combined with the (++) operator, just like lists. This operator also functions as the Semigroup append operator (<>). This operation is O(n + m), scaling with the sum of the vector sizes.

(++) :: Vector a -> Vector a -> Vector a

To combine a whole list of vectors, use the concat function.

concat :: [Vector a] -> Vector a

Import Notes

The accessing operators and the type name can be unqualified (depending on what other structures your code uses, of course). The append operator should be qualified with everything else. Otherwise you'll have to explicitly import Prelude and hide the list (++) operator.

import Data.Vector (Vector, (!), (!?))
import qualified Data.Vector as V

Conclusion

If you want to learn about more data structures in Haskell, make sure to head back to the series page! If you've been doing this series in order, you've just got two structures left! Next up is the Sequence!