CODEWITHSUNDEEP
data-structuresfunctional-programmingsoft-heap
J D
J D

Reputation: 48687

Purely functional soft heap

Are there any implementations of a purely functional soft heap data structure in any language?

Upvotes: 16

Views: 1654

Answers (3)

shaunc
shaunc

Reputation: 5611

The Haim Kaplan, Robert E. Tarjan, Uri Zwick paper describes but doesn't fully analyze purely functional variant. It can be found at:

http://phdtree.org/pdf/44150182-soft-heaps-simplified/

Upvotes: 1

RudeDude
RudeDude

Reputation: 879

This project has Java code that might not be too terrible to translate to Scala... and then make it more functional.

https://github.com/lowasser/SoftSelect

But as noted previously the Purely Functional Data Structures book has Haskell code that may be easier to adopt to Soft Heaps, especially given the example Java code.

https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Upvotes: 0

Don Stewart
Don Stewart

Reputation: 137947

A quick search of the ACM digital library indicates that Chazelle's soft heap structure, despite being very interesting, has received relatively little study, and that persistent/functional soft heaps are thus an open research topic.

So I would say no, there are no known approaches for persistent soft heaps. Describing one would be a publishable result (it may boil down to adding copying where you would mutate the original structure, and identifying sharing opportunities).

Upvotes: 20

Related Questions