/* hashed.q: memorize function values */

// reference to the table of past results (initially empty)

def HASH = ref emptyhdict;

// retrieve a hashed function value if possible, or calculate it and store it
// in the table

public hashed F X;
hashed F X	= get HASH!(F,X) if member (get HASH) (F,X);
		= put HASH (update (get HASH) (F,X) Y) || Y
		    where Y = F X otherwise;

// Example: hashed fib function

private hfib;
fib		= hashed hfib;

hfib 0		= 0;
hfib 1		= 1;
hfib N		= fib (N-1)+fib (N-2) if N>1;