Purely Functional Data Structures - Chris Okasaki

I got this book in Egypt, and it's taken me well over a month since getting back to actually get round to reading it and finishing it. This book is described as a "handy reference for professional programmers working with functional languages". This is the biggest lie since the title "ML for the Working Programmer".

The book is excellent. My suspicion is that it's Okasaki's thesis rewritten in book form. It's basically "nuts tricks you can play with functional languages to get good performance, even in the face of pure functional languages'. As a book of highly-abstract tricks, it makes a nice contrast to the low-level bit-twiddling tricks of Warren's "Hacker's Delight".

The book is really not about the data structures - it's more an armoury of techniques to, for example, get good worst-case costs through scheduled lazy evaluation. The guy's some kind of pure functional god, and the book makes my head hurt. Genius.

Posted 2004-05-16.