L’Origami, art du pliage, permet de transformer une simple feuille en une grue, un canard ou un brontosaure –art poétique, donc, qui fait émerger de la virginité d’une page un monstre depuis longtemps disparu ou le vol d’un oiseau. Peut-être que notre activité –à nous autres programmeurs- n’a pas pour le grand public l’attrait oriental de cette discipline épurée et pourtant ! ne consiste-t-elle pas à faire émerger du chaos d’interminables séquences de bits des structures vivantes et disciplinées ?
L’art du pliage
C’est dans cet état d’esprit que je voudrais aujourd’hui illustrer l’art du pliage… des listes. Nous répèterons les gestes constitutifs de cet art comme autant de katas pour en percevoir l’extrême versatilité.
Il existe essentiellement deux formes de pliage : de gauche à droite, et de droite à gauche. De gauche à droite, on pose d’abord un pan du tissu sur la table, puis on ramène le tissu, pli par pli. De droite à gauche, on tient le tissu à la main et on l’attire vers soi, pour ne le déposer qu’à la fin sur la table. Pour plier une liste, également, on suit un ordre ou l’autre : il nous faut une fonction qui décrive le pli, une valeur initiale qui tient lieu de table et une liste, enfin, notre tissu. En voici la transcription en code
N.B : pour les rudiments de Haskell nécessaires à la lecture de ce billet, voir le précédent.
| Code Haskell : | Sélectionner tout |
1 2 3 4 5 6 7 | -- foldl : fold en anglais, plier en français ; l pour left : de gauche à droite foldl _ i [] = i --il n’y a plus de morceau à plier, on donne la liste pliée foldl f i (x:xs) = foldl f (f i x) xs --on replie sur la valeur initiale le prochain pan de la liste -- foldr : fold right, de droite à gauche foldr _ i [] = i -- arrivés au bout de la liste, nous la posons sur la table foldr f i (x:xs) = f x (foldr f i xs) --nous plions le premier morceau de la liste sur le reste de la liste à plier |
Quelques figures simples
Regardons un peu ce que l’on peut faire avec ces deux gestes simples et des fonctions primitives :
copy = foldr ( : ) [] --le constructeur de liste, qui est un opérateur, est placé entre parenthèse pour être utilisé comme une fonction
length = foldr (\x y -> 1+y) 0 --longueur de la liste
remove elem = foldr (\x y -> if x == elem then y else x:y) [] --retirer un élément de la liste
sum = foldr (+) 0 --somme
product = foldr (*) 1 --produit
append a b = foldr ( : ) b a --concaténer deux listes
map f = foldr (( : ) . f) [] --appliquer une fonction à une liste
La direction du pli ne compte pas toujours, mais souvent: Prenez par exemple ce joli bout de code :
N.B : flip intervertit l’ordre des arguments d’une fonction : flip f = \x y -> f y x
reverse = foldl (flip ( : )) [] --inverse l’ordre de la liste
Une figure pour le poker
Je vous avais promis une formulation plus élégante de split-if, utilisée pour analyser les mains au poker (fonction développée et utilisée lors des trois précédents billets), la voici, d’un geste de Samouraï :
| Code : | Sélectionner tout |
1 2 3 4 | --@ permet de nommer la structure déconstruite par pattern matching splitIf' p xs = foldr (ft p) [[]] xs |
En voici une de disambiguate :
| Code : | Sélectionner tout |
1 2 | disambiguate' a b = foldr (\x y -> if x == EQ then y else x) EQ $ zipWith compare a b --les recherches sur compare et zipWith sont laissées au lecteur |
Enfin je propose, à ceux qui n’auraient dans la journée que la stimulation intellectuelle de faire des boucles,
| Code : | Sélectionner tout |
for (int i = 0 ; i < MAX_VAL ; ++i) // si j’avais gagné un euro à chaque fois…
| Code : | Sélectionner tout |
foldl f a bs = foldr (\b g x -> g (f x b)) id bs a
de l’intérêt de tout cela, j’annonce une série de billets prochains sur la mise en place d’une IA simple et modulaire pour des jeux de plateau mettant à profit les katas du jour. Nous rendrons ainsi hommage aux morpions !
Comme il se peut que j’aie quelques notions importantes à présenter d’abord, laissez-moi tout de même un ou deux billets avant de lancer la série.
Exercices :
- réfléchir aux représentations d’un plateau de morpions
- faites une recherche sur l’algorithme minimax
- êtes-vous plutôt strict ou paresseux ? si vous êtes plutôt paresseux, je montrerai dans le prochain billet tous les bénéfices de ce trait de caractère…