A Sample of the Memoization Pattern in F#

Article
05/31/2007

Pieter Breed has been asking some useful questions on the F# list recently about using the "Map" type. I really appreciate it when people take the time to let us know when data structures are tricky to learn to use in F#.

Looking at Pieter's blog made me think it might be instructive to show how the memoization pattern looks in F# (or at least one example of the pattern). I've included the code below:

#light

open System

open System.Text

open System.Collections.Generic

// Save computed results by using an internal dictionary.
// Note that memoize is inferred to have type
// memoize: ('a -> 'b) -> ('a -> 'b)

let memoize f =

let cache = Dictionary<_, _>()

fun x ->

if cache.ContainsKey(x) then cache.[x]

else let res = f x

cache.[x] <- res

res

// An example, taken from Pieter's blog

let memoizedAppend =

memoize (fun input ->

printfn "Working out the value for '%A'" input

String.concat ", " [ for i in 0 .. 9 -> sprintf "%d: %s" i input ])

And using this in F# Interactive:

> Console.WriteLine(memoizedAppend("this"))

Working out the value for '"this"'

0: this, 1: this, 2: this, 3: this, 4: this, 5: this, 6: this, 7: this, 8: this, 9: this

> Console.WriteLine(memoizedAppend("this"))

0: this, 1: this, 2: this, 3: this, 4: this, 5: this, 6: this, 7: this, 8: this, 9: this

Some things to note here:

Working out the value for 'this' is only printed once, as we expcet
The generic type of memoize is computed automatically. This makes the code short and clear (once you get used to the F# syntax). This is known as automatic generalization, and is a key part of type inference and succinct coding in all typed functional languages.
The example uses double lookup - this can be changed if necessary, but I thought it instructive to keep the same structure as Pieter's sample

There will be a section on memoization and caching in the Expert F# book, in the "Techniques" chapter

Update: Here's the single-lookup version of this:

let memoize f =
    let cache = Dictionary<_, _>()
    fun x ->
        let mutable ok = Unchecked.defaultof<_>
        let res = cache.TryGetValue(x,&ok)
        if ok then res
        else let res = f x
             cache.[x] <- res
             res

.Update: here's a version that uses a single mutable reference cell holding an immutable tree-based Map value.

let memoize f =

let cache = ref Map.empty

fun x ->

match (!cache).TryFind(x) with

| Some res -> res

| None ->

let res = f x

cache := (!cache).Add(x,res)

res

don

A Sample of the Memoization Pattern in F#

Additional resources