在大多数功能语言（包括Haskell）中，定义链接列表类型本身很简单：
data List a = Nil | Cons a (List a)
但是，我在Haskell教程中找不到任何内容，这些教程显示了如何定义自己的数组类型。如何以一种定义自己的列表的方式定义数组数据类型？
注意：我的问题不是关于如何在Haskell中使用数组。从理论上讲，这仅仅是如何定义自己的数组类型，就像对进行的操作一样List，而无需使用任何类型的库或内置功能。
AFAIK，仅使用纯haskell不能实现具有O（1）键访问时间的容器。为此，需要进行原始内存分配和访问例程。当然可以使用纯函数结构（例如，映射）来模拟原始内存：
import Data.Map
type Ptr = Int
type StupidHeap = Map Ptr Byte
然后，可以使用此堆实现指针算术和类似c的数组。当然，这种容器的实际时间复杂度仍将保持对数。因此，像我的StupidHeap这样的仿真只是由编译器使用其自身的内置函数进行“优化”的。我相信，这可能是人们对ST monad的推理方式。如果您查看GHC的数组实现，将会看到大量的内建函数。
tl; dr：没有与编译器无关的解决方案。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句