[Haskell-cafe] function result caching

[Carl Witty]

On Fri, 2006-10-13 at 01:27 +0300, Silviu Gheorghe wrote:
> it does, thank you very much for the quick answer, unfortunately as I
> understand it, it doesn't work well on ints :(
> 
> for just now i created a list 
> 
> slowFunctionCacheList= [slowFunction (i) | i <-[0..5000000]] 
> and use "slowFunctionCacheList !! i" instead of "slowFunction (i)"
> 
> it helped alot (i mean i stoped the program after "3 hours still
> working" and got the result in 2 minutes :))
> 
> i am still curious about a better method (and a general one), because
> this is ugly, and it only works on ints as i see it.

I can describe a method that's uglier, faster, and more general; is that
better or not?

You're using an infinite list to store your cached results.  (Well, your
list is actually finite, but an infinite list would work just as well.)

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.

Carl Witty