[PRL] Implementing sets efficiently in a functional language

[Johan Ovlinger]

I would also recommned Chris Okasaki's amortized datastructures.  He
gave a fascinating talk here at CCS a few years back (so long ago, the
faculty offices opposite the admin in cullinane were still meeting
rooms), where he showed (away, away memory haze!) how to express
several efficient datastructures in a functional manner.  Looking his
work up on the web, it seems that lazy evaluation was a key
ingredient in his amortized complexity, but I don't immediately recall
how that would come into the picture.

I do however recall wearing a huge grin as he described his functional
queue data structure. The invariants are so simple and so
effective.  I'm grinning now. It's just coo.