This project implements C# versions of the data structures from Chris Okasaki’s book Purely Functional Data Structures. These are implemented as static functions, to closely resemble the book’s version. These are meant to be used as a companion when reading the book. This allows one to fire up the samples, in a debugger, and see how they work. It also allows one to test the performance to see how they stack up with other data structures.

Purely Functional Data Structures

Okasaki, Chris. Purely Functional Data Structures. Cambridge, U.K.: Cambridge UP, 1998. Print.

• Abstract Data Types --> templates
• Immutable data structures --> readonly data members
• Lazy evaluation --> class Lazy<T>
• Polymorphic recursion --> Static member functions
• Structure dumping --> Only implemented in test code
• Recursive structures --> Not supported (cut and paste for now)

• Community Edition of Visual Studio (Free)
• Git Extensions (Free)
• ReSharper, Extensions for .NET Developers
• A retrospective from Chris Okasaki
• Amazon.com
• Google Books
• Chris Okasaki’s original PhD dissertation

To update a shared set across multiple threads, we can use an Interlocked.CompareExchange() to only update the pointer, when it hasn't changed.

var word = NextWord(10);
while (true)
{
 var workingSet = _set;
 Thread.MemoryBarrier();
 var newSet = SplayHeap<string>.Insert(word, workingSet);
 var oldSet = Interlocked.CompareExchange(ref _set, newSet, workingSet);
 if (ReferenceEquals(oldSet, workingSet))
 break;
}

🔥 Greg Eakin