Dojo

Un pas trop grand

Hier au Dojo, en présentant un Kata, j'ai fait un pas trop large et je suis retombé d'une façon telle que j'ai quelque peu raté la figure que je voulais exécuter.

C'était une figure à propos d'une fonction récursive. Le processus d'écriture de fonctions récursives a un aspect qui peut paraître magique. Il y a presqu'à chaque fois un moment où la fonction se met en place avec une sorte de déclic. Une fois qu'elle est en place, tout s'éclaire, on ne peut plus voir le code tout à fait comme avant le déclic, un peu comme ces images en trompe-l'oeil, une fois l'astuce révélée.

Par exemple : imaginons que je mette au point une fonction longueur, capable de calculer la longueur d'une liste, sans écrire de tests (j'ai dit imaginons; pour moi écrire du code sans tests, ce serait comme partir au travail en pyjama). J'en suis là de mon code -- nous sommes en Haskell :

longueur [] = 0

La longueur d'une liste vide est zéro. Maintenant, j'aimerais écrire la suite de la fonction : la longueur d'une liste non vide, c'est, voyons, c'est au moins 1 plus.. plus la longueur de la même liste une fois privée de son premier élément. Alors j'écris :

longueur (x:xs) = 1 + longueur xs

Que suis-je en train de faire ? Je mets au point une fonction; au cours de cette mise au point, j'en appelle à la fonction même que je suis en train de mettre au point. Je me dis "si longueur marchait correctement, je pourrais l'utiliser ici, dans l'expression 1 + longueur xs". Je fais cela, et soudain pouf! la fonction fonctionne. Ca paraît magique : c'est comme s'il suffisait simplement de se figurer que la fonction marche, de l'utiliser, et voilà : la fonction marche !

Du calme. Repassons la séquence au ralenti -- avec des tests. Tout d'abord :

longueurListeVideEgaleZero =  0 ~=? longueur []

puis

longueur [] = 0

A ce point, une partie de la fonction longueur est, en fait, au point : je sais que si je l'applique à une liste vide, j'obtiendrais zéro. Je peux donc m'aventurer à écrire :

longueurListeUnElementEgaleUn =  1 ~=? longueur ["foo"]

Le test plante : Program error: pattern match failure: longueur instNum_v32 ["foo"] Traduction : la fonction longueur ne sait pas du tout que faire d'une liste à un élément. Apprenons-lui :

longueur []  = 0

longueur [_] = 1

Le test passe. Ma fonction est au point pour deux cas de figure : vide,1 élément. Encore un peu d'audace :

longueurListeNElementsEgaleN =  2 ~=? longueur ["foo", "bar"]

Comme l'indique ce test, l'exemple est 2, mais l'intention est N. 0,1,N : nous y sommes, c'est la trilogie classique des tests que l'on doit effectuer à propos d'une fonction portant sur un conteneur.

Nouvelle complainte du compilateur : Program error: pattern match failure: longueur instNum_v32 ["foo","bar"] Vous connaissez l'histoire.

Allons-y doucement. Conscients de nos limite, ajoutons, avec pusillanimité, un "fake it" supplémentaire :

longueur []    = 0

longueur [_]   = 1

longueur [_,_] = 2

Les tests passent, mais on sent bien que ça ne va pas pouvoir continuer comme ça très longtemps. Si on développait ? (au sens mathématique du terme) Puisque longueur est au point pour les cas 0 et 1, je peux écrire en toute tranquilité :

longueur []  = 0

longueur [x] = 1

longueur [x,y] = 1 + longueur [y]

Je remplace les jokers par des variables pour clarifier, et parce que l'utilisation de jokers dans la partie droite de l'égalité n'a pas de sens. Les tests passent. Je remarque que :

longueur []  = 0

longueur [x]   = 1 + longueur []

longueur [x,y] = 1 + longueur [y]

Les tests passent. Si j'osais, je dirais qu'en général, sauf quand elle est vide, la longueur d'une liste, c'est 1 plus la longueur de cette liste privée de son premier élément. Ce qui s'écrit :

longueur []  = 0

longueur (x:xs) = 1 + longueur xs

J'ai des cas de test pour 0,1 et 2. Qu'est-ce qu'on risque ?

Les tests passent. Je change mon dernier test pour voir :

longueurListeNElementsEgaleN =

    4 ~=? longueur ["ah", "ah", "only", "serious"]

Les tests passent. Et il n'y a rien de magique dans le processus : j'ai certes fait appel à ma fonction alors qu'elle était en chantier, mais c'était à chaque fois sur les parties du domaine de valeur pour lesquelles la fonction était déjà au point. Sans test, ça parait douteux, loufoque (comme un type qui serait venu au travail en pyjama). Mais ça n'est pas magique. Avec TDD c'est simplement possible.

