Combine memoization and tail-recursion

Question

Is it possible to combine memoization and tail-recursion somehow? I'm learning F# at the moment and understand both concepts but can't seem to combine them.

Suppose I have the following memoize function (from Real-World Functional Programming):

let memoize f = let cache = new Dictionary<_, _>()                 (fun x -> match cache.TryGetValue(x) with                           | true, y -> y                           | _       -> let v = f(x)                                        cache.Add(x, v)                                        v) 

and the following factorial function:

let rec factorial(x) = if (x = 0) then 1 else x * factorial(x - 1) 

Memoizing factorial isn't too difficult and making it tail-recursive isn't either:

let rec memoizedFactorial =   memoize (fun x -> if (x = 0) then 1 else x * memoizedFactorial(x - 1))  let tailRecursiveFactorial(x) =   let rec factorialUtil(x, res) = if (x = 0)                                   then res                                   else let newRes = x * res                                        factorialUtil(x - 1, newRes)   factorialUtil(x, 1) 

But can you combine memoization and tail-recursion? I made some attempts but can't seem to get it working. Or is this simply not possible?

Answer 1

As always, continuations yield an elegant tailcall solution:

open System.Collections.Generic   let cache = Dictionary<_,_>()  // TODO move inside  let memoizedTRFactorial =     let rec fac n k =  // must make tailcalls to k         match cache.TryGetValue(n) with         | true, r -> k r         | _ ->              if n=0 then                 k 1             else                 fac (n-1) (fun r1 ->                     printfn "multiplying by %d" n  //***                     let r = r1 * n                     cache.Add(n,r)                     k r)     fun n -> fac n id  printfn "---" let r = memoizedTRFactorial 4 printfn "%d" r for KeyValue(k,v) in cache do     printfn "%d: %d" k v  printfn "---" let r2 = memoizedTRFactorial 5 printfn "%d" r2  printfn "---"  // comment out *** line, then run this //let r3 = memoizedTRFactorial 100000 //printfn "%d" r3 

There are two kinds of tests. First, this demos that calling F(4) caches F(4), F(3), F(2), F(1) as you would like.

Then, comment out the *** printf and uncomment the final test (and compile in Release mode) to show that it does not StackOverflow (it uses tailcalls correctly).

Perhaps I'll generalize out 'memoize' and demonstrate it on 'fib' next...

EDIT

Ok, here's the next step, I think, decoupling memoization from factorial:

open System.Collections.Generic   let cache = Dictionary<_,_>()  // TODO move inside  let memoize fGuts n =     let rec newFunc n k =  // must make tailcalls to k         match cache.TryGetValue(n) with         | true, r -> k r         | _ ->              fGuts n (fun r ->                         cache.Add(n,r)                         k r) newFunc     newFunc n id  let TRFactorialGuts n k memoGuts =     if n=0 then         k 1     else         memoGuts (n-1) (fun r1 ->             printfn "multiplying by %d" n  //***             let r = r1 * n             k r)   let memoizedTRFactorial = memoize TRFactorialGuts   printfn "---" let r = memoizedTRFactorial 4 printfn "%d" r for KeyValue(k,v) in cache do     printfn "%d: %d" k v  printfn "---" let r2 = memoizedTRFactorial 5 printfn "%d" r2  printfn "---"  // comment out *** line, then run this //let r3 = memoizedTRFactorial 100000 //printfn "%d" r3 

EDIT

Ok, here's a fully generalized version that seems to work.

open System.Collections.Generic   let memoize fGuts =     let cache = Dictionary<_,_>()     let rec newFunc n k =  // must make tailcalls to k         match cache.TryGetValue(n) with         | true, r -> k r         | _ ->              fGuts n (fun r ->                         cache.Add(n,r)                         k r) newFunc     cache, (fun n -> newFunc n id) let TRFactorialGuts n k memoGuts =     if n=0 then         k 1     else         memoGuts (n-1) (fun r1 ->             printfn "multiplying by %d" n  //***             let r = r1 * n             k r)   let facCache,memoizedTRFactorial = memoize TRFactorialGuts   printfn "---" let r = memoizedTRFactorial 4 printfn "%d" r for KeyValue(k,v) in facCache do     printfn "%d: %d" k v  printfn "---" let r2 = memoizedTRFactorial 5 printfn "%d" r2  printfn "---"  // comment out *** line, then run this //let r3 = memoizedTRFactorial 100000 //printfn "%d" r3  let TRFibGuts n k memoGuts =     if n=0 || n=1 then         k 1     else         memoGuts (n-1) (fun r1 ->             memoGuts (n-2) (fun r2 ->                 printfn "adding %d+%d" r1 r2 //%%%                 let r = r1+r2                 k r))  let fibCache, memoizedTRFib = memoize TRFibGuts  printfn "---" let r5 = memoizedTRFib 4 printfn "%d" r5 for KeyValue(k,v) in fibCache do     printfn "%d: %d" k v  printfn "---" let r6 = memoizedTRFib 5 printfn "%d" r6  printfn "---"  // comment out %%% line, then run this //let r7 = memoizedTRFib 100000 //printfn "%d" r7