Menu
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?
715
Data is immutable in Haskell. We do not mutate the existing list but build a new list from applying the function. Haskell helps us to avoid the security issue by default.
Although Haskell has an incremental array update operator, the main thrust of the array facility is monolithic. Arrays are not part of the Standard Prelude---the standard library contains the array operators. Any module using arrays must import the Array module.
Definition of Haskell Array. In Haskell array is used to store the different values, it is immutable in nature, which means once assigned we cannot modify the original one. If we perform any operations on the array then it will always return us to the new array, only accessing elements is fine with the original one.
In Haskell, lists are a homogenous data structure. It stores several elements of the same type. That means that we can have a list of integers or a list of characters but we can't have a list that has a few integers and then a few characters. And now, a list!
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.
147
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
