Haskell 中的列表 : data type or abstract data type?

Question

据我了解，Haskell 中的列表类型是在内部使用链表实现的。但是，该语言的用户无法看到实现的细节，也无法修改构成链表的“链接”以使其指向不同的内存地址。我想，这是在内部完成的。

那么，列表类型如何被限定为 Haskell 呢？它是“数据类型”还是“抽象数据类型”？什么是链表类型的实现？

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

例如，这段代码旨在将元素 a 添加到列表的索引 n 处:

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 中，它们不是纯粹的函数式，head 和 tail 的值是你可以改变的。在 Haskell 中，您无法更改它们。