17/07/2007

[F#] Petit exercice paresseux.

Sur un forum consacré aux langages fonctionnels, quelqu'un a proposé un petit exercice. Il fallait trouver tous les ensembles d'entiers naturels dont la somme vaut n. J'ai proposé la solution suivante en F#. Elle utilise les compréhensions de listes et je la trouve plutôt élégante (presqu'autant que son équivalent Haskell) :

let sums n =
  let rec sumrec = function
   | 0, _ -> [[]]
   | n, m -> [for i in 1 .. min n m ->> [for j in sumrec((n - i), i) -> i :: j]]
  sumrec(n, n)

La compréhension de ce code est laissée à la discrétion du lecteur. :) Il est à noter que dans une compréhension, le -> permet d'ajouter des éléments, tandis que le ->> ajoute le contenu de la liste qui suit (en append).

On se rend compte facilement que la fonction n'est pas optimale : de nombreux calculs sont effectués plusieurs fois. Une solution est d'utiliser de la programmation dynamique. Don Syme présente sur son blog une technique générique, et assez intéressante, pour mémoriser les résultats intermédiaires. Je vais présenter ici une autre méthode, plus originale, mais qui ne fonctionne pas partout.

Les développeurs Haskell ont l'habitude de l'évaluation paresseuse. Le concept est d'évaluer une expression que lorsqu'elle est effectivement utilisée. Cela permet d'écrire ce genre de code : "let my_if cond v1 v2 = if cond then v1 else v2", v1 étant évalué seulement si la condition est vraie. Cela permet aussi de définir et manipuler une structure de donnée infinie (par exemple, stocker l'ensemble des entiers naturels).

La fonction récursive donnée plus haut dépend de deux arguments : n et m. Il est donc possible de définir un tableau 2D de taille n * m, dont chaque case contient le résultat de la fonction. Dans certains langages, on initialiserait le tableau avec une valeur par défaut et on utiliserait le tableau comme espace de stockage de résultats, en faisant moult effets de bord. Je propose ici une version fonctionnelle pure, qui ne calcule que les cases du tableau nécessaires :

let sums n =
  let rec a = Array2.init (n+1) (n+1) init
  and init k l =
    lazy if k = 0 then [[]]
          else [for x in 1 .. min k l ->> [for xs in a.[k-x, x].Force() -> x :: xs]]
  a.[n,n].Force()

Le mot-clé lazy indique que l'expression qui suit doit paresseuse (donc, calculer seulement quand on la demande). La méthode Force() sert à accéder à la valeur d'une expression paresseuse. L'originalité de ce code, c'est que le tableau a est mutuellement récursif avec sa fonction d'initialisation.

Une fois le tableau initialisé (mais rien n'est encore calculé), on accède juste à la case (n, n). Pour renvoyer la valeur, les calculs nécessaires (et seulement ceux-là) sont effectués.

Pour les développeurs Caml qui sont encore sceptiques : convertissez la fonction ci-dessus en Caml. Ma tentative a multiplé le nombre de lignes par 3... et ne marchait pas. En effet, la récursion mutuelle entre une valeur et une fonction n'est pas autorisée dans ce cas-là. Pour les sceptiques qui n'utilisent pas un langage fonctionnel : convertissez ma fonction dans votre langage (en conservant la même logique, hein : je sais que l'on peut différemment et aussi efficacement)... et on va rigoler. :)