recursive definition

["QUERCIA Michel (T) Math" <querciam@l-carnot1.ac-dijon.fr>]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2425 bytes --]



==========================================================================  

En francais :

Il a ete explique dans un post precedent que "let rec x = f(x)"
n'est compilable que si "x" est une fonction ou si la compilation
de "f(x)" ne depend pas de "x".

Qu'est-ce qui ne va pas dans la definition de "fib" ci dessous ?

==========================================================================  

In english :

I remember a post where it was explained that "let rec x = f(x)" is   
handled
only when "x" is a function or when "f(x)" may be compiled with no   
knowledge
of "x".

So, what is wrong with the following attempt to define "fib" ?

==========================================================================  


>       Caml Light version 0.7

#                        (* +----------------------+
                            |  Fonction a memoire  |
                            +----------------------+ *)


let remember(f) =
  let t = hashtbl__new(17) in
  fun x -> try hashtbl__find t x
           with Not_found -> let y = f(x) in hashtbl__add t x y; y
;;
remember : ('a -> 'b) -> 'a -> 'b = <fun>
#


let premier = remember(fun x ->
  printf__fprintf stderr "appel %d\n" x; flush stderr;
  let y = ref(2) in
  while !y * !y < x & x mod !y > 0 do incr y done;
  !y * !y > x
);;
premier : int -> bool = <fun>
#
map premier [1;2;3;4;5;6;7;8;9;10];;
appel 10
appel 9
appel 8
appel 7
appel 6
appel 5
appel 4
appel 3
appel 2
appel 1
 - : bool list =
 [true; true; true; false; true; false; true; false; false; false]
#
map premier [1;2;3;4;5;6;7;8;9;10];;
 - : bool list =
 [true; true; true; false; true; false; true; false; false; false]
#


let rec fib = remember(fun x ->
  if x < 2 then 1 else fib(x-1) + fib(x-2)
);;
Entrée interactive:
>..............remember(fun x ->
>  if x < 2 then 1 else fib(x-1) + fib(x-2)
>).......
Ce genre d'expressions n'est pas autorisé comme membre droit d'un "let   
rec".
#quit();;

Process inferior-caml finished

==========================================================================  


PS : J'ai aussi essaye :

let rec fib(x) = let g = remember(fun x -> ...) in g(x);;

Ca marche (a la compilation) mais il n'y a pas memorisation
des resultats puisque g est reconstruite a chaque appel.

==========================================================================  


Michel Quercia
Lycee Carnot
Dijon

email = querciam@ac-dijon.fr
Cc = quercia@u-bourgogne.fr