C++中的函数式数据结构

Question

有没有人知道一个C++数据结构库，提供了与熟悉的STL数据结构相对应的函数式（又称不可变的，在FP范畴中也称为“持久化”）结构？

所谓“函数式”，是指对象本身是不可变的，而对这些对象的修改会返回新的对象，这些新的对象在适当的情况下共享与父对象相同的内部。

理想情况下，这样的库将类似于STL，并且将与Boost.Phoenix很好地配合使用（注意：我实际上还没有使用过Phoenix，但据我所知，它提供了许多算法，但没有数据结构，除非对现有数据结构进行延迟计算的更改算作数据结构 - 是吗？）

- drg

---

你能否通过按值传递和返回所有对象来获得大致所需的效果？ - anon

只有在我能够容忍性能和内存开销的情况下才行。函数式数据结构的技巧在于尽可能共享内部内容。这样做是安全的，因为对象是不可变的，并且比在大型数据结构上仅通过值返回要少得多地占用内存和处理器资源。 - drg

在和他人合写 http://portal.acm.org/citation.cfm?id=1596591 经验报告时，我对同一个问题产生了真正的兴趣。当时我得出的结论是，确实需要垃圾回收：持久性结构的优势在于共享，但在存在共享的情况下，没有任何单个节点的明确所有权，因此某种形式的中央管理机构（GC）必须决定哪些节点可以被回收。要么对于应用程序而言，节点仅被分配但永远不会被释放是无关紧要的。 - Pascal Cuoq

当然，你可以拥有一个更或少是临时的GC（引用计数，或者像Boehm一样的保守GC），但是为了内存管理的优点和缺点而设计的语言会使事情变得更简单、更有效。 - Pascal Cuoq

对于许多函数类型来说，使用shared_ptr<>而不需要GC是可以的。我遇到的问题是，许多函数类型利用了惰性计算，这可能会导致大量额外的C++代码来表示thunks。 - sigfpe

Answer 1

我会查看并确定Yannis Smaragdakis开发的FC++是否包含任何数据结构。毫无疑问，这个项目比其他任何项目都更关注在C++中支持函数式编程风格。

- Norman Ramsey

---

看起来是一个有趣的库，不过最近好像没有更新了。里面有一个持久化列表数据类型，但似乎在FC++之外并不适用于一般用途。 - drg

Answer 2

这只是一个简单的提醒而不是详细的答案，但Bartosz Milewski似乎在这方面做了很多工作。例如：

http://bartoszmilewski.com/2013/11/13/functional-data-structures-in-c-lists/

看起来他在这里实现了Okasiki书中很多算法，纯函数数据结构:

https://github.com/BartoszMilewski/Okasaki

注意：我还没有尝试过这些，但它们是除FC++之外我看到的第一个C++持久化数据结构。

希望我能尽快尝试它们。

- TerrestrialIntelligence

---

他们似乎缺少重要的部分...比如删除。 - Michael