# Could someone give me an example of to use this code

Discussion in 'Javascript' started by lorlarz, Feb 26, 2010.

1. ### lorlarzGuest

Could someone give me an example of to use this code?:

function memoizer(memo, formula) {
var recur = function (n) {
var result = memo[n];
if (typeof result !== 'number') {
result = formula(recur, n);
memo[n] = result;
}
return result;
};
return recur;
};
var factorial = memoizer([1, 1], function (recur, n) {
return n * recur(n -1);
});
var fibonacci = memoizer([0, 1], function (recur, n) {
return recur(n -1) + recur(n -2);
});

lorlarz, Feb 26, 2010

2. ### lorlarzGuest

Here (AGAIN) is the code (for which I need a sample (example) of its
use:

(Some of the previous post got posted as quoted material wrongly
last time. HERE is the whole script):

function memoizer(memo, formula) {
var recur = function (n) {
var result = memo[n];
if (typeof result !== 'number') {
result = formula(recur, n);
memo[n] = result;
}
return result;
};
return recur;
};
var factorial = memoizer([1, 1], function (recur, n) {
return n * recur(n -1);
});
var fibonacci = memoizer([0, 1], function (recur, n) {
return recur(n -1) + recur(n -2);
});

(end of script)

lorlarz, Feb 26, 2010

3. ### Martin HonnenGuest

You can call that function like this:
var fact5 = factorial(5);
That computes 1 * 2 * 3 * 4 * 5 and stores ("memorizes") the results so
that on the next call of "factorial" with arguments less than 6 no
recursion is needed.

Martin Honnen, Feb 26, 2010
4. ### Scott SauyetGuest

As Martin pointed out, this memoizes the function so that when it's
called again with the same parameter, it just looks up and returns a
stored value; this is useful for any function that takes significant
calculation and might be called often with the same parameter,
including via recursive calls.

There are many different versions out there, but some of them are
simpler to understand than that one. One simple one for functions of
a single parameter is this:

function memoize(f) {
var cache = {};
return function (n) {
return (n in cache)? cache[n] : cache[n] = f(n);
};
}

It can then be used like this:

function fibonacci (x) {
if(x < 2) return 1; else return fibonacci (x-1) + fibonacci
(x-2);
}

fibonacci = memoize(fibonacci)

This should be useful for any single-valued function for which the
distinct inputs have distinct String-valued representations (because
"n in cache" will do a String conversion of "n".)

Cheers,

-- Scott

Scott Sauyet, Feb 26, 2010
5. ### lorlarzGuest

I see that it does work and that you can get the result at the end of
each recursion,
but I still do not understand the way n (when factorial(x); is called)
gets to where
it needs to get. Could someone elaborate on the details of how the n
value "travels"
through this routine?

lorlarz, Feb 26, 2010
6. ### lorlarzGuest

Ecen in your clearer version I have trouble understanding how the
value
gets to n in:

return function (n)

lorlarz, Feb 26, 2010
7. ### Scott SauyetGuest

memoize is a function that accepts a function as a parameter and
returns another function.

Remember that functions are first-class items in Javascript. They can
be supplied as parameters, assigned to variables, returned from
functions, etc.

A somewhat more verbose version of the same idea is this:

function memoize(f) {
var cache = {};
function result(n) {
return (n in cache)? cache[n] : cache[n] = f(n);
};
return result;
}

The input parameter is a function, "f". "memoize" returns the
function internally named "result". That function takes a single
parameter, called "n". The only difference in the earlier version is
that instead of naming the returning function, it uses an anonymous
one.

So the "n" gets called when you do this:

var fib = memoize(function fib(n) {
if (n < 2) return 1;
return fib(n-1) + fib(n-2);
});

or if you want to break it down, like this:

function fib(n) {
if (n < 2) return 1;
return fib(n-1) + fib(n-2);
}

fib = memoize(fib);

Does that make sense?

-- Scott

Scott Sauyet, Feb 26, 2010
8. ### Scott SauyetGuest

I've only once used it for DOM-related code. But I've done some
mathematics-heavy work, and it helped a lot. On one occasion, it sped
up a process from the 20-30 second range down to below 100ms.

The DOM bit was a few years back. I had a collection of deeply-nested
lists representing parent-child relationships, and needed to highlight
on click of one node all those nodes of certain degrees of
consanguinity (equivalent, say, to "second-cousin, once removed".) I
generated functions for each degree of relatedness I cared about,
functions accepting a node and returning an array of related nodes,
and then memoized the result of that function. Although I never timed
it, it made for a much snappier interface, as the users regularly
clicked on only a few nodes per visit, but would hit them many times
each.

I do think that it's a rare case to need this for normal DOM work, but
as the ES engines get more powerful, they might become better vehicles
for computation-intensive work, and these techniques might become more
powerful.

-- Scott

Scott Sauyet, Feb 26, 2010
9. ### lorlarzGuest

[snip]

Scott, thanks. That just about makes sense. It is kinda like the
passed-in function is
a local contained function within some same outer function. But THEN
it seems to me
the parameter name (n) would have to be the same name (that is: n) any
other time a parameter is
needed. Above you use n in both the parameter locations YET, in a
previous post you
cited this example: (and one place you use x and the other n and still
it works!!??):

function memoize(f) {
var cache = {};
return function (n) {
return (n in cache)? cache[n] : cache[n] = f(n);
};
}

function fibonacci (x) {
if(x < 2) return 1; else return fibonacci (x-1) + fibonacci
(x-2);
}

fibonacci = memoize(fibonacci);

// AND YET THE FOLLOWING WORKS!!??? when it starts x
// but the other internal function uses n !!!

Obviously my understanding is still not clear (or quite right)

lorlarz, Feb 26, 2010
10. ### Scott SauyetGuest

Javascript does not have named parameters; they are interpreted by
position. It simply doesn't matter what you call them.

For instance, if you have this:

return x + 1;
}

