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

recursive definition
• QUERCIA Michel (T) Math
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 1996-04-23 (18:45) From: QUERCIA Michel (T) Math Subject: recursive definition
```

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

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

```