[Haskell-cafe] function result caching

[John Meacham]

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⑈