function nthOdd(n) {
var temp = 2 * n;
}

it doesn't matter that the outer function, "nthOdd", calls the inner
one, "addOne" using a parameter named "temp". When the inner one is
processed, the value of the first parameter is assigned to "x".

This may or may not be helpful, but you could think of the value of
memoize(fibonacci) to be the following function:

function(n) {
return (n in cache)
? cache[n]
: cache[n] = (function fibonacci (x) {
if(x < 2) return 1;
return fibonacci (x-1) + fibonacci(x-2);
})(n);
};

where cache has been defined in such a way as to be available when the
function is called. The following syntax means that the internal
function should have the value stored in "n" assigned to its parameter
"x":

(function internal(x) {
// return result of calculations involving x
})(n); // with the value of "n" assigned to "x"

Cheers,

-- Scott

Scott Sauyet, Feb 26, 2010
11. ### lorlarzGuest

[snip]

I can make sense of it only by looking at it 2 ways. (1) the
way you describe it above -- and I am taking that quite a lot on
faith, since the n parameter is being passed not only to the
function it was sent to but by to the anonymous function which
is outside where the passed function is actually used.

(2) it semms fine to me that the function along with its parameter,
however named
is plopped in IN FULL as sent (with filled parameter) to the spot
where it is used (fully appreciating the name of the parameter
does not matter).

To reiterate:
Really, the only strange part of the situation is that the
outer anonymous function being returned using
whatever it is called, and that is what you claim -- which
I again must take on faith just because it is what
you say with your code translation happens.
But I hate to take things
on faith and how that happens is still not clear.

So, it is still weird to me that in the following, the return function
(n) { ...}
the outer anon function is given THAT param. It is not strange that
the f(x) in the inner function can get f(x):

function memoize(f) {
var cache = {};
return function (n) {
return (n in cache)? cache[n] : cache[n] = f(n);
};
}

function fibonacci (x) {
if(x < 2) return 1; else return fibonacci (x-1) + fibonacci
(x-2);
}

fibonacci = memoize(fibonacci);

lorlarz, Feb 26, 2010
12. ### lorlarzGuest

Scott wrote:

[snip]

