Scala allows you to use the
lazy keyword to defer the initialization of member values until they are called. With this technique, you can implement some excellent data structures called streams.
As discussed in Chapter 3.5.1 of Structure and Interpretation of Computer Programs by Abelson, Sussman, and Sussman (a.k.a. The Wizard Book), streams are delayed lists. They let us use sequence manipulations without forcing us to incur the cost of implementing these sequences as lists. Most importantly, we don’t have to initialize every value of a list in order to look at some of the values in the list.
Over the last two days, I’ve applied this technique to a stream-based QuadTree design, allowing me to have a data structure capable of providing access to massive (Terabyte-sized) terrain heightmaps without forcing me to load all of the terrain data into memory at once. Moreover, I can use my streaming QuadTree class to generate the terrain, building as much or as little of it as I need for the sake of demonstrations, and preserving the concept of shared vertices between neighboring (or enclosing) branch and leaf nodes.
This design is modular. Not as much as I’d like, and it needs more refactoring, but it’s modular enough that I could cache the terrain data to disk (or to a network service) after generation, and prune unused nodes from my local copy as I move through the terrain, in order to minimize runtime memory.
While technically possible to do this in Java, it would have been extremely ugly and complex. Once again, I’m really happy to be writing this project in Scala.
- alexsaintx posted this