TD/TP Caml n°3++ : Polynômes

On représente des polynômes d'entiers, a0 + a1 x + ... + an xn, sous forme "pleine" ou sous forme "creuse". La première forme correspond à un polynôme pour lequel tous les monômes sont presque tous présents. la seconde forme est privilégiée si seuls quelques monômes sont présents comme dans l'exemple qui suit.

type monome = {coef:int; degre:int};;

type polynome = Plein of int list
               |Creux of monome list;;
Par exemple, pour le polynome 3 + 5 x + 7 x3 + 4 x4, on le représentera de préférence sous la forme "pleine"
Plein [3; 5; 0; 7; 4]
Alors que le polynome 5 x2 + 8 x7 + 3 x10 sera plutot représenté sous la forme "creuse"
Creux [{coef=5;degre=2}; {coef=8;degre=7}; {coef=3;degre=10}]

Exercice 1

Ecrire une fonction qui évalue le polynôme pour une valeur donnée de x.

Exercice 2

Ecrire une fonction qui additionne deux polynômes.

Exercice 3

Ecrire une fonction qui dérive un polynôme

Exercice 4

Représenter maintenant un polynôme polymorphe pour lequel le coefficient et le degré sont des paramètres de type. C'est ce nouveau type qui sera utilisé dans la suite.

Exercice 5

En utilisant des opérateurs abstraits d'addition (++) et de multiplication (**), réécrire les fonctions d'évaluation d'un polynôme et d'addition de deux polynômes

Exercice 7

Ecrire des spécialisations de ces fonctions polymorphes au type entier vu en cours :

type entier = Zero | Succ of entier;;
Remarque : on devra réécrire l'addition de deux entiers (vu en cours) mais aussi la multiplication de deux entiers.