我知道在惰性函数语言中，链接列表采用生成器式语义，并且在优化编译器下，当它们实际上不用于存储时，它们的开销可以被完全删除。
但是在急剧的功能语言中，它们的使用似乎并不那么重，而优化它们似乎更加困难。有一个很好的性能原因，像Scheme这样的语言使用平面数组作为它们的主要序列表示吗？
我知道使用单链表时明显的时间复杂性影响;我更多地考虑使用热切单链表作为主要序列表示的实际性能结果，考虑编译器优化。
TL; DR：没有性能优势！
第一个Lisp将cons（链表单元格）作为唯一的数据结构，并将其用于所有内容。 Common Lisp和Scheme都有今天的向量，但是对于功能风格来说它并不是一个很好的匹配。链表可以有一个递归步骤在累加器前面添加零个或多个元素，最后你有一个在迭代之间共享的列表。该操作可能会进行多次递归，使得多个版本共享尾部。我想说共享是链表最重要的方面。如果您制作了一个minimax算法并将状态存储在链表中，则可以更改状态而无需复制状态的未更改部分。
C ++ Bjarne Stroustrup的创建者提到in a talk，即使按顺序插入并需要移动数据结构中的一半元素，使数据结构加扰并且像链表一样加倍的惩罚也很容易超出。请记住，这些是双重链接列表和突变插入，但他提到大多数时间是线性地跟踪指针，获取所有CPU缓存未命中，找到正确的点，因此对于排序中的每个O（n）搜索列出一个向量会更好。
如果你有一个程序，你在不在前面的列表上做了很多插入，那么树可能是更好的选择，你可以在CL和Scheme中使用cons。事实上，所有Chris Okasaki纯粹的功能数据结构都可以用cons实现。 Haskell中大多数“可变”结构的实现与它类似。
如果您在Scheme中遇到性能问题，并且在分析后发现您应该尝试使用数组替换链表操作，那么就没有任何阻碍。最后，所有算法选择都有利有弊。任何语言的硬计算都很难。