Purely Functional Data Structures in Clojure: Leftist Heaps
Last year I started reading a book called Purely Functional Data Structures. It’s a fascinating book and if you’ve ever wondered how Clojure’s persistent data structures work, it’s mandatory reading.
I had no clue about Haskell’s - much less ML’s! - syntax and I was finding it very difficult to follow along. What I did notice is that their syntaxes are not so different from each other.
So I put the book down and read Learn You a Haskell For Great Good! with the hopes that learning more about haskell’s syntax - in particular, learning how to read its type signatures - would help me get going with Puretly Functional Data Structures.
Luckily, I was right - and I recommend you do the same if you’re not familiar with either of those languages. Learn You a Haskell For Great Good! is a great book and I got a lot out of it. My series on Monads is a product of reading it.
Enough background though.
The purpose of this post is two-fold: One is to share the github repository I created and that will contain the Clojure versions of the data structures in the book as well as most solutions to the exercises - or at least as many as my time-poor life allows me to implement.
The other is to walk you through some of the code and get a discussion going. Hopefully we will all learn something - as I certainly have when implementing these. Today, we’ll start with Leftist Heaps.
- Every node has a rank, which is the distance from its right spine to the nearest leaf
- A node’s left child has a rank at least as large as its right child
In a nutshell, these are the operations we need to be able to perform on a leftist heap:
- insert a value into an existing heap
- merge two heaps
- find the minimum value in a heap
- delete the minimum value, returning a new heap
Since the book uses ML/Haskell, it starts with a data type definition for Heaps that exposes these and a couple of other auxiliary functions. I decided to take a stab at writing the solution using Clojure’s protocols and records:
1 2 3 4 5 6 7 8 9
When implementing the algorithms the base case for the recursive solutions will involve dealing with nil values which at first seems like it wouldn’t be a problem. However, protocol functions dispatch on the type of its first argument so what happens if I call the function is-empty? on nil?
Luckily, Clojure allows us to extend a protocol to core types:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Note how I extended a few of the protocol functions to the nil data type, allowing me to continue with this implementation with no nasty hacks.
There’s one last bit missing: a function that will ensure each heap retains the leftist property:
1 2 3 4 5 6 7
The reason this function is isolated is that the Heap protocol defined above is fairly generic and could be used for defining other types of heaps - and I didn’t feel it warranted its own interface.
We can now play with it and create a new leftist heap:
1 2 3 4 5 6 7
While I quite like this approach, I thought I’d also implement this solution using Clojure’s core data types - maps in this case - and no protocols. The code is shown below:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
Using it is equally simple:
1 2 3 4 5 6 7
That’s it for now.
As I implement more of the book’s code and exercises I’ll add them to the github repo - it also includes tests for all implementations.