Bon. Où veux-je en venir ? Hier au Dojo, en présentant un Kata, j'ai fait un pas trop large et je suis retombé d'une façon telle que j'ai quelque peu raté la figure que je voulais exécuter. Le pas a fonctionné, je suis retombé sur mes pattes (un peu comme Calvin, qui transforme un trébuchement en roulade et se relève en faisant: "TaDaa!") mais là, Antoine, qui écoutait très sérieusement la présentation à levé la main.

Le kata portait sur LAGS (Louez votre Avions et Gagnez des Sous. Allez voir ce problème ou bien la suite de ce post va s'autodétruire dans les 10 secondes).

Fast Forward, Stop, Rewind, Stop, Play. J'en suis au moment où mon dernier test affirme que si un carnet d'ordre contient des demandes de locations incompatibles entre elles, alors la valeur de cette liste est le prix de location le plus elevé :

valeurAvecNLocationsIncompatiblesEgaleMaxPrixLocation =

    14 ~=? valeur [Location "AF515" 0 5 10,

		   Location "BA01" 3 7 14,

		   Location "CX7"  4 3 7]

Le test passe car :

data Location = Location { idt : String, debut, duree, prix : Integer }

fin :: [Location] -> Integer

fin l = debut l + duree l

valeur :: [Location] -> Integer

valeur [] = 0

valeur (l:ls) = max (prix l) (valeur ls)

Alors je passe ambitieusement au cas suivant :

valeurAvecNLocationsCompatiblesEgaleValeurMeilleurPlan =

    18 ~=? valeur [Location "AF514" 0 5 10,

		   Location "BA06"  3 7 14,

		   Location "AF515" 5 7 7,

		   Location "C0O" 6 7 8]

Il ne s'agit pas seulement de prendre la meilleure location possible : lorsque plusieurs locations peuvent être enchaînées il faut trouver l'enchaînement le plus rentable, le "plan" de locations pour lequel la somme des locations effectuées serait la plus elevée. Dans ce cas de test, AF514 puis AF515 ou bien AF514 puis C0O sont deux plans possibles : le premier rapporte 10 + 7 le second 10 + 8 et c'est donc 18 la bonne réponse.

Comment faire ? Je remarque qu'étant données une location et les suivantes, ce dont on doit "tirer le max" ce n'est pas simplement le prix de la première location, mais la somme des locations qu'on pourrait enchaîner à cette première location. Je fais donc un "extract method" :

valeur [] = 0

valeur (l:ls) = max (valeurPlan l ls) (valeur ls)


valeurPlan :: Location -> [Location] -> Integer

valeurPlan l _ = prix l

Je me suis contenté de "sortir" le calcul de la valeur qui est à comparer avec la valeur de la suite de la liste. Le dernier test -- et celui-là seul -- continue de ne pas passer. Je suis au milieu de la paroi, j'ai juste lâché une main.

Ralenti. C'est là où je manque mon pas de peu.

La valeur d'un plan qui commencerait par la location l, c'est le prix de l plus le prix de certaines locations issues de la suite de la liste, mais pas n'importe quelles locations : seules celles qui peuvent débuter après l. Et parmi celles-ci pas n'importe laquelle : celle qui, si on la continuait avec d'autres locations de la liste, offrirait la meilleure valeur. Il faut, pour calculer valeurPlan (qui participe au calcul de valeur) trouver le meilleur enchaînement; et ce meilleur enchaînement possible, c'est la fonction valeur qui peut le donner.

Vous voyez l'astuce ? Je sais que valeur n'est pas entièrement au point (la preuve : je travaille dessus), mais je vais faire comme si elle marchait, pour mettre au point valeurPlan, qui permettra de finir valeur. Un petit vertige me prend. Ne pas regarder en bas. J'écris :

valeurPlan :: Location -> [Location] -> Integer

valeurPlan l ls = prix l + valeur suitesPossibles

   where suitesPossibles = filter (peutSuivre) ls

         peutSuivre x = debut x >= fin l

Ici, pour un seul nouveau test, trois nouveaux concepts entrent en scène :

• la relation de compatibilité (temporelle) entre les locations (peutSuivre);
  
• le filtrage par application d'une fonction à une liste;
  
• la récursion mutuelle : valeur <-> valeurPlan;
  

Un pas d'une telle longueur, ce n'est pas du tout "kata-friendly". Pas naturel. Trop de code pour un test.

Mais bon. Je connais le passage. Je lance le pied, bien loin.. Hoooooop-là ! Les tests passent. Tadaa ! Mais Antoine à lâché prise, et il est en bas.

Exercice 1.19.2 : en vous inspirant de la décomposition effectuée plus haut dans l'exemple "longueur", proposez à Christophe une décomposition naturelle qui lui permettrait de démystifier ce passage de la mise au point mutuelle de "valeur" et "valeurPlan".