Université Louis Pasteur
LICENCE 2ème année

 
Travaux Pratiques de
Programmation Fonctionnelle
(sujet n°1)



Quelques informations utiles sur les outils disponibles.

(a) L'interpréteur

   L'interpréteur se lance par la commande ocaml. L'invite de l'interpréteur est #. Pour sortir de l'interpréteur faire Ctrl+D. Afin de ne pas perdre vos programmes, vous pouvez taper vos expressions Ocaml dans un fichier .ml,  par exemple TP1.ml, et les utiliser ensuite dans l'interpréteur en tapant la directive #use "TP1.ml";; (attention, ici le # n'est pas l'invite de l'interpréteur, mais doit être tapé). Dans un fichier vous pouvez mettre des commentaires entre (* et *).

(b) Le compilateur
          
Un condensé d'une page html sur l'utilisation du compilateur se trouve ici.


I. Evaluation.


(a) En utilisant l'interpréteur, évaluer les expressions suivantes (lire la réponse de l'interpréteur) :
  • 1+2*3;;
  • 1.0 * 2;;
  • (1 < 2);;
  • int_of_char('a');;
  • "Photo"^"graph";;
  • let pi = 4.0 *. atan 1.0;;
  • let carre x = x *. x;;
  • carre(sin pi) +. carre(cos pi);;
(b) Même chose avec ces expressions :
  • 7 mod 3;;
  • 2. ** 10.;;
  • (4.6+.0.2) < 4.7;;
  • 'a' < 'b';;
  • "aab" < "aac";;
  • if 3*5 < 16 then "yes" else "no";;
  • let test = ("caml" > "autre langage");;
  • if test then 1+1 else 0;;
  • if true then 't' else "false";;
(c) Evaluer ces expressions utilisant le mot-clef function et la construction let ... in ... :
  • (function x -> 2*x+1) 3;;
  • let x = 3 in 2*x+1;;
  • let x = 2 in let y = 5 in x*y;;
  • let (x,y) = (2,5) in x*y;;
  • let x = 2 in let y = x+3 in x*y;;
(d) Définir la fonction carré d'un nombre réel dans un fichier carre.ml puis appliquer cette fonction dans l'interpréteur en utilisant la directive use.

(e) En considérant les couples de float comme des nombres complexes, écrire les fonctions de base sur les nombres complexes :
re (partie réelle), im (partie imaginaire), add (addition), sub (soustraction) et mul (multiplication). (On rappelle que (a+ib)+(a'+ib')=(a+a')+i(b+b'), (a+ib)-(a'+ib')=(a-a')+i(b-b') et (a+ib)×(a'+ib')=(aa'-bb')+i(a'b+ab').)


II. Décomposition fonctionnelle d'un problème.

