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⑈ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe