似乎是类型的功能列表
"a*a"节点|无
在大多数情况下，O（n）的运行时间比面向对象的O（1）差，例如enqueue——函数实现必须非尾递归循环到最后，而面向对象的实现只能使last.next=new和last=new。这些列表是否有一个干净的功能实现，没有这个问题？如果没有，是否实际使用了功能列表？为什么？
感谢
单链表是函数式语言中最重要和最主要的数据结构。haskell、Common Lisp、Scheme等都严重依赖于它
函数链表比你想象的要糟糕得多——添加到尾部意味着复制参数链表的每一段，并使最后创建的段指向具有新值的新节点，因为你不能改变参数。
在Lazy语言中，这是可以做到的，但由于它是懒惰的，所以在使用它之前，不会真正创建任何东西。它不会破坏堆栈，优化非常智能。（例如Haskell）
在Scheme等热切的语言中，通常要么从头到尾构建一个列表，要么在最后反转列表。那么它将是O(n)。通常，如果你已经创建了列表中的所有节点来节省内存，你可以线性反转列表，它会像你没有这样工作。CCD_ 2和CCD_。在Common LISP中，你可以在代码中做同样的事情，并说它是功能性的，只要它从相同的参数中计算出相同的值，并且永远不会改变实际的参数本身。一些实现，如Racket，依赖于不可变列表，因此可以存储有关它们的信息，以提高速度。例如，list?需要检查最后一个CON，以检查()是否为#t，但它似乎会记住结果。如果列表是可变的，就无法做到这一点。
能够变异某些东西与OO无关。您可以在Scheme和Common Lisp中实现这一点，因为它们是多范式语言，而不是纯粹的函数语言。
以下是在具有单链表（cons）的Scheme中通过在添加（不起作用）时改变尾部来实现的队列：
#!r6rs
(import (rnrs)
(rnrs mutable-pairs))
(define (queue-make)
(let ((q (list 'head)))
(set-car! q q)
q))
(define (queue-empty? q)
(and (pair? q)
(null? (cdr q))))
(define (queue-push! q v)
(let ((tmp (car q))
(vc (cons v '())))
(set-cdr! tmp vc)
(set-car! q vc)))
(define (queue-pop! q)
(if (null? (cdr q))
(error 'queue-empty "Empty queue") ; empty
(let ((v (cadr q)))
(set-cdr! q (cddr q))
v)))
(define q (queue-make))
(queue-push! q 1)
(queue-push! q 2)
(queue-push! q 3)
(queue-pop! q) ; ==> 1
(queue-pop! q) ; ==> 2
(queue-pop! q) ; ==> 3
(queue-pop! q) ; ==> throws queue-empty: Empty queue
如果没有，功能列表是否实际使用？为什么
考虑到您对频繁修改的数据结构感兴趣，我能看到的关于持久（链接）列表的唯一用例是作为实现堆栈数据结构的基础。
push操作在列表的前面添加一个新值（即，它创建一个新的列表元素并重用先前存在的列表的其余部分）peek或top操作返回列表中的第一个值pop操作返回在第一个元素之后开始的列表
您定义的列表作为堆栈数据结构工作得很好，因为所有修改都发生在理想的位置，添加或删除新元素时，您不必重新生成现有列表的任何部分。堆栈通常不需要按照添加顺序（从后到前）对其所有元素进行迭代/遍历。
除此之外，AFAIK列表是一个不太理想的数据结构，因为当你想在它前面以外的任何地方编辑它时，你必须重建所有元素，直到发生更改的地方。最糟糕的情况是在列表的"末尾"添加一个元素。这就是为什么基于树的结构更适合作为持久（"不可变"）数据结构的基础：它们可以重用更多的现有节点，而通常，只有位于应该发生某些更改的节点路径上的节点才能被替换。（"更改"=从未更改的原始数据结构中派生出一个新的、不同的数据结构。）
如果你不需要经常修改你的列表，而且你主要是按顺序（而不是按随机顺序）阅读它的元素，那么它可能也就足够了。一个优点是，与更复杂的结构（如树）相比，它的内存开销非常小。
Node of 'a * 'a node | Nil[…]是否有这些列表的干净功能实现不存在此问题
显然不是，如果你对"列表"的定义就是你给出的。但同样（这可能是一个有点天真的建议），你可以在某种自我平衡的二叉树的基础上实现一个"列表"：
- 遍历该"列表"中的所有元素意味着按左子节点优先、父节点优先、右子节点优先的顺序遍历树
- 在列表末尾追加将意味着在最右边的叶节点处进行更改；您只需要重建从根节点到最右侧叶节点的路径，其他所有内容都可以重用
- 树越不深，在修改树时可能需要更改的元素就越少。因此，我建议使用自平衡二叉树
但是，再说一遍，我不是专家，我的建议可能很天真。有关功能数据结构的深入处理，请查看下面引用的资源。
进一步阅读：
- Chris Okasaki（1996），纯函数数据结构
- 它所基于的论文（可在线获取PDF格式）
- 关于计算机科学SE的问题，"自Okasaki以来，纯函数数据结构有什么新内容？"
在大多数情况下，O（n）的运行时间比面向对象的对应对象O（1）的运行时间差
这与面向对象无关。除非保留了指针，否则任何链接结构都将在尾部附加O（N）。是的，很多语言实际上都使用链表。
更新：此外，指针与对象方向无关。