[Haskell-cafe] Re: function result caching

[apfelmus at quantentunnel.de]

Carl Witty wrote:
> Instead of using an infinite list, you can use an infinite binary tree,
> with a cached result at every node.

This, also known as patricia tree, is indeed the canonical answer. In
general, one can always construct an (in)finite map from keys (Ints in
the present case) to values as a trie. See also

  Ralf Hinze. Generalizing generalized tries. Journal of Functional
  Programming, 10(4):327-351, July 2000
  http://www.informatik.uni-bonn.de/~ralf/publications/GGTries.ps.gz

This paper uses generic programming, but that should not be the problem
as concrete cases can always be constructed "by hand" in plain Haskell.
To apply this to Ints, one should view them as

    type Int = [Digit]
    data Digit = Zero | One

Also note that there is absolutely no balancing involved (which would
break infinite and lazy stuff).

Regards,
apfelmus