Skip to content

Latest commit

 

History

History
49 lines (44 loc) · 2.35 KB

README.md

File metadata and controls

49 lines (44 loc) · 2.35 KB

Fun Programming

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.

From the book:

Purely Functional Data Structures

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

Features:

  • 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)

Links:

Sample code

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;
}

Author

🔥 Greg Eakin