[Haskell-cafe] Re: function result caching

[ajb at spamcop.net]

G'day all.

Carl Witty wrote:

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

Quoting apfelmus at quantentunnel.de:

> This, also known as patricia tree, is indeed the canonical answer.

A Patricia tree is but one infinite tree data structure.  There's
another (which is actually an infinite list of balanced binary trees)
at http://haskell.org/hawiki/MemoisingCafs

Cheers,
Andrew Bromage