5 people like it.

memoize

Memoize from _real world functional programming_ by Petricek and Skeet chapter 10 tutorial

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
let memoize fn =
  let cache = new System.Collections.Generic.Dictionary<_,_>()
  (fun x ->
    match cache.TryGetValue x with
    | true, v -> v
    | false, _ -> let v = fn (x)
                  cache.Add(x,v)
                  v)

let square n = 
  printfn "computing square of %d" n
  n*n

let memSquare = memoize square
memSquare 42
memSquare 42
memSquare 99 
val memoize : fn:('a -> 'b) -> ('a -> 'b) (requires equality)

Full name: Script.memoize
val fn : ('a -> 'b) (requires equality)
val cache : System.Collections.Generic.Dictionary<'a,'b> (requires equality)
namespace System
namespace System.Collections
namespace System.Collections.Generic
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<_,_>

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

Full name: Script.square
val n : int
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
val memSquare : (int -> int)

Full name: Script.memSquare
Raw view Test code New version

More information

Link:http://fssnip.net/mW
Posted:9 years ago
Author:Alan Wostenberg
Tags: optimizations