6 people like it.
Like the snippet!

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
calculated values are retrieved from the cache.

Raw view Test code New version

More information

Link:	http://fssnip.net/8P
Posted:	13 years ago
Author:	Tomas Petricek
Tags:	memoization , dynamic programming , fibonacci