当前位置：文江博客话题详情

为什么 F# 列表没有尾指针

发布于 2024-12-09 06:15:34 字数 178 浏览 1 评论 0原文

或者换句话说，拥有一个基本的、只有一个头指针的单链表会给你带来什么好处？我可以看到尾指针的好处是：

O(1) 列表串联
O(1) 将内容附加到列表的右侧

与 O(n) 列表串联相比，这两者都是相当方便的事情（其中 n 是左侧列表的长度？）。丢掉尾指针有什么好处呢？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

戴着白色围巾的女孩 2024-12-16 06:15:34

F# 与许多其他函数式语言一样，有一个 cons-list （该术语最初来自LISP，但概念是相同的）。在 F# 中，:: 运算符（或 List.Cons）用于 cons'ing：注意签名是 'a –> '一个列表-> '列表（请参阅掌握 F# 列表）。

不要将 cons-list 与不透明的链表实现混淆，后者包含离散的第一个[/最后]节点 - cons-list 中的每个单元都是[不同]列表的开始！ ，“列表”只是从给定 cons-cell 开始的单元链。

当以类似函数的方式使用时，这提供了一些优点：一是所有“尾部”单元都是共享的，并且由于每个 cons-cell 都是不可变的（“数据”可能是可变的，但这是一个不同的问题），因此不存在一种对“尾部”单元格进行更改并弄乱包含该单元格的所有其他列表的方法。

由于此属性，可以高效构建[新]列表 - 也就是说，它们不需要副本 - 只需cons到前面即可。此外，将列表解构为 head :: tail 也非常高效 - 再次强调，无需复制 - 这在递归函数中通常非常有用。

这种不可变属性通常不存在于[标准可变]双链表实现中，因为附加会增加副作用：内部“最后”节点（类型现在不透明）和“尾部”单元格之一被更改。（有不可变的序列类型允许“有效恒定时间”追加/更新，例如Scala 中的immutable.Vector - 然而，与 cons-list 相比，这些是重量级对象，cons-list只不过是一系列组合在一起的单元格.)

如前所述，cons-list 也有缺点，并不适合所有任务 - 特别是，创建一个新列表（除了 cons 到头部之外）是一个 O(n) 操作，fsvo n ，并且无论好坏（或更坏），该列表都是不可变的。

我建议创建您自己的 concat 版本，以了解此操作是如何真正完成的。（文章为什么我喜欢F#：列表 - 基础知识涵盖了这一点。）

快乐编码。

另请参阅相关帖子：为什么只能添加到列表前面用函数式语言？

F#, like many other functional[-ish] languages, has a cons-list (the terminology originally comes from LISP, but the concept is the same). In F# the :: operator (or List.Cons) is used for cons'ing: note the signature is ‘a –> ‘a list –> ‘a list (see Mastering F# Lists).

Do not confuse a cons-list with an opaque Linked List implementation which contains a discrete first[/last] node - every cell in a cons-list is the start of a [different] list! That is, a "list" is simply the chain of cells that starts at a given cons-cell.

