纯函数式数据结构的好处是什么？

Question

有大量关于数据结构的文本，以及数据结构的代码库。我知道纯函数式数据结构更容易理解。然而，我很难理解在实用代码中使用纯函数式数据结构(使用或不使用函数式编程语言)相对于命令式代码的实际优势。有人能提供一些纯函数式数据结构具有优势的真实案例吗?为什么？

类似于我在programming_language中使用data_structure_name来做certain_thing.这样的示例，因为它可以做应用程序

谢谢。

PS:我所说的纯函数式数据结构与持久化数据结构不同。持久数据结构是一种不会改变的数据结构？？另一方面，纯函数式数据结构是一种纯操作的数据结构。

Answer 1

纯函数式(也称为持久化或不可变)数据结构为您提供了几个优点：

共享你永远不需要锁定它们，这极大地改善了concurrency.

• they
• 结构，这减少了内存使用。例如，考虑Haskell中的列表1、2、3、4和一些命令式语言，如Java。要在Haskell中生成新的列表，您只需创建新的cons (一对值和对下一个元素的引用)，并将其连接到以前的列表。在Java中，你必须创建全新的list而不破坏原来的list。如果你使用函数式风格，你可以使持久化的数据结构.
• also，，你可以避免考虑操作的时间和顺序，这样，使你的程序更加declarative.
• fact，，即数据结构是不可变的，允许你做一些更多的假设，

扩展了的功能。例如，Clojure利用不变性这一事实在每个对象上正确地提供了hashCode()方法的实现，因此任何对象都可以用作映射中的键。具有不可变数据和函数式风格的

• 您也可以自由使用.

一般来说，它有更多的优点，它是另一种模拟现实世界的方式。This和来自SICP的其他一些章节将让你更准确地了解不可变结构的编程，以及它的优缺点。

Answer 2

除了共享内存安全之外，大多数纯函数数据结构还可以为您提供持久性，而且实际上是免费的。例如，假设我在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在添加新字符(它只包含a-d)后保持未修改的，而b包含a-h，它们共享一些相同的内存(对于set，由于它是一棵AVL树，并且树的形状会发生变化，所以很难判断共享了多少内存)。我可以继续这样做，跟踪我对树所做的所有更改，这样我就可以返回到以前的状态。

下面是一个很棒的Wikipedia article on Purely Functional图，它显示了在二叉树xs中插入字符'e‘的结果

​

​

Answer 3

Erlang程序几乎完全使用函数式数据结构，它们几乎可以无缝地扩展到多个内核，从而获得巨大的好处。由于共享数据(主要是二进制文件和位串)从不修改，因此永远不需要锁定此类数据。