From: "QUERCIA Michel (T) Math" <querciam@l-carnot1.ac-dijon.fr>
To: "'caml-list@pauillac.inria.fr'" <caml-list@pauillac.inria.fr>
Subject: recursive definition
Date: Mon, 22 Apr 96 12:16:00 PDT
==========================================================================
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