哈斯克尔.为什么数组比列表更快？

Question

我正在研究Haskell.我有下一个问题:

List类型是Haskell中的基本类型.Haskell中的数组基于列表.这是索引列表[Ix a]和函数按表格列出 - 对[[Ix a,Value]]列表.为什么Array比列表更快,如果在里面使用列表？

Answer 1

我怕你错了.

在Haskell中有几个数组实现,但据我所知,它们都是在连续的内存数组之上实现的.因此,有可能O(1)访问元素进行阅读.

数组和列表之间的相似性仅存在于操作集级别.

Answer 2

数组不是基于列表,它们与其他编程语言类似地实现,具有连续的存储区域.

创建它们的最常用方法是,数组函数将索引,值对列表作为参数,当您打印它们时,它们也会显示为这样的列表.这是因为Haskell中的数组不仅可以通过整数进行索引,还可以通过实现Ix类型类的任何内容进行索引,例如(Int,Int)-pairs,Booleans,Char和许多其他版本.所以[(index,value)]表示实际上是显示数组的唯一合理,一致的方式,就像在Haskell中一样.

Answer 3

数组不是基于列表.列表是常规的递归数据类型:

data [] a = [] | a : [a]

虽然各种数组库(如uvector,array,vector,carray,hmatrix)使用低级读写操作来向数组提供接口.虽然具有不同的复杂性,但两种数据结构都可以表示序列,但没有相似之处.