Functional data-structures (F#, ML, Haskell)

A good way to learn Standard ML (which is very similar to F#) is to read Chris Okasaki's book, Purely Functional Structures, which uses ML for examples in the main text.

Okasaki has many interesting ideas on functional programming. For example, among other interesting articles here, I enjoyed "Alternatives to Two Classic Data Structures".

There is also source code next to the PDF, in both Java and Ada. However, the deletion routine for red-black trees is missing from the source code. I mention that because, as Randall Helzerman points out in an Amazon comment on Okasaki's book,

Although he presents an EXTREMELY lucid description of how to implement Red-Black trees in a functional language, he only presented algorithms for insertion and querying. Of course, deletion from a red-black tree is the hardest part, left here, I suppose, as an exercise to the student. If you want to supply this missing piece yourself, check out a paper by Stefan Kars, "Red-black trees with types", J. Functional Programming 11(4):425-432, July, 2001. It presents deletion routines, but you'll still want to read Okasaki's book first, for unless you're very much smarter than me you won't be able to understand Kars' paper until you read Okasaki's exposition of red black trees.

Unfortunately, I do not have access to that Journal. I'm hoping to get a PDF from a friend.... Here it is. Warning: The code it shows, including for deletion, uses existential types.

Functional data-structures are interesting for many reasons, not the least of which is their value in persistent data storage, such as in a system that was used when I was at AMD. Here is an overview of current knowledge of such data-structures.