scala - 非持久性数据结构可以以纯函数方式使用吗？

Question

这是一个关于函数式编程的一般问题，但我也对它在特定语言中的答案很感兴趣。

我对函数式语言只有初学者的了解，所以请耐心等待。

我的理解是，与命令式语言相比，函数式语言侧重于不同的数据结构，因为它们喜欢不变性:持久性数据结构。

例如，它们都有一个不可变列表概念，您可以在其中形成一个新列表 x :: l和 y :: l来自现有列表 l和两个新项目x和 y没有 l 的所有元素需要复制。这可能是由新列表对象在内部将旧列表对象作为尾部来实现的。

在命令式语言中，很少使用这样的数据结构，因为它们不像 c 样式数组那样提供良好的引用局部性。

一般来说，寻找支持函数式风格的数据结构是它自己的一项努力，所以如果人们不必总是这样做就好了。

现在这里有一个想法，如果有正确的语言支持，如何在函数式编程中使用所有经典数据结构。

通常，命令式语言中的数据结构具有在其上定义的修改操作(以伪代码形式):

data.modify(someArgument)

写这个的功能方式是

newData = modified(data, someArgument)

一般的问题是这通常需要复制数据结构 - 除非语言可以知道 data实际上不会被其他任何东西使用:那么，修改可以以变异原始的形式进行，没有人能分辨出区别。

在一大类情况下，语言可以推断出“从未在其他地方使用过”的属性:当 modified 的第一个参数时是一个未绑定(bind)的值，如本例所示:

newData = modified(modified(data, someArgument))

在这里， data可以在别处使用，但 modified(data, someArgument)显然不是。

这就是在 C++ 中被称为“右值”的东西，而在 C++ 的最新版本中，讽刺的是，它根本没有任何功能，否则可以重载这样的右值。

例如，可以这样写:

Data modified(Data const& data) { // returns a modified copy }
Data modified(Data && data) { // returns the modified original }

这意味着在 C++ 中，人们实际上可以采用任何可变的高效数据结构并将其转换为具有不可变的 api，该 api 可以像命令式版本一样高效地以纯函数方式使用。

(需要注意的是，在 C++ 中，有时仍然需要强制转换来强制右值重载。当然，在实现此类数据结构时需要小心，即在使用右值重载时。不过这可能会得到改进。)

现在我的问题:

实际的函数式语言有类似的机制吗？或者这不是出于其他原因所必需的吗？

(我标记了一些我特别感兴趣的特定语言。)

Answer 1

确实，持久数据结构比可变数据结构慢。对此没有任何争议。有时差异可以忽略不计(迭代链表与数组)，有时差异可能很大(反向迭代)，但这不是重点。选择使用不可变数据是(或应该是)有意识的:我们用性能换取稳定性。

考虑这一点:对于大多数(不是全部)现代程序，本地性能不是问题。对于今天的程序，真正的性能瓶颈在于并行化——无论是在共享内存的本地机器上，还是在不同机器上。考虑到我们现在处理的数据量，从内存局部性和分支预测中挤出最后一点并不会减少它。我们需要规模。猜猜并行程序中 bug 的第一大来源是什么？没错——突变。

现代程序的另一个大问题是稳定性。程序可能会在您身上崩溃的日子已经一去不复返了，您只需重新启动它并继续工作。今天的程序需要在无外设的服务器上运行数月或数年，完全不需要人工干预。今天的程序不能只是放弃它的数字武器并期望人类找出问题所在。在这种情况下，本地性能远不如稳定性和并行化重要:购买(或租用)另外 10 台服务器比雇人时不时地重新启动程序要便宜得多。

确实可以使用变异来制作可并行化且稳定的程序。理论上是可以的。只是更难了。对于不可变数据，您必须首先真正瞄准您的脚。

然后，这里有一些观点:我们已经在那里了。您多久使用一次 goto您的代码中的说明？你考虑过这是为什么吗？您可以使用 goto 做出各种巧妙的表演技巧。 ，但我们选择不这样做。在编程历史的某个时刻，我们决定 goto麻烦多于值得。原始指针也发生了同样的事情:许多语言根本没有它们，其他语言对它们进行了严密保护，即使在那些可以不受限制地访问原始指针的语言中，现在使用它们也被认为是一种糟糕的形式。今天，我们正处于下一阶段的中间:首先我们放弃了goto ，然后我们放弃了原始指针，现在我们正在慢慢放弃变异。

然而，如果你真的发现自己出于正当理由插入了本地性能的极限，并且你已经确定不可变数据确实是瓶颈(记住:首先测量，然后优化)，那么大多数函数式语言(Haskell 和 Elm 除外)会让你逃脱突变，尽管不情愿。就像 C# 中的原始指针一样，您可以进行突变，您只需要对其进行明确(并小心)即可。例如，在 F# 中，您可以拥有可变变量、原始数组、可变记录、类、接口(interface)等。这是可能的，只是不推荐。到目前为止的普遍共识是，只要是局部的(即不会泄漏到外部)，就可以使用突变，并且你真的知道你在做什么，你已经记录了它，并对其进行了彻底的测试.

一个常见的情况是“值(value)构造”，其中您有一个最终产生不可变值的函数，但在执行此操作时会做各种困惑的事情。一个例子是 F# 核心库如何实现 List.map : 通常，因为列表是从前到后迭代的，但是是从后到前构建的，所以需要先通过迭代来构建转换后的列表，然后将其反转。因此，F# 编译器在此处作弊并在构建列表时对其进行变异，以避免额外的反转。

关于“局部性”问题的另一个说明。还记得我是怎么说的，你可以用 goto 做各种巧妙的性能技巧。 ?嗯，这已经不完全正确了。由于程序员开始编写程序时没有 goto ，二进制代码变得更加可预测，因为跳转现在由编译器生成，而不是由人类编码。这使得 CPU 可以很好地预测它们，并根据这些预测优化处理。最终结果是，现在您实际上可能会因不加选择地使用 goto 而获得更差的性能。而不是使用公认的更高级别的工具，如循环。过去，CPU 不能这么智能，因此选择不使用 goto纯粹是一种稳定性措施。但现在结果证明它实际上对性能有帮助，谁会想到呢？

我认为不变性也会发生同样的事情。我不确定它会如何发生，但我确信它会发生。即使在今天，没有特殊的硬件，仍然可以在编译时做一些优化:例如，如果编译器知道一个变量是不可变的，它可能会决定将它缓存在一个寄存器中很长一段时间，甚至提升它到一个常数。确实，当今大多数实际编译器并未执行所有这些可能的优化(尽管它们确实执行了一些)，但它们会。我们才刚刚开始。 :-)