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