纯粹的功能数据结构有什么好处？

Question

数据结构和数据结构库中有大量文本。我知道纯粹的功能数据结构更容易推理。但是，我很难理解在命令式对应方面使用纯粹的功能数据结构（使用功能编程语言）中纯粹的功能数据结构的现实优势。有人可以提供一些现实世界的情况，纯粹的功能数据结构具有优势，为什么？

沿线的示例就像我使用 data_structure_name 在 编程_language 去做 应用 因为它可以做 whith.

谢谢。

PS：我所说的纯粹功能数据结构与持续数据结构不同。持续数据结构是一种不变的数据结构？另一方面，纯粹的功能数据结构是纯粹运行的数据结构。

Answer 1

纯粹的功能性（又称持续或不可变的）数据结构为您提供了几个优点：

• 您永远不必锁定它们，这极为改进 并发.
• 他们可以共享结构， 减少内存使用量. 。例如，在Haskell中考虑列表[1、2、3、4]，以及Java等命令式语言。要在Haskell中产生新列表，您只需要创建新的列表 cons （对值和参考对元素对），然后将其连接到上一个列表。在Java中，您必须创建全新的列表，以免损坏上一个列表。
• 您可以制作持久的数据结构 懒惰的.
• 另外，如果您使用功能风格，则可以 避免考虑时间和操作顺序, ，因此，使您的程序更多 声明性.
• 事实，数据结构是不可变的，允许您做出更多的假设，因此 扩展语言的能力. 。例如， 克洛杰尔 使用不变性的事实正确地提供了每个对象上的HashCode（）方法的实现，因此任何对象都可以用作地图中的键。
• 有了不变的数据和功能风格，您也可以自由使用 记忆.

总的来说，这是建模现实世界的另一种方法。 这个 SICP的其他一些章节将使您更准确地使用不变的结构，其优势和缺点。

Answer 2

除了共享记忆安全外，最纯粹的功能数据结构也为您提供 持久性, ，实际上是免费的。例如，假设我有一个 set 在OCAML中，我想为此添加一些新值，我可以做到这一点：

module CharSet = Set.Make(Char)
let a = List.fold_right CharSet.add ['a';'b';'c';'d'] CharSet.empty in
let b = List.fold_right CharSet.add ['e';'f';'g';'h'] a in
...

a 遗迹 未修改 添加新字符（仅包含AD）后， b 包含ah，它们共享一些相同的内存（与 set 判断共享多少内存是有点棘手的，因为它是AVL树，而树的形状会发生变化）。我可以继续这样做，跟踪我对树的所有更改，使我可以回到以前的状态。

这是来自 Wikipedia关于纯粹功能的文章 这显示了将字符“ e”插入二进制树的结果 xs:

Answer 3

Erlang程序几乎完全使用纯粹的功能数据结构，它们通过将几乎无缝地扩展到多个内核来获得可观的好处。由于共享数据（主要是二进制文件和位字符串）从未经过修改，因此从来没有需要锁定此类数据。

Answer 4

拿F＃的这个小片段：

let numbers = [1; 2; 3; 4; 5]

您可以100％确定地说，这是整数1到5的不可变列表。您可以通过对该列表的参考进行传递，而不必担心该列表可能已被修改。这是我使用它的足够理由。

Answer 5

纯粹的功能数据结构具有以下优点：

• 持久性：可以将旧版本重复使用，因为他们知道它们无法更改。

• 共享：数据结构的许多版本只能同时保留，只有适度的内存要求。

• 线程安全：任何突变都隐藏在懒惰的thunk中（如果有），因此由语言实现处理。

• 简单性：不必跟踪状态变化使纯粹使用功能性数据结构更容易使用，尤其是在并发的背景下。

• 增量：纯粹的功能数据结构由许多微小的零件组成，使其非常适合递增垃圾收集，从而导致较低的潜伏期。

请注意，我尚未将并行性作为纯粹功能数据结构的优势，因为我不认为是这种情况。有效的多核算并行性需要可预测的位置，以利用缓存并避免在共享对主内存的共享访问中瓶颈，并且纯粹的功能数据结构充其量在这方面具有未知特征。因此，许多使用纯粹功能数据结构的程序在多核算上并行时并不那么扩展，因为它们将所有时间都花在缓存失误中，争夺共享内存路径。

我所说的纯粹功能数据结构与持续数据结构不同。

这里有一些混乱。在纯粹的功能数据结构的背景下，持久性是一个术语，用于指代数据结构的先前版本的能力，因为他们知道它们仍然有效。这是纯粹功能性的自然结果，因此，持久性是所有纯粹功能数据结构的固有特征。