Haskell中的列表:数据类型还是抽象数据类型？

Question

据我所知,Haskell中的列表类型是使用链表在内部实现的.但是,该语言的用户无法查看实现的详细信息,也无法修改组成链接列表的"链接"以允许其指向不同的内存地址.我想,这是内部完成的.

那么,如何在Haskell中限定列表类型？它是"数据类型"还是"抽象数据类型"？那个实现的链表类型是什么？

另外,由于Prelude提供的列表类型不是链表类型,如何实现基本链表功能？

举例来说,这段代码旨在在列表的索引n处添加元素a:

add [] acc _ _ = reverse acc
add (x:xs) acc 0 a = add xs (x:a:acc) (-1) a 
add (x:xs) acc n a = add xs (x:acc) (n-1) a

使用"真实"链表,添加元素只需修改指向内存地址的指针.这在Haskell中是不可能的(或者是它？),因此问题是:我的实现是将一个元素添加到列表中最好的一个,或者我错过了一些东西(reverse我觉得,使用该函数特别难看,但是可以不做吗？)

如果我说的话有误,请不要犹豫,纠正我,谢谢你的时间.

Answer 1

你混淆了数据结构的可变性.这是一个正确的列表 - 只是你不允许修改的列表.Haskell纯粹是功能性的,意味着值是不变的 - 您不能更改列表中的项目,而不能将数字2转换为3.而是执行计算以根据需要更改创建新值.

您可以通过以下方式最简单地定义该函数:

add ls idx el = take idx ls ++ el : drop idx ls

该列表el : drop idx ls重用原始列表的尾部,因此您只需要生成一个新的列表idx(这是take函数的作用).如果你想使用显式递归来实现它,你可以像这样定义它:

add ls 0 el   = el : ls
add (x:xs) idx el
  | idx < 0   = error "Negative index for add"
  | otherwise = x : add xs (idx - 1) el
add [] _ el   = [el]

这以相同的方式重用列表的尾部(这el : ls是第一种情况).

由于您似乎无法查看这是一个链接列表,因此我们要清楚链接列表是什么:它是由单元格组成的数据结构,其中每个单元格都有一个值和对下一个项目的引用.在C中,它可能被定义为:

struct ListCell {
void *value; /* This is the head */
struct ListCell *next; /* This is the tail */
}

在Lisp中,它定义为(head . tail),head值在哪里,tail是对下一个项的引用.

在Haskell中,它定义为data [] a = [] | a : [a],a值在哪里,[a]是对下一个项的引用.

如您所见,这些数据结构都是等效的.唯一的区别是在C和Lisp中,它们不是纯粹的功能,头部和尾部值是你可以改变的东西.在Haskell中,你无法改变它们.

Answer 2

Haskell是一种纯函数式编程语言.这意味着根本无法进行任何更改.

列表是非抽象类型,它只是一个链表.

您可以这样定义它们:

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

这正是链接列表的定义方式 - 头部元素和(其指向)其余部分.

请注意,这在内部没有区别 - 如果您想要更高效的类型,请使用Sequence或Array.(但由于不允许进行任何更改,因此您无需实际复制列表以区分副本,这可能是性能增益而不是命令式语言)

CharlieP,你正在寻找指针,但没有找到任何指针.考虑Java,它也缺少指针.用纯Java制作链表是不可能的？不,当然不.您将引用一个头对象,它本身将具有值和对列表中下一个对象的引用.添加一个sentinel对象来指示列表的结尾,然后就完成了.这正是给定类型定义所说的.您不需要显式指针来创建链接列表.你只需要链接.谁关心GHC在幕后做什么？ (5认同)
实际上,内部模块`GHC.Types`将其定义为`infixr 5 :; data [] a = [] | a:[a]` (3认同)

Answer 3

在Haskell中,"数据类型"和"抽象类型"是艺术术语:

给定一个类型a,[a](list of a)是一种数据类型,因为你可以在可见的构造函数cons(书面:)和nil(书面[])上进行模式匹配.抽象类型的一个例子是IO a,你无法通过模式匹配来解构.