SML 是否为非常大的集合提供了高效的不可变列表实现，或者应该使用数组和突变来进行此优化？

Question

每次我们对列表进行 cons 和解构以及类似的操作时，我们都会创建原始列表的副本。对于非常大的集合，这可能会成为性能问题。

据我了解，为了改善这种情况，一些编程语言将列表实现为可以更有效地复制的数据结构。SML中有类似的东西吗？也许在语言定义中，或者作为依赖于实现的功能？

如果没有这样的数据结构，数组和可变性是在大型列表上优化的一种模式吗？只要状态对于函数来说是局部的，函数仍然可以被认为是纯函数吗？

SML 是多范式的，但惯用的 SML 也是功能优先的，因此“具有高效复制的列表”和“可变数组”方法都应该有意义，具体取决于核心语言提供的功能。

对于非常大的集合，是否存在比普通单链表更有效的不可变数据结构？如果没有，是否有一个原生的纯函数式数据结构可以优化这个场景？或者应该在内部使用可变性和数组？

Answer 1

\n

SML中有类似的东西吗？也许在语言定义中，或者作为依赖于实现的功能？

\n

\n

这里有几个选择，具体取决于您愿意依赖什么。

\n

定义提供的“初始基础”不提供类似的内容（我认为实现可以通过给予列表一些特殊的编译器处理并将它们实现为写时复制数组或类似的方式来优化列表，但我'我不知道有这样的实现）。

\n

广泛实施的（SML/NJ、MLton、MoscowML、SML#、Poly/ML）SML 基础库提供了功能性和可变选项。我想到的是\'a\xc2\xa0Vector.vector和\'a\xc2\xa0Array.array（分别是不可变的和可变的）。SML/NJ 有一个文字扩展vector，例如 as #\xe2\x80\x8d[1,\xc2\xa02,\xc2\xa03]，我相信 MLton 在选择加入的基础上支持这一点。

\n

还有一些其他库，例如CMLib，它们提供其他不可变的数据结构（例如，strings）

\n

@molbdnilo 上面评论了 Okasaki 的纯函数式数据结构。我只读过他的论文，而不是书本版本（我相信书本有额外的材料，尽管我不知道到什么程度；似乎这已经出现在软件工程堆栈交换上）。我不知道他在那里提供的数据结构的任何预打包版本。

\n

\n

只要状态对于函数来说是局部的，函数仍然可以被认为是纯函数吗？

\n

\n

这显然在某种程度上取决于您对纯函数的定义。我听说过使用私有状态的函数“观察纯”，这似乎足够广泛，至少被一些相关论文使用（例如，https://doi.org/10.1016/j ） .tcs.2007.02.004 )

\n

\n

对于非常大的集合，是否存在比普通单链表更有效的不可变数据结构？或者应该在内部使用可变性和数组？

\n

\n

我认为上面提到的向量是你想要的（我想这取决于“非常大”有多大），但显然可能存在更好的选择，取决于使用。例如，如果插入和删除比随机访问更重要，那么可能有更好的选择。

\n

根据您的工作负载，可变性也可能更有意义，例如，如果随机访问很重要，您正在执行许多更新，并且需要良好的内存局部性。

\n