如何在Haskell中定义数组类型

Question

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

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

但是,我在Haskell教程中找不到任何地方,我已经看到它展示了如何定义自己的数组类型.如何定义一个数组数据类型的方式我们从无到有的定义我们自己的列表？

注意:我的问题不是关于如何在Haskell中使用数组; 理论上,它只是如何定义一个自己的数组类型,就像所做的那样List,而不使用任何类型的库或内置功能.

Answer 1

AFAIK,只能使用纯haskell来实现具有O(1)密钥访问时间的容器.为了做到这一点,需要原始内存分配和访问例程.当然可以使用纯功能结构(例如地图)模拟原始内存:

import Data.Map

type Ptr = Int
type StupidHeap = Map Ptr Byte

然后可以使用此堆实现指针算术和类c数组.但是,当然,这种容器的实际时间复杂性仍然是对数的.所以像我的StupidHeap这样的仿真只是由编译器使用自己的内置来"优化".我相信这就是人们对ST monad的理由.如果你看一下GHC的数组实现,你会看到很多内置函数.

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