How to define an array type in Haskell
arrays, haskell, user-defined-types
Solution
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.
Problem
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.