Discussion :

[Fractal LLG]

Bonjour

Si j'écris le programme suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let rec appartient x l = match l with
  | [] -> false
  | h::t -> (h = x) || (appartient x t);;

qui teste, comme vous l'aurez deviné, l'appartenance d'un élément à une liste, est-ce que le compilateur le reconnait comme une fonction récursive terminale? (elle l'est clairement en écrivant : )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let rec appartient x l = match l with
  | [] -> false
  | h::t -> if (h = x) then true else (appartient x t);;

------------------

Autre petite question : quelle est la complexité de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

fun x -> mem := (x::!mem) (* où mem est une 'a list ref définie dans le contexte *)

En d'autres termes, si !mem contient beaucoup d'éléments, est ce qu'en rajouter un va prendre beaucoup de temps?

Merci

Fractal

[SpiceGuid]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(h = x) || (appartient x t)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if (h = x) then true else (appartient x t)

L'opérateur or ou || est semi-stricte et cela signifie que ces deux expressions sont rigoureusement identiques pour le compilateur.

En d'autres termes, si !mem contient beaucoup d'éléments, est ce qu'en rajouter un va prendre beaucoup de temps?

Le constructeur _::_ c'est un ajout en tête.
L'ajout d'un élément en tête (consing) se fait en temps constant.
L'ajout d'un élément en queue (append) se fait en temps linéaire.

[Fractal LLG]

Oki merci

Fractal

[Garulfo]

Le truc, c'est de savoir si l'appel récursive sera bien le dernier appel avant le retour de la fonction. Ce n'est pas évident, même avec un if. C'est parce qu'un if s'évalue en forme normal et non applicatif que c'est vrai.

Tu peux toujours essayer dans un cas comme ça de provoquer un affichage et de voir ce qui se passe dans un cas où || deviendrait préfixé et tu verras qu'on perd la récursivité terminale.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
# let tracer n s =  print_int n ; print_string " - Evaluation " ; print_endline s ;; 
val tracer : int -> string -> unit = <fun>
# let rec f x n =
     match x with
     | [] -> false 
     | h::t -> ( tracer n "ou" ; (||) )
               ( tracer n "h" ; (h>0) )
               ( tracer n "f" ; f t (n+1))
  ;;
val f : int list -> int -> bool = <fun>
# f [-1;1] 1 ;;
1 - Evaluation f
2 - Evaluation f
2 - Evaluation h
2 - Evaluation ou
1 - Evaluation h
1 - Evaluation ou
- : bool = true

Essayons avec un operateur infixe déclaré sur « || »

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
# let (++) a b = (tracer 0 "ou") ; (a || b) ;;
# let rec g x n =
     match x with
     | [] -> false 
     | h::t -> ( tracer n "h" ; (h>0) ) 
               ++
               ( tracer n "g" ; g t (n+1))
  ;;
# g [-1;1] 1 ;;
1 - Evaluation g
2 - Evaluation g
2 - Evaluation h
0 - Evaluation ou
1 - Evaluation h
0 - Evaluation ou
- : bool = true

Comme tu peux le voir c'est vraiment dû à la manière d'évaluer un if ou un ||. Ce n'est pas une reconnaissance syntaxique. Ici on voit bien que le « ou » est la dernière fonction appelée d'un appel de « f » ou de « g ». Ce n'est pas récursif terminal.

Je ne vois pas un moyen simple par contre de te montrer que c'est le cas avec le « || »... en Scheme les macros sont simples à faire et il y a un mécanisme de trace automatique. C'est plus facile.

Je ne sais pas si tu vois où je voulais en venir ?