(a) Taper les fonctions suivantes :
  • longueur (longueur d'un segment AB du plan)
  • circonference (circonference d'un cercle)
  • cercle_circonscrit (cercle circonscrit à 3 points)
où une droite est définie par les coefficients a (pente) et b (ordonnée à l'origine) de l'équation y = ax+b.
Cercle circonscrit

(b) Appliquer les fonctions de la question (a) de façon à vérifier les propriétés suivantes :
 
      Soient les points O(0,0), A(cos(-π/4),sin(-π/4)), B(cos(π/2),sin(π/2)) et C(cos(π/8),sin(π/8)). Alors
  • la longueur des segments [O,A], [O,B] et  [O,C] est 1.
  • la circonférence du cercle circonscrit à A, B et C est 2π.
(c) Taper les fonctions suivantes :
  • intersection_vide (teste si l'intersection de 2 intervalles est vide)
  • union_inter (plus petit intervalle contenant 2 intervalles)
  • contigus3 (contiguïté de 3 intervalles)
où un intervalle [a,b] est défini par le couple (a,b) de ses bornes inférieures (a) et supérieures (b) et en convenant que l'intervalle est vide si a>b.

(d) Appliquer les fonctions de la question (c) de façon à montrer les propriétés suivantes :
  • l'intersection de [2,4] et [1,2] est non vide.
  • l'intersection de [4,5] et [1,2] est vide.
  • le plus petit intervalle contenant [1,2] et [4,5] est [1,5].
  • les intervalles [1,2], [4,5], [2,4] sont contigus.
(e) Reprendre les questions (a) et (b) en définissant une droite par les 3 coefficients a,b,c de l'équation ax+by+c=0.

(f) Reprendre la question (c) et (d) en définissant un intervalle (non vide) par le couple (a,b) ou (b,a) de ses bornes inférieures (a) et supérieures (b).
 

III. Récursivité.

(a) Définir une fonction nbbits1 qui, étant donné un entier positif n, calcule le nombre de bits à 1 dans la représentation en base 2 de n. Exemple : nbbits1 5 = 2.

(b) Définir une fonction base2 qui, étant donné un entier positif n, retourne la représentation en base 2 de n (sous la forme d'une chaine de caractères). Exemple : base2 5  = "101".

(c) Rechercher les informations sur le module String à partir du manuel de référence de Ocaml de façon à trouver les fonctions qui permettent de connaître la longueur d'une chaîne de caractère ainsi que l'extraction d'une sous-chaîne.
  1. Ecrire une fonction qui inverse une chaine de caractères. Exemple : "CAML" sera transformé en "LMAC".
  2. Ecrire une fonction qui reconnaît les palindromes, comme "bob" ou "eluparcettecrapule".
(d) Taper les fonctions suivantes :
  • puissance (calcul de x^n)
  • pgcd (plus grand commun diviseur de 2 nombres entiers)
  • fib (terme de la suite de Fibonacci) (la suite de Fibonacci peut être définie comme suit : fib(0) = 0, fib(1)=1, fib(n+2) = fib(n+1)+fib(n))
  • premier (test de primalité)
(e) La directive #trace permet de tracer l'exécution d'une fonction. Après que cette directive a été tapée, tous les appels à la fonction sont "tracés" : cela signifie qu'à chaque appel, l'argument et le résultat sont affichés. Cette directive est intéressante pour analyser le comportement opérationnel d'une définition récursive. Essayer cette directive avec la fonction fib en tapant #trace fib;; puis fib(3);;.

(f) On cherche à estimer la complexité de la fonction fib. La complexité d'un programme est le nombre d'opérations élémentaires effectuées lors de son exécution, en fonction de la taille des données. Définir une fonction récursive  nb_add_fib qui, étant donné un entier n, compte le nombre d'additions effectuées par l'appel fib(n). Pour un entier n quelconque, quel est le nombre total d'additions effectuées dans le calcul de fib(n).

(g) On peut réduire drastiquement la complexité de la fonction fib en la définissant autrement. Proposer une autre définition récursive pour caculer les termes de la suite de Fibonacci et réécrire la fonction nb_add_fib pour cette nouvelle version. Indication : calculer deux termes successifs en une fois.


IV. Constructeurs de types * et ->, fonctionnelles et fonctions d'ordre supérieur.

(a) Inventer des valeurs ou fonctions dont le type est :
(b) Taper les fonctions suivantes (vues en TD) :
(c) Appliquer les fonctions de la question (b) de façon à montrer les propriétés suivantes :
Utiliser les fonctions dérivables sur R que sont :  u(x) = 3x2+1 dont la dérivée est 6x, et v(x) = sin(x) dont la dérivée est cos(x). On a (v o u)'(x) = u'(x) . v'(u(x)) = 6x . cos(3x2+1).

(d) Ecrire le programme sigma qui calcule la somme des n premiers termes d'une suite u (vu en TD).

(e) Appliquer la fonction sigma de la question (d) pour :


[Page réalisée par Eric Violard]