Commençons donc par la fonction puissance, dans sa version 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

Avec les polynômes creux, l'application directe donne plus ou moins ceci (en remplaç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édent *)
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