This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

More problems with memoization
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2006-10-02 (15:29) From: Diego Olivier FERNANDEZ PONS 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

```