A Sample of the Memoization Pattern in F#
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 (note "out" arguments of .NET methods can be returned as F# tuple values since F# 1.9)
let memoize f =
let cache = Dictionary<_, _>()
fun x ->
let ok,res = cache.TryGetValue(x)
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
