Functional data structures in C++
Asked Answered
N

2

23

Does anyone know of a C++ data structure library providing functional (a.k.a. immutable, or "persistent" in the FP sense) equivalents of the familiar STL structures?

By "functional" I mean that the objects themselves are immutable, while modifications to those objects return new objects sharing the same internals as the parent object where appropriate.

Ideally, such a library would resemble STL, and would work well with Boost.Phoenix (caveat- I haven't actually used Phoenix, but as far as I can tell it provides many algorithms but no data structures, unless a lazily-computed change to an existing data structure counts - does it?)

Nordic answered 3/5, 2010 at 10:3 Comment(5)
Could you not get roughly the required effect by passing and returning all objects by value?Attestation
Only if I could stand the performance and memory overhead. The trick with functional data structures is that they share internals wherever possible. This is safe to do because the objects are immutable, and is much less memory- and processor-hungry than just returning by value on large data structures.Nordic
I became genuinely interested in the same question while co-writing the experience report at portal.acm.org/citation.cfm?id=1596591 . My conclusion at the time was that you really need garbage-collection: the advantage of persistent structure is in sharing, but in the presence of sharing there is no longer clear ownership of any single node, so some sort of central authority (the GC) has to decide which nodes can be reclaimed. That, or it doesn't matter for your application that nodes are only allocated and never freed.Permutation
Of course you can have a more or less ad-hoc GC (reference counting, or a conservative GC such as Boehm's), but a language that was designed for the advantages and the disadvantages of memory management makes thing simpler and more effective.Permutation
@Pascal For many functional types, shared_ptr<>s would be fine to use without GC. The problem I've had is that many functional types make use of laziness and that can result in significant amounts of extra C++ code to represent thunks.Zachariahzacharias
C
4

I would look and see whether FC++ developed by Yannis Smaragdakis includes any data structures. Certainly this project more than any other is about supporting a functional style in C++.

Collete answered 3/5, 2010 at 13:31 Comment(1)
Looks like an interesting library, no recent activity though. There is a persistent list datatype in there, but it doesn't appear to be good for general use outside of FC++.Nordic
V
2

This is more of a heads up than a detailed answer, but Bartosz Milewski appears to have done a lot of work on this. See, for example:

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

Looks like he's implemented a lot of algorithms from Okasiki's book Purely Functional Data Structures here:

https://github.com/BartoszMilewski/Okasaki

N.B. I haven't tried these yet, but they're the first C++ persistent data structures I've seen outside of FC++.

Hopefully, I'll get to trying them soon.

Vanadinite answered 11/12, 2013 at 15:45 Comment(1)
They seem to be missing important parts... like deletionKamkama

© 2022 - 2024 — McMap. All rights reserved.