use*_*261 5 functional-programming list
我注意到在Haskell和OCaml等函数式语言中,您可以使用列表执行2个操作.首先你可以做x:xsx是元素的地方ans xs是一个列表,结果是我们得到一个新的列表,其中x在常量时间附加到xs的开头.第二个是x++yx和y都是列表,结果是我们得到一个新的列表,其中y在线性时间内相对于x中元素的数量附加到x的末尾.现在我不是语言设计和编译器的专家,但在我看来,这很像一个链接列表的简单实现,其中一个指针指向第一个项目.如果我用C++这样的语言实现这个数据结构,我会发现添加一个指向最后一个元素的指针通常是微不足道的.在这种情况下,如果以这种方式实现这些语言(假设它们确实使用了所描述的链接列表),则向最后一项添加"指针"将使得将项添加到列表末尾并且允许模式匹配更有效.最后一个元素.
我的问题是这些数据结构是否真的实现为链表,如果是这样,为什么他们不添加对最后一个元素的引用？
Nor*_*sey 11
是的,它们确实是链表.但它们是不可改变的.不变性的优点是您不必担心还有谁有指向同一列表的指针. 您可以选择编写x++y,但程序中的其他位置可能依赖于x保持不变.
在这些语言的编译器上工作的人(我是其中之一)并不担心这个成本,因为有很多其他数据结构可以提供高效的访问:
表示为两个列表的功能队列提供到两端恒定时访问和分期常量时间put和get操作.
像手指树这样更复杂的数据结构可以以非常低的成本提供多种列表访问.
如果你只是想要恒定时间附加,John Hughes开发了一个优秀,简单的列表表示为函数,它提供了这一点.(在Haskell库中,它们被称为DList.)
如果您对这些问题感兴趣,可以从Chris Okasaki的书" Purely Functional Data Structures"和Ralf Hinze的一些不那么令人生畏的论文中获得很好的信息.