caching results of iterative procedure.

Quote:

> One more question, please. Could someone suggest me a good

> way to define `memo' that make it works with procedure of

> any arity? (as `memoized' and `non-memoized' do). To use

> wt-trees I need a way to put an order to object of unknown

> structure.

There is no standard-compliant way to order arbitrary objects in

Scheme, nor to compute hash codes for them. Thus a truly general memo

in standard Scheme would be doomed to use simple linear search for the

table of prior cases, rendering it of dubious value. If you limit

yourself to procedures that take some number of numerical arguments

(or perhaps integer, or integer with range limitations), then

prospects are much brighter. You can get a list of all the arguments

using the unparenthesized-lambda-parameter notation, and then use

standard list-processing techniques. For example, if what you want is

ordering comparison, you just cdr down the two lists in parallel,

comparing corresponding elements.

By the way, in response to the earlier poster who suggested simply

replacing binomial with an iterative algorithm -- I assume that

Marco's point was not that he really wanted to do binomial

coefficients this way so much as that he was using that as a test case

for the general technology of memoization as a higher-order procedure.

If the point is really to do an efficient binomial coefficient

calculation, though, your solution may not be the best either, since

it relies so intesively on multiplication and division. Depending on

the machine, language implementation, range of numbers used, etc., you

may find that you are better off with an approach that only uses

addition. Marco's memoized version does, but it can be improved on

(if efficiency is the name of the game) by being more careful with the

data structure and order in which values are computed.

-Max Hailperin

Associate Professor of Computer Science

Gustavus Adolphus College

800 W. College Ave.

St. Peter, MN 56082

USA

http://www.gustavus.edu/~max/