 6 people like it.

# Memoization for dynamic programming

The snippet shows how to implement reusable memoization function and how to use it to implement efficient Fibonacci number generator using dynamic programming.

## Recursive Fibonacci

 ```1: 2: 3: 4: 5: 6: 7: 8: ``` `````` /// Inefficient recursive implementation of Fibonacci numbers. /// /// The problem is that 'fibs 3' will call 'fibs 1' recursively /// three times. To solve this, we'd like to keep the result of /// previously calculated function calls using dynamic programming. let rec fibs n = if n < 1 then 1 else (fibs (n - 1)) + (fibs (n - 2)) ``````

## Reusable memoization function

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: ``` `````` open System.Collections.Generic /// The function creates a function that calls the argument 'f' /// only once and stores the result in a mutable dictionary (cache) /// Repeated calls to the resulting function return cached values. let memoize f = // Create (mutable) cache that is used for storing results of // for function arguments that were already calculated. let cache = new Dictionary<_, _>() (fun x -> // The returned function first performs a cache lookup let succ, v = cache.TryGetValue(x) if succ then v else // If value was not found, calculate & cache it let v = f(x) cache.Add(x, v) v) ``````

## Memoized Fibonacci

 ```1: 2: 3: 4: 5: 6: 7: 8: 9: ``` `````` /// Recursive function that implements Fibonacci using memoization. /// Recursive calls are made to the memoized function, so previously /// calculated values are retrieved from the cache. let rec fibs = memoize (fun n -> if n < 1 then 1 else (fibs (n - 1)) + (fibs (n - 2))) // Note - add #nowarn "40" to disable warning complaining about recursive // value reference. This is not an issue in this snippet. ``````
val fibs : n:int -> int

Full name: Script.Simple.fibs

Inefficient recursive implementation of Fibonacci numbers.

The problem is that 'fibs 3' will call 'fibs 1' recursively
three times. To solve this, we'd like to keep the result of
previously calculated function calls using dynamic programming.
val n : int
namespace System
namespace System.Collections
namespace System.Collections.Generic
val memoize : f:('a -> 'b) -> ('a -> 'b) (requires equality)

Full name: Script.Memoized.memoize

The function creates a function that calls the argument 'f'
only once and stores the result in a mutable dictionary (cache)
Repeated calls to the resulting function return cached values.
val f : ('a -> 'b) (requires equality)
val cache : Dictionary<'a,'b> (requires equality)
Multiple items
type Dictionary<'TKey,'TValue> =
new : unit -> Dictionary<'TKey, 'TValue> + 5 overloads
member Add : key:'TKey * value:'TValue -> unit
member Clear : unit -> unit
member Comparer : IEqualityComparer<'TKey>
member ContainsKey : key:'TKey -> bool
member ContainsValue : value:'TValue -> bool
member Count : int
member GetEnumerator : unit -> Enumerator<'TKey, 'TValue>
member GetObjectData : info:SerializationInfo * context:StreamingContext -> unit
member Item : 'TKey -> 'TValue with get, set
...
nested type Enumerator
nested type KeyCollection
nested type ValueCollection

Full name: System.Collections.Generic.Dictionary<_,_>

--------------------
Dictionary() : unit
Dictionary(capacity: int) : unit
Dictionary(comparer: IEqualityComparer<'TKey>) : unit
Dictionary(dictionary: IDictionary<'TKey,'TValue>) : unit
Dictionary(capacity: int, comparer: IEqualityComparer<'TKey>) : unit
Dictionary(dictionary: IDictionary<'TKey,'TValue>, comparer: IEqualityComparer<'TKey>) : unit
val x : 'a (requires equality)
val succ : bool
val v : 'b
Dictionary.TryGetValue(key: 'a, value: byref<'b>) : bool
Dictionary.Add(key: 'a, value: 'b) : unit
val fibs : (int -> int)

Full name: Script.Memoized.fibs

Recursive function that implements Fibonacci using memoization.
Recursive calls are made to the memoized function, so previously