[boost] Memoization library

From: Jim Apple (japple_at_[hidden])
Date: 2003-12-11 20:25:26

Is there any interest in a memoization library?  I've begun writting one 
  for the following reasons:

* Memoization can be more efficient than dynamic programming
* Memoization allows user-space functions to still be written recursively
* Memoization can keep state between calls, and therefore used in 
situations that would not call for dynamic programming

I am deterred by the following
* Memoization can encourage sloppy programming - For some problems, 
dynamic programming really is best
* The best syntax I've come up with is a bit clumsy:

int choose(int n, int k, function<int (int, int)> recur);
int choose(int n, int k, function<int (int, int)> recur = choose) {
   if ((k == 0) || (k == n)) {
     return 1;
   } else {
     return recur(n-1,k-1) + recur(n-1,k);
   }
}

memoize(choose)(50,25);
choose(50,25)
========= or  =================
 

int choose_memo(int n, int k, function<int (int, int)> recur) {
   if ((k == 0) || (k == n)) {
     return 1;
   } else {
     return recur(n-1,k-1) + recur(n-1,k);
   }
}
 

int choose(int n, int k) {
   return choose_memo(n,k,choose);
}

memoize(choose_memo(50,25));
choose(50,25)
=========end code ================

Jim Apple