I can make sense of it only by looking at it 2 ways. (1) the
way you describe it above -- and I am taking that quite a lot on
faith, since the n parameter is being passed not only to the
function it was sent to but by to the anonymous function which
is outside where the passed function is actually used.

(2) it semms fine to me that the function along with its parameter,
however named
is plopped in IN FULL as sent (with filled parameter) to the spot
where it is used (fully appreciating the name of the parameter
does not matter).

To reiterate:
Really, the only strange part of the situation is that the
outer anonymous function being returned using
whatever it is called, and that is what you claim -- which
I again must take on faith just because it is what
you say with your code translation happens.
But I hate to take things
on faith and how that happens is still not clear.

So, it is still weird to me that in the following, the return
function
(n) { ...}
the outer anon function is given THAT param. It is not strange that
the f(n) in the inner function can get f(x):

function memoize(f) {
var cache = {};
return function (n) {
return (n in cache)? cache[n] : cache[n] = f(n);
};
}

function fibonacci (x) {
if(x < 2) return 1; else return fibonacci (x-1) + fibonacci
(x-2);
}

fibonacci = memoize(fibonacci);

lorlarz, Feb 26, 2010
13. ### Scott SauyetGuest

I think I'm getting confused by your confusion. Perhaps a simpler function-returning-function would help:

return function(x) {
return n + x;
};
}

// equivalent to function(x) {return 7 + x;}

If you listened to the Crockford talk you discussed in another thread,
you'll know that there was a fair bit about closures. The fact that
concerning you, right? That's just the parameter supplied. The fact
that it has access to the value 7 might be a little more surprising.
To understand that more fully, you might want to look at the FAQ notes
on closures .

Cheers,

-- Scott
____________________
 http://jibbering.com/faq/faq_notes/closures.html

Scott Sauyet, Feb 26, 2010
14. ### lorlarzGuest

[snip]
I did some experiments:

As long as there is a function returned where a parameter is used in
any function,
it knows the parameter passed to
memoize IN the function passed and uses it: Here are some
experiments:

function memoize(f) {
var cache = {};
//alert(n); // <- n is not known here
return function(n) {alert(n);} // this works even though
// passed in function not used

}

function fibonacci (x) {

}

fibonacci = memoize(fibonacci)

fibonacci(5);

lorlarz, Feb 26, 2010
15. ### lorlarzGuest

I got it now. Remembering the function passed in the more complex
example, is simply like remembering the 7 in your simple example.

I usually understand closures. Somehow I got confused when a function
was involved. At this moment, I too, do not even understand my
confusion.

Perhaps, the fact that recursion was also involved in the somewhat
more
complex example (as well as a closure) freaked me out.

Thanks for your help Scott. You really did help. Regards, Larz

lorlarz, Feb 26, 2010
16. ### lorlarzGuest

[snip]
As a P.S. to my own reply, let me state that what is really neat
about the routine other than closure and other than recursion
is the ability to mutate functions or add onto them when you
pass in a function and return that function (mutated in any way you
want or not) _and_/_or_ with whatever else you want to return in the
return statement that can also use whatever the numbers of
parameter(s)
you have set up to be sent in when you finally use that which is
returned.

Indeed all that provides for exciting possibilities. Perhaps my over
excitement about all this before nnt-clearly-seen feature resulted in
the confusion. It is a lot more than setting a function for
systematic
reuse with modification (and thus is good fdr many situations other
than
recursion).

Thanks again, Scott, and thanks to Stefan for his kindly submitted
perspectives and useful inputs.

lorlarz, Feb 27, 2010
17. ### Dr J R StocktonGuest

In comp.lang.javascript message <4b87f8c3\$0\$6720\$
or-online.net>, Fri, 26 Feb 2010 17:37:19, Martin Honnen
Examples of cacheing, of varying potency, can be seen in
<URL:http://www.merlyn.demon.co.uk/js-misc0.htm#Cash>. That may partly

If it is known that the result can never be equivalent to false, the
test-or-call can be somewhat simplified.

As coded, the OP's memoizer only works if the answers are numbers. If
the rest were against "undefined" the restriction would be effectively
removed.

Dr J R Stockton, Feb 28, 2010