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
implicitconversions 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.