纯function数据结构的好处是什么?

数据结构上有大量文本,数据结构代码库也有。 我明白,纯粹的function数据结构更容易推理。 然而,我很难理解在实际代码中使用纯函数式数据结构(使用函数式编程语言还是不使用函数式编程语言)在命令式对象上的真实世界优势。 有人可以提供一些真正的世界情况下,纯function数据结构有优势,为什么?

像我在编程语言中使用data_structure_name来做应用程序,因为它可以做某些事情

谢谢。

PS:我的意思是纯数据结构和持久数据结构不一样。 持久的数据结构是一个不会改变的数据结构? 另一方面,纯function数据结构是纯粹操作的数据结构。

纯粹的function(即持久或不可变)数据结构给你几个优点:

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

总的来说,这是更多的优点,它是对现实世界进行build模的另一种方式。 SICP的这个和其他一些章节将给你更加准确的编程方式,以及不可变的结构,它的优点和缺点。

除了共享内存安全之外,大多数纯粹的function数据结构也给你持久性 ,而且实际上是免费的。 例如,假设我在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 ... 

添加新的字符(它只包含广告)后仍然未修改 ,而b包含啊,并且他们共享一些相同的内存(一个set有点棘手告诉多less内存共享,因为它是一个AVL树和树的形状改变)。 我可以继续这样做,跟踪我对树的所有改变,让我回到以前的状态。

下面是维基百科关于Purely Functional的文章中的一个很好的图表,显示了将字符'e'插入到二叉树xs

替代文字

Erlang程序几乎全部使用纯粹function性的数据结构,通过几乎无缝地缩放到多个内核,Erlang程序可以获得实质性的好处。 由于共享数据(主要是二进制文件和位串)永远不会被修改,所以永远不需要locking这些数据。

拿这个F#的小片段:

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

你可以100%确定地说,这是一个不可变的整数1到5的列表。你可以绕过对列表的引用,而不必担心列表可能被修改。 这是我使用它的足够理由。

纯function数据结构具有以下优点:

  • 持久性:旧版本可以被安全地重用,因为它们不可能被改变。

  • 共享:数据结构的许多版本可以同时保留,只有适度的内存要求。

  • 线程安全性:任何变异都隐藏在惰性内部(如果有的话),因此由语言实现来处理。

  • 简单性:不必跟踪状态变化,使得纯function数据结构更易于使用,特别是在并发环境中。

  • 增量性:纯粹的function性数据结构由许多微小的部分组成,因此非常适合增量垃圾收集,从而降低延迟。

请注意,我没有列出并行性作为纯粹function性数据结构的优点,因为我不相信这是事实。 高效的多核并行性需要可预测的局部性,以便利用高速caching并避免在共享对主内存的访问时遇到瓶颈,纯function数据结构在这方面充其量也是未知特性。 因此,许多使用纯function数据结构的程序在多核上并行化时不能很好地进行扩展,因为它们将所有时间花在caching未命中,争夺共享内存path。

纯粹function性数据结构的含义与持久性数据结构并不相同。

这里有一些混乱。 在纯粹function的数据结构的背景下,持久性是一个术语,指的是在知道这些数据结构仍然有效的情况下,能够引用数据结构以前版本的安全性。 这是纯粹function性的自然结果,因此,持久性是所有纯粹function性数据结构的固有特征。