Take this naive definition of Fibonacci sequence:
let rec fib n = if n < 2I then 1I else fib (n-1I) + fib (n-2I)
*Good*: correct, easy to write. *Bad*: performance. Calculates
the same values over and over again.
How about saving up the results? There is this function
I got from Don Syme's blog:
open System.Collections.Generic let memoize f = let cache = Dictionary<_, _>(); let compute x = let res = f x in (cache.[x] <- res; res); fun x -> if cache.ContainsKey(x) then cache.[x] else compute x
Can we use this to patch up Fibonacci? Well, not directly. Test it.
memoize fib 30 is hardly faster than fib 30. Why? Obviously,
since the recursive calls are not cached.
The easiest way to work around that is to lambda-abstract the recursion
from fib. It is not as fancy as it sounds. Simply do this (and notice
there's no more rec in let):
let rfib self n = if n < 2I then 1I else self (n-1I) + self (n-2I)
Introduce a fixed-point combinator:
let rec fix f x = f (fix f) x
In Haskell that would be simply
fix f = f (fix f)
But the following does not work (think about the reason).
let rec fix f = f (fix f)
Now, the naive Fibonacci function can be expressed as
let fib = fix rfib
However, by providing a memoizing fixed-point memofix, its performance
can be drastically improved:
let memofix f = let rec g = memoize (fun x -> f g x) in g let fib = memofix rfib
Below is Problem 2 again from Project Euler, just to show it works with
this machinery. The solution is hardly the best one for this particular
problem. But recursive memoization is natural in other dynamic
programming contexts.
#light open System.Collections.Generic let memoize f = let cache = Dictionary<_, _>(); let compute x = let res = f x in (cache.[x] <- res; res); fun x -> if cache.ContainsKey(x) then cache.[x] else compute x let memofix f = let rec g = memoize (fun x -> f g x) in g let fib = let f self n = if n < 2I then 1I else self (n-1I) + self (n-2I) in memofix f let euler_0002 = Seq.init_infinite (fun x -> BigInt x) |> Seq.map fib |> Seq.filter (fun x -> x % 2I = 0I) |> Seq.take_while ((>) 4000000I) |> Seq.sum printfn "%A" euler_0002