Expiring cached data?

[Tom Pledger]

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