arrays - 如何在 Haskell 中定义数组类型

Question

在包括 Haskell 在内的大多数函数式语言中，定义链表类型本身很简单:

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

但是，我在所见的 Haskell 教程中找不到任何地方显示如何定义自己的数组类型。如何定义数组数据类型，就像我们无中生有地定义自己的列表一样？

备注 : 我的问题不是关于如何在 Haskell 中使用数组；理论上，它只是如何定义自己的数组类型，就像为 List 所做的那样。 ，不使用任何类型的库或内置功能。

Answer 1

AFAIK，仅使用纯 Haskell 无法实现具有 O(1) key 访问时间的容器。执行此操作所需的原始内存分配和访问例程。当然可以使用纯函数结构(例如映射)来模拟原始内存:

import Data.Map

type Ptr = Int
type StupidHeap = Map Ptr Byte

然后可以使用这个堆来实现指针算术和类 c 数组。但当然，这种容器的实际时间复杂度仍将保持对数。所以像我的 StupidHeap 这样的仿真只是被编译器使用自己的内置函数“优化”。我相信这就是人们对 ST monad 的推理方式。
如果您查看 GHC 的数组实现，您会看到大量的内置函数。

tl; dr:没有编译器无关的解决方案。