This offers some advantages when used in a functional-like manner: one is that all the "tail" cells are shared and since each cons-cell is immutable (the "data" might be mutable, but that's a different issue) there is no way to make a change to a "tail" cell and flub up all the other lists which contain said cell.

Because of this property, [new] lists can be efficiently built - that is, they do not require a copy - simply by cons'ing to the front. In addition, it is also very efficient to deconstruct a list to head :: tail - once again, no copy - which is often very useful in recursive functions.

This immutable property generally does not exist in a [standard mutable] Double Linked List implementation in that appending would add side-effects: the internal 'last' node (the type is now opaque) and one of the "tail" cells are changed. (There are immutable sequence types that allow an "effectively constant time" append/update such as immutable.Vector in Scala -- however, these are heavy-weight objects compared to a cons-list that is nothing more than a series of cells cons'ed together.)

As mentioned, there are also disadvantages a cons-list is not appropriate for all tasks - in particular, creating a new list except by cons'ing to the head is an O(n) operation, fsvo n, and for better (or worse) the list is immutable.

I would recommend creating your own version of concat to see how this operation is really done. (The article Why I love F#: Lists - The Basics covers this.)

Happy coding.

回复收藏 0 原文

丧 2024-12-16 06:15:34

F# 列表是不可变的，没有“追加/连接”之类的东西，而只是创建新列表（可能会重用旧列表的一些后缀）。不变性有很多优点，超出了这个问题的范围。（所有纯语言和大多数函数式语言都具有这种数据结构，它不是 F#-ism。）

另请参阅

http ://diditwith.net/2008/03/03/WhyILoveFListsTheBasics.aspx

其中有很好的图表来解释事情（例如为什么前面的 consing 是比最后的不可变列表便宜）。

回复收藏 0 原文

千里故人稀 2024-12-16 06:15:34

除了其他人所说的之外：如果您需要高效但不可变的数据结构（这应该是惯用的 F# 方式），您必须考虑阅读 Chris Okasaki，纯函数式数据结构。还有一篇论文（本书基于该论文））。

回复收藏 0 原文

梦冥 2024-12-16 06:15:34

除了已经说过的内容之外，函数式编程简介部分MSDN 上有一篇关于使用功能列表解释了列表如何工作并在 C# 中实现它们，因此这可能是理解它们如何工作的好方法（以及为什么添加对最后一个元素的引用将不允许有效地实现追加）。

如果您需要将内容附加到列表的末尾以及前面，那么您需要不同的数据结构。例如，Norman Ramsey 发布了 DList 的源代码，其中包含这些

回复收藏 0 原文

奈何桥上唱咆哮 2024-12-16 06:15:34

如果您发现需要一个具有更好的追加操作性能的列表，请查看 QueueList 和 JoinList 中FSharpx 扩展库。

QueueList 封装了两个列表。当您使用 cons 添加前缀时，它会在第一个列表中添加一个元素，就像 cons 列表一样。但是，如果您想追加单个元素，可以将其推到第二个列表的顶部。当第一个列表用完元素时，List.rev 会在第二个列表上运行，并且两个列表会交换，将列表按顺序放回原处，并释放第二个列表以追加新元素。

JoinList 使用可区分联合来更有效地附加整个列表，并且涉及更多一些。

对于标准 cons-list 操作来说，两者的性能显然较差，但对于其他场景来说，性能更好。

您可以在文章重构模式中阅读有关这些结构的更多信息匹配。

回复收藏 0 原文

江南烟雨〆相思醉 2024-12-16 06:15:34

正如其他人指出的那样，F# 列表可以由数据结构表示：

List<T> { T Value; List<T> Tail; }

从这里开始，约定是列表从您引用的 List 开始，直到 Tail > 为空。根据该定义，其他答案中的优点/功能/限制就自然而然了。

但是，您最初的问题似乎是为什么列表的定义更像是：

List<T> { Node<T> Head; Node<T> Tail; }
Node<T> { T Value; Node<T> Next; }

这样的结构将允许附加和前置到列表，而不会对原始列表的引用产生任何明显的影响，因为它仍然只看到一个“窗口” ”现已扩展的列表。尽管这（有时）允许 O(1) 串联，但此类功能会面临几个问题：

串联只能工作一次。这可能会导致意外的性能行为，其中一个串联的复杂度为 O(1)，但下一个串联的复杂度为 O(n)。举例来说：
```
 listA = makeList1 ()
 列表 B = makeList2 ()
 listC = makeList3 ()
 listD = listA + listB //修改A尾部的节点，时间复杂度为O(1)
 listE = listA + listC //现在必须复制A以与C连接
```
您可能会说，在可能的情况下节省时间是值得的，但令人惊讶的是不知道何时会是 O(1) 以及何时 O(n) 是反对该功能的有力论据。
现在，所有列表都会占用两倍的空间，即使您从未打算将它们连接起来。
您现在有一个单独的列表和节点类型。在当前的实现中，我相信 F# 仅使用单一类型，就像我的答案开头一样。可能有一种方法可以只用一种类型来完成您所建议的操作，但这对我来说并不明显。
连接需要改变原始的“尾部”节点实例。虽然这不应该影响程序，但它是一个突变点，大多数函数式语言都倾向于避免。

As others have pointed out, an F# list could be represented by a data structure:

List<T> { T Value; List<T> Tail; }

From here, the convention is that a list goes from the List you have a reference to until Tail is null. Based on that definition, the benefits/features/limitations in the other answers come naturally.

However, your original question seems to be why the list is not defined more like:

List<T> { Node<T> Head; Node<T> Tail; }
Node<T> { T Value; Node<T> Next; }

Such a structure would allow both appending and prepending to the list without any visible effects to the a reference to the original list, since it still only sees a "window" of the now expanded list. Although this would (sometimes) allow O(1) concatenation, there are several issues such a feature would face:

The concatenation only works once. This can lead to unexpected performance behavior where one concatenation is O(1), but the next is O(n). Say for example:
```
 listA = makeList1 ()
 listB = makeList2 ()
 listC = makeList3 ()
 listD = listA + listB //modified Node at tail of A for O(1)
 listE = listA + listC //must now make copy of A to concat with C
```
You could argue that the time savings for the cases where possible are worth it, but the surprise of not knowing when it will be O(1) and when O(n) are strong arguments against the feature.
All lists now take up twice as much space, even if you never plan to concatenate them.
You now have a separate List and Node type. In the current implementation, I believe F# only uses a single type like the beginning of my answer. There may be a way to do what you are suggesting with only one type, but it is not obvious to me.
The concatenation requires mutating the original "tail" node instance. While this shouldn't affect programs, it is a point of mutation, which most functional languages tend to avoid.

回复收藏 0 原文