纯功能数据结构有什么好处？
leo*_*on 56 ocaml haskell functional-programming purely-functional data-structures
有大量关于数据结构的文本和数据结构代码库.我知道纯粹的功能数据结构更容易推理.但是,我很难理解在实用代码中使用纯函数式数据结构(使用函数式编程语言与否)的命令对应的真实世界优势.有人可以提供一些真实世界的案例,其中纯功能数据结构具有优势,为什么？
这个例子就像我在programming_language中使用data_structure_name来做应用程序,因为它可以做某些事情.
谢谢.
PS:我的意思是纯功能数据结构与持久数据结构不同.持久性数据结构是一种不会改变的数据结构.另一方面,纯功能数据结构是纯粹运行的数据结构.
ffr*_*end 71
纯功能(也称为持久性或不可变)数据结构具有以下几个优点:
- 你永远不必锁定它们,这极大地提高了并发性.
- 他们可以共享结构,从而减少内存使用量.例如,考虑Haskell中的列表[1,2,3,4]和Java等命令式语言.要在Haskell中生成新列表,您只需创建新的
cons(值对和引用到下一个元素)并将其连接到上一个列表.在Java中,您必须创建全新的列表,以免损坏前一个列表. - 你可以使持久数据结构变得懒惰.
- 另外,如果使用功能样式,则可以避免考虑操作的时间和顺序,从而使程序更具说明性.
- 事实上,数据结构是不可变的,允许您做出一些更多的假设,从而扩展语言的功能.例如,Clojure使用不变性的事实来正确地为每个对象提供hashCode()方法的实现,因此任何对象都可以用作映射中的键.
- 使用不可变数据和功能样式,您还可以自由使用memoization.
一般来说,它还有更多的优点,它是对现实世界进行建模的另一种方式.来自SICP的这一章和其他章节将为您提供更准确的不可变结构编程视图,优缺点.
- http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504(显然)也会很好地阅读这个主题. (9认同)
- @rks:看看[自冈崎以来纯粹的功能数据结构有什么新东西？](http://cstheory.stackexchange.com/q/1539/634),以补充这个伟大的,但现在有点过时的书. (3认同)
- @Carl 我发现您对无锁并发访问共享内存的影响非常乐观。我确信我可以区分一方面是一致的（已评估的或未评估的）表达式，另一方面是共享内存转换而不锁定从一个到另一个。 (2认同)
- @Pascal Cuoq:GHC存在.继续在并发评估thunk时找到一个不连贯的问题.如果你发现了一个真正的错误,我肯定会关注Simon Marlow.但我只是没有看到它发生.只要您的操作是纯粹的,就可以在运行时表示中做出许多非常谨慎的选择,以确保一致性.(如果你在unsafePerformIO方面做了一些事情,那么所有的赌注都会关闭.) (2认同)
Nik*_*chi 24
除了共享内存安全性之外,大多数纯函数数据结构还可以为您提供持久性,实际上是免费的.例如,假设我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在添加新字符(它只包含广告)之后保持未修改,同时b包含啊,并且它们共享一些相同的内存(set由于它是一个AVL树和形状,因此分辨内存是多么棘手树的变化).我可以继续这样做,跟踪我对树所做的所有更改,让我回到以前的状态.
这是维基百科关于Purely Functional的文章中的一个很好的图表,它显示了将字符'e'插入二叉树的结果xs:
Mar*_*tos 14
Erlang程序几乎完全使用纯粹的功能数据结构,并且通过几乎无缝扩展到多个内核,它们获得了巨大的好处.由于永远不会修改共享数据(主要是二进制文件和位字符串),因此无需锁定此类数据.
- Erlang从一个内核的绝对性能差到"n"内核的绝对性能不佳. (3认同)
- @Jon:首先,你的评论是一个全面的概括; Erlang在消息传递应用程序中表现非常出色,其中主要的工作负载是通信.其次,你的评论忽略了这一点.是的,Erlang是一种缓慢的语言,但它仍然可以从使用不可变数据类型中受益. (3认同)
拿这个F#的小片段:
let numbers = [1; 2; 3; 4; 5]
您可以100%确定地说这是整数1到5的不可变列表.您可以传递对该列表的引用,并且永远不必担心列表可能已被修改.这足以让我使用它.
纯功能数据结构具有以下优点:
持久性:旧版本可以安全地重复使用,因为它们不能被更改.
共享:许多版本的数据结构可以同时保存,只需要适度的内存要求.
线程安全:任何突变都隐藏在懒惰的thunk(如果有的话)中,因此由语言实现处理.
简单性:不必跟踪状态变化,使纯粹的功能数据结构更易于使用,特别是在并发环境中.
增量:纯功能数据结构由许多微小部分组成,使其成为增量垃圾收集的理想选择,从而降低延迟.
请注意,我没有将并行性列为纯功能数据结构的优势,因为我不相信这种情况.高效的多核并行性需要可预测的局部性,以便利用高速缓存并避免在对主存储器的共享访问上遇到瓶颈,而纯功能数据结构在这方面至多具有未知特性.因此,许多使用纯功能数据结构的程序在多核上并行化时不能很好地扩展,因为它们将所有时间都花在缓存未命中,争夺共享内存路径.
我所说的纯功能数据结构与持久数据结构不同.
这里有一些混乱.在纯功能数据结构的上下文中,持久性是一个术语,用于指代在知道它们仍然有效的情况下引用回安全数据结构的先前版本的能力.这是纯功能的自然结果,因此,持久性是所有纯功能数据结构的固有特征.