Re: [Caml-list] More problems with memoization

[Diego Olivier FERNANDEZ PONS <diego.fernandez_pons@etu.upmc.fr>]

     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