I just got Purely Functional Data Structures by Chris Okasaki. I read his Thesis when I was in college and I wanted to check out the expanded print version. There were several nice things about the data structures presented in the book. Besides being very clear conceptually, they also allowed for very useful features like ‘persistence’. I.e. being allowed to modify a structure without destroying the original.
Back when I read it I spent a little bit of time trying to implement the code in java. However, I ran into two stumbling blocks. The first was that java doesn’t allow free floating functions. The second is that a fundamental feature needed to support these data structures is the ability to lazily evaluate code and then store the result (also known as memoization). I was able to get around the first issue by using anonymous classes, but it was kind of clunky. I was working on the lazy evaluation but then projects and whatnot got in the way.
For the second issue, C# helped out by giving having delegates which are a decent replacement for free floating functions. C# 2.0 adds anonymous delegate that make it easier (although not trivial) to create lambdas. And now, thanks to the LazyLoader work Jay, Kevin and I did, it’s possible to have lazily evaluated expressions.
I’m going to do some experimentation in my spare time to try to implement these and make them available to see how C# 2.0 compares in ease over the functional languages I’m used to.