Pure Danger Tech


clojure-conj: Data structures

25 Oct 2010

There were two great data structures talks on day 1. Luke VanderHart did a talk on Clojure zippers which are present in core and Chris Houser talked about his implementation of finger trees. I’ve spent some time playing with zippers so much of this talk was review for me, but it was well presented. It inspired me to write up what we’ve done with building zippers from trees of records and the tree pattern-matching and mutation facilities we’ve built over the top. I did a lightning talk of this stuff on day 2.

Chris’s talk on finger trees was really intriguing and I look forward to thinking more about where they are useful vs other existing data structures.

Finger trees allow you to do a lot of interesting things that seem match up well with Clojure but I’m not going to try to explain it because I don’t understand it yet. :) I think some use cases where they’d be useful are when you need a list with fast add/remove on either end or if you need a sorted set with the ability to quickly (log(n)) check containment and select an nth element from the sorted set.

Finger trees reminded me a little of some of the nice properties of skip lists (which I explored here a bit) although I suspect finger trees have huge advantages over skip lists from a persistent data structure viewpoint.

I guess I should also mention the lightning talk by Zach Tellman about Aleph that uses asynchronous event-driven channels which are also data structures of a sort and a pretty classic abstraction for communication.