On Thu, Oct 12, 2006 at 04:01:14PM -0700, Carl Witty wrote:
Instead of using an infinite list, you can use an infinite binary tree, with a cached result at every node. Construct a binary tree with the following property: Consider the path from the root to a node, where left branches are called "0" and right branches are called "1". This sequence of 0's and 1's is the binary expansion of the key whose cached value is stored at that node (with the least-significant-bit at the root of the tree). (Actually constructing this tree, and looking things up in it, is left as an exercise for the reader; but it isn't very hard.)
This generalizes to any kind of key that can be uniquely serialized into bits; looking up the corresponding value then takes O(# of bits in the key) extra time and space, which is far better than the O(2^(# of bits in the key)) that an infinite list would use.
it is too bad IntSet and IntMap are strict in their subtrees, it would have been nice to provide things like infiniteMap :: (Int -> a) -> IntMap a infiniteMap = ... cachingSet :: (Int -> Bool) -> IntSet cachingSet = ... out of curiosity, why are IntMap and IntSet strict in their subtrees. since their subtrees are not of CPR form, I would think the benefit would not be that great and might even hurt in some situations... was there testing of the 'lazy' version? John -- John Meacham - ⑆repetae.net⑆john⑈