How to define an array type in Haskell

Question

In most functional languages, Haskell included, it is simplicity itself to define a linked-list type:

data List a = Nil | Cons a (List a)

However, I couldn't find anywhere in the Haskell tutorials that I have seen that showed how to define your own array type. How does one define an array data type in the way we defined our own list out of nothing?

Note: My question is not about how to use arrays in Haskell; it is merely how to, in theory, define one's own array type, like what was done for List, without using any sort of library or built-in functionality.

Answer 1

AFAIK, one can't implement a container with O(1) key access time using only pure haskell. Raw memory allocation and access routines needed in order to do this. Surely it is possible to emulate raw memory using pure functional structures (e.g. maps):

import Data.Map

type Ptr = Int
type StupidHeap = Map Ptr Byte

Then one may implement pointer arithmetic and c-like arrays using this heap. But actual time complexity of such container will still remain logarithmic, of course. So those emulations like my StupidHeap just being 'optimized' by compiler using its own builtins. This is how one may reason about ST monad, I believe. If you look through GHC's array implementation, you'll see loads of builtins.

tl;dr: There's no compiler-agnostic solution.

Answer 2

The typeclass Storable gives you access to memory via pointers. It isn't part of the language per se, as it is a FFI (Foreign Function Interface). The primitive types (such as Bool, Char, Int) are already Storable. I would refer you to this set of great lecture notes. The one on memories is great, as are the others. (Kinda weird that this set of notes is almost never mentioned when people give recommendations for learning Haskell).

Also, this question is most likely a duplicate of this, and the answer is also informative.