每次我们对列表进行 cons 和解构以及类似操作时，我们都会创建原始列表的副本。对于非常大的集合，这可能会成为性能问题。
据我了解，为了改善这种情况，一些编程语言将列表实现为可以更有效地复制的数据结构。 SML中有这样的东西吗？也许在语言定义中，或者作为一个依赖于实现的特性？
如果没有这样的数据结构，数组和可变性是否是一种在大型列表上优化的模式？只要状态对函数而言是局部的，函数还能被认为是纯函数吗？
SML 是多范式，但惯用的 SML 也是功能优先的，因此“高效复制列表”和“可变数组”方法都应该有意义，具体取决于核心语言提供的内容。
对于非常大的集合，是否有一种比普通单链表更有效的不可变数据结构？如果没有，有没有原生的纯函数式数据结构可以优化这个场景？还是应该在内部使用可变性和数组？
最佳答案
Is there something like this in SML? Perhaps in the language definition, or as a feature that is implementation dependent?
这里有几个选项，具体取决于您愿意依赖什么。
the definition提供的“初始基础”不提供类似的东西(我想一个实现可以通过给它们一些特殊的编译器处理并将它们实现为写时复制数组或类似的东西来优化列表，但我不知道一个实现)。
广泛实现的(SML/NJ、MLton、MoscowML、SML#、Poly/ML)SML 基础库提供功能性和可变性选项。我想到的是 'a Vector.vector和 'a Array.array (不可变和可变，分别)。 SML/NJ 有一个 vector 文字的扩展，例如作为 #[1, 2, 3]，我相信 MLton 在选择加入的基础上支持这一点。
还有一些其他的库，比如CMLib ，它提供其他不可变数据结构(例如，sequences)
@molbdnilo 在上面评论了 Okasaki 的纯函数式数据结构。我只读过他的 thesis , 而不是书籍版本(我相信它有额外的 Material ，虽然我不知道到什么程度；似乎是 this has come up on on software engineering stack exchange )。我不知道他在那里展示的数据结构有任何预打包版本。
As long as the state is local to the function, can the function still be considered pure?
这显然在某种程度上取决于您对纯函数的定义。对于使用私有(private)状态的函数，我听说过“观察纯”的说法，这似乎足够普遍，至少有一些相关论文(例如 https://doi.org/10.1016/j.tcs.2007.02.004)使用了它
Is there an immutable data structure that is more efficient than the normal singly linked list for very large collections? Or should mutability and arrays be used internally?
我认为上面提到的向量是您想要的(我想这取决于“非常大”的大小)，但显然可能存在更好的选择，具体取决于使用情况。例如，如果插入和删除比随机访问更重要，那么可能会有更好的选择。
根据您的工作负载，可变性也可能更有意义，例如，如果随机访问很重要，您正在进行很多更新，并且需要良好的内存局部性。
关于list - SML 是否为非常大的集合提供了一个有效的不可变列表实现，或者应该使用数组和变异来进行这种优化？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/72682884/