Laurent Le Brun

On his blog, Don presented a way to do generic memoization. Pure functions always return the same value when called with the same input. So it's sometimes useful to memoize results and avoid computing the same thing several times.

Generic memoization

Here is another way to memoize recursive functions. This version does not have warnings when the function is recursive and it might be easily be ported to OCaml.

[fsharp]
let rec cache f =
  let h = HashTable.Create()
  let rec fct x =
    if not (h.Contains x) then h.[x] <- f fct x
    h.[x]
  fct

Functions you want to memoize need to take an extra argument. This argument is a function that you call instead of using recursion. For instance:

[fsharp]
let fibo' fibo x =
  if x < 2 then 1
  else fibo (x - 1) + fibo (x - 2)

let fibo = cache fibo'

A more concise notation can be:

[fsharp]
let fibo = cache <| fun fibo x ->
  if x < 2 then 1
  else fibo (x - 1) + fibo (x - 2)

This is quite interesting since you need to change only one line from the naive version.

Function statistics

If you don't know if memoization is useful or not, you can use a similar tip to display calls statistics. For instance, here's my stats function:

[fsharp]
open System.Collections.Generic

let max2 (x: KeyValuePair<_,_>) (y: KeyValuePair<_,_>) =
    if x.Value > y.Value then x
    else y

let print_details (h: (_, int) HashMultiMap) =
    printfn "%d different inputs." <| Seq.length h
    printfn "Called %d times." (h |> Seq.fold (fun x y -> x + y.Value) 0)
    let m = Seq.fold1 max2 h
    printfn "Most frequent input (%d times): %A." m.Value m.Key

let rec stats f =
    let h = HashTable.Create 100
    let n = ref 0
    let rec fct x =
        match h.TryFind x with
          | None -> h.[x] <- 1
          | Some v -> h.[x] <- v + 1
        incr n
        let res = f fct x
        decr n
        if !n = 0 then print_details h
        res
    fct

Then you only need to replace cache by stats to disable memoization and display statistics.

[fsharp]
let fibo = stats <| fun fibo x ->
  if x < 2 then 1
  else fibo (x - 1) + fibo (x - 2)

[fsharp]
> fibo 20;;
21 different inputs.
Called 21891 times.
Most frequent input (6765 times): 1.
val it : int = 10946

When the number of inputs is low, and when some inputs are used very often, then memoization may greatly improve speed.

Dynamic programming

Here is a solution for the knapsack problem, using dynamic programming. This is very easy to do thanks to the previous cache function.

[fsharp]
let data = [(1, 1); (3, 4); (4, 5); (7, 10)]

let rec knapsack = cache <| fun knapsack weight ->
  data |> List.filter (fun (w, _) -> w <= weight)
       |> List.map (fun (w, v) -> v + knapsack (weight - w))
       |> List.fold_left max 0

Data is a list of objects (weight * value). knapsack n returns the maximum value you can get when total weight <= n.