Purely functional Okasaki-style red-black tree maps in Scala

[article index] [] [@mattmight] [rss]

[Update: You probably want to see my newer post on red-black deletion. With a full red-black map implementation in Racket.]

I've been working on a static analysis engine, and I needed node- and subtree-level access to a functional map backed by balanced trees.

No language libraries provide this access readily, so this was a good opportunity to see how easily red-black trees could be implemented in Scala.

Chris Okasaki's Purely Functional Data Structures is the standard reference for implementing efficient functional data structures, and the code below is based on his implementation. At first, I practically transliterated from the Haskell code, and then I polished it up with object-oriented "best practices."

In the process, I learned three things about Scala:

  • I learned why the generic data structures in Scala libraries prefer implicit conversions to constraints. As it turns out, the implicit approach is more flexible, making it possible to use third-party classes with your map structure.
  • I also learned how to use private[package] to get fine-grained control over a member's package-level scope.
  • Finally, I learned how to create helper objects that make constructing data structures more natural and succinct.