Saturday, November 10, 2012

F# Memorization on Recursive Function

The memoization on recursive function is a topic I spent this Friday on.

Typical solution for memoization Fibonacci is listed below:


 let mem f =   
   let lookup = System.Collections.Generic.Dictionary<_,_>()  
   fun n ->  
     match lookup.TryGetValue n with  
     | true, v -> v  
     | _ ->  
       let a = f n  
       lookup.Add(n, a)  
       a  
 let rec fibonacci3 = mem (fun n ->   
               match n with   
               | 0 | 1 -> 1  
               | _ -> (fibonacci3 (n-1)) + (fibonacci3 (n-2)))  

Does this has a more general solution? Thanks to our team's Vlad, the following is a more general solution.

 let memoize wrapFunction =  
   let cache = System.Collections.Generic.Dictionary()  
   let rec f x =   
     match cache.TryGetValue x with  
     | true, v -> v  
     | false, _ ->  
       let v = wrapFunction f x  
       cache.[x] <- v  
       v  
   f  
 let fib =   
   memoize (  
     fun f x ->  
       if x < 2 then 1  
       else f(x - 1) + f(x - 2)  
   )  


No comments: