Browse thread
More problems with memoization
-
Diego Olivier FERNANDEZ PONS
-
Jon Harrop
- Martin Jambon
- Diego Olivier FERNANDEZ PONS
- Tom
-
Jon Harrop
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2006-10-02 (15:29) |
From: | Diego Olivier FERNANDEZ PONS <diego.fernandez_pons@e...> |
Subject: | Re: [Caml-list] More problems with memoization |
Bonjour, Quoting Jon Harrop <jon@ffconsultancy.com>: > I believe you want to "untie the knot" of recursion, creating an > higher-order, auxiliary fibonacci function fib_aux that accepts the > recursive call as an argument: > > # let rec fib_aux fib = function > | 0 | 1 as n -> n > | n -> fib(n - 1) + fib(n - 2);; > val fib_aux : (int -> int) -> int -> int = <fun> > [...] > You can recover the ordinary fibonacci function using the Y combinator: [...] > You can write a higher-order memoization function that accepts an argument > with the type of fib_aux: > # memoize fib_aux 35;; > - : int = 9227465 Your solution is similar to Andrej Brauer's one which is exactly what I was trying to avoid because it is too much intrusive. When you break the recursion in two functions you change the type of [fib] from [fib : int -> int] to [fib : (int -> int) -> int -> int)]. In my first example you keep the type of [fib] and add a second function [fib_mem]. You can use anyone indifferently and hide the latter with the .mli val fib : int -> int = <fun> val fib_mem : int -> int = <fun> When you compare your solution with what I am trying to do you see there is a big difference in locality and transparency let rec fib = function | 0 -> 0 | 1 -> 1 | n -> fib (n - 1) + fib (n - 2) transformed into let rec fib = function | 0 -> 0 | 1 -> 1 | n -> fib_mem (n - 1) + fib_mem (n - 2) and fib_mem = make_mem fib The latter could even be done automatically by a source to source transformation (if it worked). Diego Olivier