Programmation Dynamique

Un autre aspect amusant de l'évaluation paresseuse en Haskell c'est la facilité avec laquelle on peut faire de la programmation dynamique. L'idée est d'utiliser un tableau en haskell, via le module Data.Array, qui possède une fonction array avec un type compliqué, mais qui est simplement là pour construire un tableau à partir de bornes et d'une liste d'association indice-valeur.

unTableau :: Array Int Int
unTableau = array (0,10) [ (i,i) | i <- [0..10] ]

Imaginons qu'une suite double soit définie par la récurrence u_j^{n+1} = a u_{j+1}^n + b u_j^n + c u_{j-1}^n avec
u_0^n = 1, u_N^n = 0 et une condition initiale u0 donnée. Alors un moyen très simple de calculer la matrice représentant les valeurs de la suite est le suivant :

calculSuite u0 = tableau
 where
 tableau = array ((0,0),(nMax,mMax)) [ ( (j,n), u j n ) | i <- [0..nMax], j <- [0..mMax] ]
 u 0 _ = 1
 u j 0 = u0 ! j
 u j n = if j == nMax then 
 0
 else
 a * (tableau ! (j+1,n-1)) + b * (tableau ! (j,n-1)) + c * (tableau ! (j-1,n-1))

Ce qu'il faut remarquer c'est que la fonction qui calcule les valeurs du tableau ... accède au tableau !
Si les dépendances sont cycliques, le code ne termine pas, mais si on a montré qu'on peut effectivement faire le calcul, alors tout se passe bien. On remarque que mettre dans un tableau les valeurs correspond à enregistrer les appels à une fonction dans un tableau pour ne pas avoir à calculer plusieurs fois le même sous-arbre lors des appels récursifs.

Un avantage par rapport à un code manuel, est de ne pas avoir à gérer comment remplir le tableau : l'ordre d'évaluation est « automatique », alors que dans certain programmes dynamiques, il est pénible à mettre en place (ou du moins il faut réfléchir, et imbriquer plusieurs boucles).

Un désavantage est justement que quelqu'un qui lit le code doit avoir quelque part montré que les appels sont « cohérents » et que le programme ne va pas simplement boucler, ce qui force à mettre plus de documentation à disposition.