Func' programming - un blog homéopathique

Une question de cartes
Dans son billet Misères de l’analyse objet, un cas pratique, François (j’ai décidé une bonne fois pour toute de l’appeler par son prénom) montre les travers d’une approche objet naïve qui tenterait de refléter le réel dans les classes du programme. Elle mène à un code difficile à factoriser et difficile à maintenir. Le billet montre comment raffiner le concept initial, de façon itérative, jusqu’à arriver à la représentation adaptée au meilleur algorithme. François en conclut que le véritable apport de l’approche OO est l’encapsulation, qui permet d’expérimenter à l’abri d’une interface.

Dans un autre billet, je montrerai comment des langages fonctionnels gèrent la question de l’encapsulation –et peut-être aussi que certains langages objet ne font aucun cas de l’encapsulation. Dans celui-ci, je voudrais surtout montrer ce qu’est une approche fonctionnelle et comment elle se distingue d’une approche objet.

De haut en bas, de bas en haut
L’approche fonctionnelle est parfois qualifiée de "bottom-up", de bas en haut, parce que son moteur est de partir de fonctions simples, faciles à tester et assez générales pour être réutilisées dans d’autres contextes, pour construire la solution au problème. Il s’agit donc de partir de fonctions primitives ou standard et de n’y ajouter que le strict nécessaire de fonctions nouvelles, elles-mêmes aussi orthogonales que possible aux fonctions existantes.

Cette approche a de nombreux avantages : les fonctions utilisées ont déjà été optimisées et testées, et les fonctions nouvelles à chaque programme s’ajoutent progressivement au vocabulaire du développeur pour lui faciliter la vie. Comme il les réutilise, il a un intérêt réel à les optimiser et à les tester.

Le problème à traiter
Nous reprendrons dans ce billet le problème posé par François : comment comparer deux mains au poker ? Je suppose que tout le monde ici sait jouer au poker et sera d’accord avec la remarque suivante : toutes les figures reposent sur le nombre des cartes qui, dans la main, sont identiques –par le rang ou la couleur- ou se succèdent, ou les deux (la quinte flush).

Deux conséquences découlent de cette remarque : la première est qu’il nous faut une représentation des cartes qui permette de les comparer par rang et par couleur, et rien de plus. Donc une paire d’entiers fera parfaitement l’affaire. La deuxième est que la fonction split-if-not (définie dans le précédent billet) permettra de détecter la présence de toutes les figures.

Où sont passés les domestiques ?
Pour avancer dans notre programme, nous allons d’abord définir quelques petites fonctions facultatives qui nous permettront de tester au fur et à mesure nos avancées :

Code LISP :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(defun card()
  (cons (random 13) (random 4))) ; ; random renvoie un entier entre 0 (inclus) et l’argument (exclu)
 
