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

据我所知，Haskell中的列表类型是使用链表在内部实现的。但是，该语言的用户没有看到实现的细节，也没有能力修改组成链接列表的“链接”以允许它指向不同的内存地址。我想这是在内部完成的。Haskell中的列表：数据类型还是抽象数据类型？

那么，那么列表类型是否可以像Haskell一样被限定呢？它是“数据类型”还是“抽象数据类型”？什么是实现的链表类型？

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

举个例子来说，这个代码段设计成一个列表的索引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函数尤其如此丑，但它可能没有？）

请不要犹豫，纠正我，如果我说的是错误的，并感谢您的时间。

来源

2009-12-21 CharlieP

欢迎来到StackOverflow！伟大的第一个问题 – Sampson 2009-12-21 19:53:00

http://en.wikibooks.org/wiki/Haskell/List_processing – 2009-12-21 19:57:13

感谢所有回答我的问题的人，尽管我只能将其中的一个标记为我的“接受的答案”，但您都非常有帮助。 – CharlieP 2009-12-22 10:52:17

您对数据结构的可变性感到困惑。它是一个正确的列表 - 只是不允许你修改。 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）。

由于看起来这是一个链表，所以让我们清楚一下链表是什么：它是一个由单元格组成的数据结构，其中每个单元格都有一个值和对下一个项目的引用。

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

在Lisp中，它被定义为(head . tail)，其中head是价值和tail是参照下一个项目：在C，因为它可能被定义。

在Haskell，它的定义为data [] a = [] | a : [a]，其中a是值和[a]是参照下一个项目。

正如你所看到的，这些数据结构都是等价的。唯一的区别是在C和Lisp中，它们不是纯粹的功能，头部和尾部值是可以改变的东西。在Haskell中，你不能改变它们。

来源

2009-12-21 20:39:33 Chuck

Haskell是一个纯粹的函数式编程语言。这意味着根本不能做任何改变。

列表是非抽象类型，它只是一个链表。

你可以认为这种方式定义他们的：

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

这正是被定义的链接列表的方式 - 一个头元素（指针）休息。

请注意，这在内部没有区别 - 如果您想要更高效的类型，请使用Sequence或Array。（但由于不允许更改，所以您不需要实际复制列表以便区分副本，所以这可能是性能增益而不是命令式语言）

来源

2009-12-21 19:56:07 Dario

事实上，内部模块GHC.Types定义为“infixr 5：”。数据[] a = [] | a：[a]' – ephemient 2009-12-21 19:57:54

我还是不明白为什么上面定义的列表类型是一个链表。由于Haskell是纯粹的功能，我知道数据是不可变的，但我试图反对程序员在Haskell编码时使用的实际列表，以及编译为较低级别语言时GHC实现这些列表。对不起，如果我的问题不够清楚。 – CharlieP 2009-12-21 20:22:06

CharlieP，你正在寻找的指针，但没有找到任何。考虑Java，它也缺少指针。在纯Java中建立一个链表是不可能的？不，当然不。你将会引用一个头对象，它本身会有一个值和一个对列表中下一个对象的引用。添加一个标记对象来指示列表的结尾，然后就完成了。这正是给定的类型定义所说的。你不需要显式的指针来创建链表。你只需要链接。谁在乎GHC在底下做什么？ – 2009-12-21 21:44:26

您的代码可能有效，但绝对不是最佳选择。您想在索引0中插入一个项目一个例子就拿情况：如果按照这个推导

add [200, 300, 400] [] 0 100

，你结束了：

add [200, 300, 400] [] 0 100 
add [300, 400] (200:100:[]) (-1) 100 
add [400] (300:[200, 100]) (-2) 300 
add [] (400:[300, 200, 100]) (-3) 400 
reverse [400, 300, 200, 100] 
[100, 200, 300, 400]

但我们只需要添加一个项目到列表的开头！这样的操作很简单！它是（:)

add [200, 300, 400] [] 0 100 
100:[200, 300, 400] 
[100, 200, 300, 400]

想想多少名单真的需要扭转。

您询问运行时是否修改链接列表中的指针。因为Haskell中的列表是不可变的，所以没有人（甚至是运行时）修改链表中的指针。这就是为什么，例如，将一个项目追加到列表的前面是很便宜的，但是在列表的后面添加一个元素却很昂贵。当您将一个项目追加到列表的前面时，您可以重新使用所有现有的列表。但是当你在最后追加一个项目时，它必须建立一个全新的链接列表。为了使列表前面的操作便宜，数据的不变性是必需的。

来源

2009-12-21 20:41:11

另请注意，如果您给它一个无限列表，那么算法会执行什么操作。 KABOOM！ – Chuck 2009-12-21 21:30:12

非常好的一点！ – 2009-12-21 21:38:27

回复：添加元素到列表的末尾，我建议使用(++)运营商和splitAt功能：

add xs a n = beg ++ (a : end) 
    where 
    (beg, end) = splitAt n xs

的List是一个链表，但它是只读的。您无法修改List，而是创建一个新的List结构，该结构包含您想要的元素。我没有阅读，但this book可能会得到您的基本问题。

HTH

来源

2009-12-21 20:47:17

在Haskell，“数据类型”和“抽象类型”是本领域的术语：

A“数据类型”（这是不抽象）具有可见值构造您可以在case表达式或函数定义上进行模式匹配。
“抽象类型”没有可见值构造函数，因此您无法在该类型的值上进行模式匹配。

给定一个类型a，[a]（的a列表）是一个数据类型，因为你可以在可见的构造利弊模式匹配（书面:）和零（书面[]）。一个抽象类型的例子是IO a，你不能通过模式匹配来解构。

来源

2009-12-22 02:57:52

编译器可以自由选择任何想要列表的内部表示。实际上它确实有所不同。显然，列表“[1 ..]”不是作为经典的cons系列单元来实现的。

事实上，一个懒惰列表存储为一个thunk，其计算结果为包含下一个值和下一个thunk的cons单元（一个thunk基本上是一个函数指针加上函数的参数，它被实际值替换一旦函数被调用）。另一方面，如果编译器中的严格性分析器可以证明整个列表总是被评估的，那么编译器只会将整个列表创建为一系列的cons单元。

来源

2009-12-22 07:13:06

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

回答

相关问题