Haskell arrays vs lists

Question

I'm playing with Haskell and Project Euler's 23rd problem. After solving it with lists I went here where I saw some array work. This solution was much faster than mine. So here's the question. When should I use arrays in Haskell? Is their performance better than lists' and in which cases?

Answer 1

The most obvious difference is the same as in other languages: arrays have O(1) lookup and lists have O(n). Attaching something to the head of a list (:) takes O(1); appending (++) takes O(n).

Arrays have some other potential advantages as well. You can have unboxed arrays, which means the entries are just stored contiguously in memory without having a pointer to each one (if I understand the concept correctly). This has several benefits--it takes less memory and could improve cache performance.

Modifying immutable arrays is difficult--you'd have to copy the entire array which takes O(n). If you're using mutable arrays, you can modify them in O(1) time, but you'd have to give up the advantages of having a purely functional solution.

Finally, lists are just much easier to work with if performance doesn't matter. For small amounts of data, I would always use a list.

Answer 2

And if you're doing much indexing as well as much updating,you can

• use Maps (or IntMaps), O(log size) indexing and update, good enough for most uses, code easy to get right
• or, if Maps are too slow, use mutable (unboxed) arrays (STUArray from Data.Array.ST or STVectors from the vector package; O(1) indexing and update, but the code is easier to get wrong and generally not as nice.

For specific uses, functions like accumArray give very good performance too (uses mutable arrays under the hood).

Answer 3

Arrays have O(1) indexing (this used to be part of the Haskell definition), whereas lists have O(n) indexing. On the other hand, any kind of modification of arrays is O(n) since it has to copy the array. So if you're going to do a lot of indexing but little updating, use arrays.