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

有大量关于数据结构的文本和数据结构代码库。我知道纯粹的功能数据结构更容易推理。但是，我很难理解在实用代码中使用纯函数式数据结构（使用函数式编程语言与否）的命令对应的真实世界优势。有人可以提供一些真实世界的案例，其中纯功能数据结构具有优势，为什么？这个例子就像我在programming_language中使用data_structure_name来做应用程序，因为它可以做某些事情。谢谢。 PS：我的意思是纯功能数据结构与持久数据结构不同。持久性数据结构是一种不会改变的数据结构。另一方面，纯功能数据结构是纯粹运行的数据结构。

已邀请:

5 个回复

蜗仓馈

纯功能（也称为持久性或不可变）数据结构具有以下几个优点：你永远不必锁定它们，这极大地提高了并发性。他们可以共享结构，从而减少内存使用量。例如，考虑Haskell中的列表[1,2,3,4]和Java等命令式语言。要在Haskell中生成新列表，您只需创建新的cons（值对和引用到下一个元素）并将其连接到上一个列表。在Java中，您必须创建全新的列表，以免损坏前一个列表。你可以使持久数据结构变得懒惰。另外，如果使用功能样式，则可以避免考虑操作的时间和顺序，从而使程序更具说明性。事实上，数据结构是不可变的，允许您做出一些更多的假设，从而扩展语言的功能。例如，Clojure使用不变性的事实来正确地为每个对象提供hashCode（）方法的实现，因此任何对象都可以用作映射中的键。使用不可变数据和功能样式，您还可以自由使用memoization。一般来说，它还有更多的优点，它是对现实世界进行建模的另一种方式。来自SICP的这一章和其他章节将为您提供更准确的不可变结构编程视图，优缺点。

好按紊叉

除了共享内存安全性之外，大多数纯函数数据结构还可以为您提供持久性，实际上是免费的。例如，假设我在OCaml中有一个set，我想为它添加一些新值我可以这样做：

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在添加新字符后保持不变（它只包含广告），而b包含啊，并且它们共享一些相同的内存（有一个set，因为它是一个AVL树而且分享了多少内存是很棘手的树的形状变化）。我可以继续这样做，跟踪我对树所做的所有更改，让我回到以前的状态。这是维基百科关于Purely Functional的文章中的一个很好的图表，它显示了将字符'e'插入二叉树的结果xs：

款去芳尾脊

Erlang程序几乎完全使用纯粹的功能数据结构，并且通过几乎无缝扩展到多个内核，它们获得了巨大的好处。由于永远不会修改共享数据（主要是二进制文件和位字符串），因此无需锁定此类数据。

迪擅哨乘傅

拿这个F＃的小片段：

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

您可以100％确定地说这是整数1到5的不可变列表。您可以传递对该列表的引用，并且永远不必担心列表可能已被修改。这足以让我使用它。

旗低饶彤

纯功能数据结构具有以下优点：持久性：旧版本可以安全地重复使用，因为它们不能被更改。共享：许多版本的数据结构可以同时保存，只需要适度的内存要求。线程安全：任何突变都隐藏在懒惰的thunk（如果有的话）中，因此由语言实现处理。简单性：不必跟踪状态变化，使纯粹的功能数据结构更易于使用，特别是在并发环境中。增量：纯功能数据结构由许多微小部分组成，使其成为增量垃圾收集的理想选择，从而降低延迟。请注意，我没有将并行性列为纯功能数据结构的优势，因为我不相信这种情况。高效的多核并行性需要可预测的局部性，以便利用高速缓存并避免在对主存储器的共享访问上遇到瓶颈，并且纯功能数据结构在这方面充其量具有未知特性。因此，许多使用纯功能数据结构的程序在多核上并行化时不能很好地扩展，因为它们将所有时间都花在缓存未命中，争夺共享内存路径。我所说的纯功能数据结构与持久数据结构不同。这里有一些混乱。在纯功能数据结构的上下文中，持久性是一个术语，用于指代在知道它们仍然有效的情况下引用回安全数据结构的先前版本的能力。这是纯功能的自然结果，因此，持久性是所有纯功能数据结构的固有特征。

要回复问题请先登录或注册

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

5 个回复

发起人

purely_functional

问题状态

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

与内容相关的链接

5 个回复

发起人

purely_functional

问题状态