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