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:  20061002 (15:29) 
From:  Diego Olivier FERNANDEZ PONS <diego.fernandez_pons@e...> 
Subject:  Re: [Camllist] More problems with memoization 
Bonjour, Quoting Jon Harrop <jon@ffconsultancy.com>: > I believe you want to "untie the knot" of recursion, creating an > higherorder, 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 higherorder 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