(defun card-names () '(2 3 4 5 6 7 8 9 10 V D R 1))
(defun color-names () '(Coeur Pique Carreau Trefle))
 
(defun name (card)
  (cons (nth (car card) (card-names)) ; ; (nth n liste) renvoie le énième argument de la liste
	(nth (cdr card) (color-names)))) ; ; cons peut être appelé avec 2 atomes –regardez le résultat par vous-mêmes
 
(defun hand() ; ; je vous l’ai dit, LISP n’est pas fonctionnel ; en voici un exemple :
  (let ((h nil))
    (dotimes (x 5) ; ; faire 5 fois (x prend les valeurs 0, 1 … 4)
      (push (card) h)) ; ; insère (card) au début de h
    h))
 
(defun ranks (hand)
  (mapcar #'car hand))
(defun colors (hand)
  (mapcar #'cdr hand))

Voilà, les domestiques sont arrivés, passons à la suite.

Déterminer les figures
Commençons par le gros morceau : comment détecter la présence d’un carré, d’un full, etc.
Tirons d’abord une main :

CL-USER> (setf h (hand))
((7 . 0) (9 . 1) (3 . 3) (0 . 1) (3 . 0))
CL-USER> (mapcar #'name h)
((9 . COEUR) (V . PIQUE) (5 . TREFLE) (2 . PIQUE) (5 . COEUR))

Nous n’aurons besoin que des rangs, de toute façon :

CL-USER> (setf r (ranks h))
(7 9 3 0 3)

Trions notre main :

CL-USER> (setf sr (sort r #'<))
(0 3 3 7 9)

Puis regroupons les cartes identiques :

CL-USER> (setf gsr (split-if-not #'= sr))
((0) (3 3) (7) (9))

Enfin nous retrions ce résultat pour savoir quelle est la figure la plus importante :

CL-USER> (setf sgsr (sort gsr (lambda (x y) (> (length x) (length y)))))
((3 3) (0) (7) (9))

Pour récapituler :
NB : :key précède un argument facultatif et nommé de sort, appliqué aux éléments avant d’appliquer la fonction de comparaison. (sort liste #’> :key #’length) = (sort liste (lambda (x y) (> (length x) (length y))))

Code LISP :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
(defun process-same-ranks (hand)
  (sort (split-if-not #'= (sort (ranks hand) #'<)) #'> :key #'length))

Pour détecter une couleur, le principe est le même :

Code LISP :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
(defun process-same-colors (hand)
  (sort (split-if-not #'= (sort (colors hand) #'<)) #'> :key #'length))

Et pour détecter une suite, ce n’est pas bien différent !

Code LISP :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
(defun process-succ-ranks (hand)
  (sort (split-if-not (lambda (x y) (= (1+ x) y)) (sort (ranks hand) #'<)) #'> :key #'length))

Il est donc très facile de factoriser :

Code LISP :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
(defun process-hand (split-pred rank-or-color hand)
  (sort (split-if-not split-pred (sort (funcall rank-or-color hand) #'<)) #'> :key #'length))

Pas encore tiré d’affaire
Il reste encore à comparer les deux mains, même si nous avons beaucoup avancé. Nous allons devoir calculer un score synthétique et comparable, de quelque façon que la main ait été traitée.

Pour les figures reposant sur des cartes de rang identique, la longueur de la figure la plus longue dans la main ne suffit pas à déterminer le score. Dans le cas présent (une paire), il pourrait également y avoir une seconde paire dans la main. Il faut donc également tenir compte de la longueur totale de la liste : si la première figure est une paire et que la liste des figures compte 4 éléments, il ne peut pas y avoir de deuxième paire. Pour avoir un score croissant qui corresponde à l’ordre des mains au poker, on peut multiplier la longueur de la première figure par (longueur maximale de la liste – longueur de la liste). Dans notre exemple, le score de la figure est 2 * (5 – 4) = 2.
Pour l’ensemble des figures, on a : paire = 2, double paire = 4, brelan = 6, full = 9, carré = 12 avec :

Code LISP :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
(defun score-id-ranks-figure (phand)
  (* (length (car phand)) (- 5 (length phand))))

Il suffit maintenant d’intercaler la quinte et la couleur (7 et 8 respectivement) et d’ajouter la quinte-flush (15). Vous devriez pouvoir maintenant comprendre le code suivant :

Code LISP :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
(defun synthetic-score (hand)
  (let ((id-ranks (process-hand #'= #'ranks hand))
	(succ-ranks (process-hand (lambda (x y) (= (1+ x) y)) #'ranks hand))
	(id-colors (process-hand #'= #'colors hand)))
    (let ((color (if (= 1 (length id-colors)) 8 0))
	  (straight (if (= 1 (length succ-ranks)) 7 0))
	  (other-figures (* (length (car id-ranks)) (- 5 (length id-ranks)))))
      (max (+ color straight) other-figures))))

Sommes-nous vraiment tirés d’affaire ?
Malheureusement, deux mains peuvent avoir un score identique, et il faut les départager. Heureusement, il ne nous reste presque plus rien à faire. Il suffit de donner, à côté du score synthétique, la main classée par rangs identiques. Comparer ces deux listes pour départager ne pose pas de problème :

NB: cond ressemble au switch d'autres langages. Il prend en argument un nombre variable de listes, dont le premier élément est une condition, le deuxième une expression à évaluer si la condition est vraie

Code LISP :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
(defun disambiguate (a b)
  (cond 
    ((null a) 'even)
    ((< (caar a) (caar b)) T)
    ((< (caar b) (caar a)) Nil)
    (T (disambiguate (cdr a) (cdr b)))))

Conclusion
Le billet est long mais le code est court : nous avons créé quatre fonctions non-standard : process-hand et synthetic-score, spécifiques au problème, split-if-not qui pourra nous resservir telle quelle, et disambiguate, qui aurait dû être généralisée : une fonction lexicographic-order-compare devrait être disponible dans notre arsenal de fonctions de base.

Exercices :
- écrire la fonction lexicographic-order-compare
- faites une recherche sur les différents types d’argument des fonctions de LISP (optionnels, à mot-clé, etc.)
- comment auriez-vous écrit ce programme dans votre langage favori ?
- proposez une amélioration des fonctions de ce billet