Commençons donc par la fonction puissance réputée efficace. Ce principe de division par deux est tellement classique que je ne sais que dire.
(* Puissance efficace, suppose n ≥ 0 *) let rec puissance x n = match n with | 0 -> 1 | _ -> let y = puissance x (n/2) in if n mod 2 = 0 then y * y else x * y * y ;;

La solution la plus simple consiste ensuite à bêtement calculer la somme de la valeur des monômes.

let evaluer p x = List.fold_left (fun r m -> r + m.coeff * puissance x m.degre) 0 p ;;

Mais on peut faire un peu mieux (c'est à dire faire moins de multiplications) en s'inspirant de la règle dite de Horner. Rappelons la règle:

an xn + ⋯ + a1 x1 + a0 = (an xn−1 + ⋯ + a1) * x + a0

Puis on explicite l'évaluation :

E(an xn + ⋯ + a1 x1 + a0, X) = E(an xn−1 + ⋯ + a1, X) * X + a0

Avec les polynômes creux, l'application directe donne plus ou moins ceci (en replaçant les monômes absents par des monômes de coefficient nul)

(* Méthode dite de Horner, pdeg est le degré du monome précédant *) let rec horner pdeg r x p = match p with | [] -> if pdeg = 0 then r else horner (pdeg-1) (r*x) x [] | m::rem -> if pdeg = m.degre then horner m.degre (r + m.coeff) x rem else horner (pdeg-1) (r*x) x p ;; let evaluer p x = match p with | [] -> 0 | m::rem -> horner m.degre m.coeff x rem ;;

Mais on peut employer notre function puissance en réflechissant un peu:

let rec horner pdeg r x p = match p with | [] -> r * puissance x pdeg | m::rem -> horner m.degre (r * (puissance x (pdeg-m.degre)) + m.coeff) x rem ;;