为什么F#列表没有尾巴指针 [英] Why don't F# lists have a tail pointer

问题描述

或者用另一种方式来说，拥有一个仅包含一个头指针的基本单链接列表，您将获得什么好处?我可以看到尾巴指针的好处是:

Or phrased another way, what kind of benefits do you get from having a basic, singly linked list with only a head pointer? The benefits of a tail pointer that I can see are:

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

与O(n)列表串联(其中n是左侧列表的长度?)相反，这两种方法都比较方便.丢弃尾指针有什么好处?

Both of which are rather convenient things to have, as opposed to O(n) list concatenation (where n is the length of the left-side list?). What advantages does dropping the tail pointer have?

推荐答案

F#与许多其他功能性[-ish]语言一样，具有 cons-list (该术语最初来自LISP，但概念相同).在F#中，使用::运算符(或List.Cons)进行consing:请注意，签名为‘a –> ‘a list –> ‘a list(请参阅

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).

不要将cons-list与不透明的Linked List实现混淆，该实现包含一个离散的first [/last]节点- cons-list中的每个单元格都是[different]列表的开始！也就是说，列表"只是从给定的 cons-cell起始的单元链.

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.

以类似功能的方式使用时，这提供了一些优点:一个是所有"tail"单元都是共享的，并且由于每个cons单元都是不可变的(数据"可能是可变的，但这是一个不同的问题)无法更改"tail"单元格并弄乱包含该单元格的所有其他列表.

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.

由于此属性，可以通过 cons 放在最前面，从而高效地构建[新]列表(即，它们不需要副本).另外，将列表解构为head :: tail也是非常有效的-再次没有副本-在递归函数中通常非常有用.

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.

[标准可变] Double Linked List实现中通常不存在此不可变属性，因为附加将增加副作用:内部最后一个"节点(类型现在不透明)和一个尾"单元格被改变了. (有 个不可变的序列类型，它们允许有效地固定时间"附加/更新，例如

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.)

如上所述，cons-list不适用于所有任务也有缺点-特别是创建一个新列表，除非 cons 放在首位是O(n)操作，fsvo n，并且列表变的更好(或更糟).

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.

我建议创建您自己的concat版本，以了解此操作是如何完成的. (文章为什么我爱F#:列表-基础知识对此进行了说明.)

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.)

快乐的编码.

另请参阅相关文章:为什么只能放在功能语言列表的前面?

这篇关于为什么F#列表没有尾巴指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！