61

有大量关于数据结构的文本，以及数据结构代码库。我知道纯函数式数据结构更容易推理。但是，我很难理解在实用代码中使用纯函数式数据结构（使用或不使用函数式编程语言）相对于命令式对应物的现实世界优势。有人可以提供一些纯函数式数据结构具有优势的真实案例吗？为什么？

像我使用data_structure_name in programming_language来做应用程序这样的例子，因为它可以做某些事情。

谢谢。

PS：我所说的纯函数式数据结构和持久化数据结构是不一样的。持久化数据结构是不会改变的数据结构？？另一方面，纯功能数据结构是一种纯粹操作的数据结构。

4

5 回答 5

74

纯功能（又名持久或不可变）数据结构为您提供了几个优势：

  • 您永远不必锁定它们，这极大地提高了并发性。
  • 它们可以共享结构，从而减少内存使用。例如，考虑 Haskell 中的 list [1, 2, 3, 4] 和一些命令式语言（如 Java）。要在 Haskell 中生成新列表，您只需创建新cons的（值对和对下一个元素的引用）并将其连接到上一个列表。在 Java 中，您必须创建全新的列表，以免损坏前一个列表。
  • 您可以使持久数据结构变得懒惰。
  • 此外，如果您使用函数式风格，您可以避免考虑时间和操作顺序，从而使您的程序更具声明性。
  • 事实上，数据结构是不可变的，允许你做更多的假设，从而扩展语言的能力。例如，Clojure使用不变性这一事实正确地为每个对象提供 hashCode() 方法的实现，因此任何对象都可以用作映射中的键。
  • 有了不可变的数据和函数式风格，你也可以自由地使用memoization。

还有更多的优点，一般来说，这是对现实世界进行建模的另一种方式。SICP 的这一章和其他一些章节将让您更准确地了解使用不可变结构进行编程及其优缺点。

于 2010-12-09T16:11:39.613 回答
25

除了共享内存安全之外，大多数纯函数数据结构还为您提供持久性，而且几乎是免费的。例如，假设我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 关于 Purely Functional 的文章中的一个很棒的图表，它显示了将字符“e”插入二叉树的结果xs：

替代文字

于 2010-12-09T16:18:23.487 回答
14

Erlang 程序几乎完全使用纯函数式数据结构，并且通过几乎无缝地扩展到多个内核，它们获得了巨大的好处。因为共享数据（主要是二进制文件和位串）永远不会被修改，所以永远不需要锁定这些数据。

于 2010-12-09T15:30:17.713 回答
10

纯函数式数据结构具有以下优点：

  • 持久性：旧版本可以安全地重复使用，因为它们知道它们不能被更改。

  • 共享：一个数据结构的多个版本可以同时保存，只需要适度的内存需求。

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

  • 简单性：不必跟踪状态变化使纯函数式数据结构更易于使用，尤其是在并发上下文中。

  • 增量：纯功能数据结构由许多微小的部分组成，使其成为增量垃圾收集的理想选择，从而降低延迟。

请注意，我没有将并行性列为纯函数式数据结构的优势，因为我认为情况并非如此。高效的多核并行性需要可预测的局部性，以利用缓存并避免在共享访问主内存时遇到瓶颈，而纯功能数据结构在这方面充其量具有未知特征。因此，许多使用纯函数式数据结构的程序在多核上并行化时不能很好地扩展，因为它们将所有时间都花在缓存未命中上，争夺共享内存路径。

我所说的纯函数式数据结构与持久性数据结构不同。

这里有些混乱。在纯功能数据结构的上下文中，持久性是一个术语，用于指代在知道它们仍然有效的情况下安全地引用数据结构的先前版本的能力。这是纯函数式的自然结果，因此，持久性是所有纯函数式数据结构的固有特征。

于 2010-12-25T22:45:33.290 回答
9

拿这个 F# 的小片​​段：

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

您可以 100% 肯定地说，这是一个从 1 到 5 的不可变整数列表。您可以传递对该列表的引用，而不必担心该列表可能已被修改。这足以让我使用它。

于 2010-12-09T15:37:29.553 回答