Conal Elliott writes: | Hi Andrew. This situation is what weak pointers [1] are for. You keep | weak rather than regular pointers to your cache data. The garbage | collector clears out the weak pointers and reclaims cache data when | necessary. However, I don't think there is any policy to make | discriminating choices about *which* cache data gets discarded, for | instance least recently (or frequently) used. : How about adapting splay trees so that their pointers become weak after a certain depth? The advantage for caching is that the more frequently used elements move closer to the root, so you wouldn't have to add much code for tracking recent use, just a depth threshold. See the book Purely Functional Data Structures for more details on implementing splay trees in a functional setting. - Tom