Alex Rivera | Logout

Dynamic programming in F#

Asked 2011-11-02T18:41:02.357
10

What is the most elegant way to implement dynamic programming algorithms that solve problems with overlapping subproblems? In imperative programming one would usually create an array indexed (at least in one dimension) by the size of the problem, and then the algorithm would start from the simplest problems and work towards more complicated once, using the results already computed.

The simplest example I can think of is computing the Nth Fibonacci number:

int Fibonacci(int N)
{
    var F = new int[N+1];
    F[0]=1;
    F[1]=1;
    for(int i=2; i<=N; i++)
    {
        F[i]=F[i-1]+F[i-2];
    }
    return F[N];
}

I know you can implement the same thing in F#, but I am looking for a nice functional solution (which is O(N) as well obviously).

f# functional-programming
Edit
Report

1 Answer

7

Tomas's answer is a good general approach. In more specific circumstances, there may be other techniques that work well - for example, in your Fibonacci case you really only need a finite amount of state (the previous 2 numbers), not all of the previously calculated values. Therefore you can do something like this:

let fibs = Seq.unfold (fun (i,j) -> Some(i,(j,i+j))) (1,1)
let fib n = Seq.nth n fibs

You could also do this more directly (without using Seq.unfold):

let fib =
    let rec loop i j = function
    | 0 -> i
    | n -> loop j (i+j) (n-1)
    loop 1 1
answered 2011-11-02T19:17:29.313

Your Answer