Hello. I am study the Haskell. I am have the next question :
The List type is basic type in haskell. Array in haskell based on lists . This is list of indices [Ix a] and function presents by table - list of pairs [(Ix a,Value)]. Why Array faster then lists, if inside it use lists ?
Thank you.
I am afraid you're wrong.
There're several implementations of arrays in Haskell, but as far as I understand, all of them are implemented on top of contiguous memory arrays. Because of this there's a possibility of O(1) access to element for reading.
Similarity between arrays and lists exists only on operation set level.
Arrays are not based on lists, they are implemented similarly to other programming languages, with a continuous memory area.
The most common way to create them, the array function takes a list of index, value pairs as an argument and when you print them they are shown like such a list as well. This is because arrays in Haskell can be indexed not just by integers but by anything that implements the Ix typeclass, for example (Int, Int)-pairs, Booleans, Char's and many other versions. So the [(index, value)] representation is really the only sensible, consistent way to display an array as general as the ones in Haskell.
Arrays are not based on lists. Lists are a regular, recursive data type:
data [] a = [] | a : [a]
While the various array libraries, such as uvector, array, vector, carray, hmatrix, use low level read and write operations to present an interface to arrays. There's no similarity, other than that both data structures can represent sequences, though with different complexity.