1. Introduction▲
La première partie de ce tutoriel prend des exemples simples de boucles de transformation de données et les traduit en instructions de type map ou reduce. La seconde partie considère des boucles plus complexes, les scinde en fragments unitaires et rend chacun de ces fragments fonctionnel. La troisième partie prend en exemple une longue boucle consistant en une série de transformations successives des données et la décompose en un pipeline fonctionnel.
Les exemples sont écrits en Python, car beaucoup de personnes trouvent le code Python facile à lire. Beaucoup de ces exemples évitent les particularités propres à Python afin d'illustrer des techniques qui sont communes à beaucoup de langages de programmation : map, reduce, programmation par flux de données ou en pipeline. Tous les exemples de code sont écrits en Python 2.
2. Le fil conducteur▲
Quand on aborde la programmation fonctionnelle, c'est souvent pour parler d'un nombre étourdissant de caractéristiques « fonctionnelles » : les données immuables(1), les fonctions de première classe(2) et l'optimisation de la récursion terminale(3). Ces fonctionnalités ne sont que des caractéristiques de langage qui facilitent la programmation fonctionnelle. On parle aussi de mappage, de réduction, de pipeline, de récursion, de curryfication(4) et d'utilisation des fonctions d'ordre supérieur. Ce sont des techniques de programmation employées pour écrire du code fonctionnel. Il est enfin question de parallélisation(5), d'évaluation paresseuse(6) et de déterminisme(7). Ce ne sont que des propriétés avantageuses des programmes fonctionnels.
Oubliez tout cela. Un programme écrit en style fonctionnel se caractérise essentiellement par une chose : l'absence d'effets de bord. Le code ne dépend pas de données se trouvant à l'extérieur de la fonction courante et il ne modifie pas des données à l'extérieur de cette fonction. Toutes les autres caractéristiques de la programmation fonctionnelle peuvent se déduire de cette propriété. Utilisez-la comme un fil conducteur lors de votre apprentissage.
Voici un exemple de fonction non fonctionnelle :
2.
3.
4.
a = 0
def increment():
global a
a += 1
Et voici une fonction fonctionnelle :
2.
def increment(a):
return a + 1
3. N'itérez pas sur des listes : utilisez map et reduce▲
3-1. Map▲
La fonction map prend en argument une fonction et une collection de données. Elle crée une nouvelle collection vide, applique la fonction à chaque élément de la collection d'origine et insère les valeurs de retour produites dans la nouvelle collection. Finalement, elle renvoie la nouvelle collection.
Voici un map simple qui prend en entrée une liste de noms et renvoie une liste contenant la longueur de chacun de ces noms :
Ce map élève au carré chacun des nombres de la collection qui lui est passée :
2.
3.
4.
squares = map(lambda x: x * x, [0, 1, 2, 3, 4])
print squares
# => [0, 1, 4, 9, 16]
Ce map ne prend pas une fonction nommée en paramètre : il prend une fonction anonyme en ligne définie à l'aide du mot-clef lambda. Les paramètres de cette fonction lambda sont définis à gauche du caractère deux-points et le corps de la fonction est défini à sa droite. Le résultat de l'exécution du corps de cette fonction est renvoyé (implicitement).
Le code non fonctionnel ci-dessous prend une liste de noms réels et les remplace par des noms de code choisis aléatoirement.
(Comme vous pouvez le remarquer, cet algorithme peut éventuellement affecter le même nom de code secret à plusieurs des agents secrets. Espérons que cela ne constituera pas une source de confusion au cours de la mission secrète.)
Nous pouvons réécrire ce code avec un map :
2.
3.
4.
5.
6.
7.
8.
import random
names = ['Mary', 'Isla', 'Sam']
secret_names = map(lambda x: random.choice(['Mr. Pink',
'Mr. Orange',
'Mr. Blonde']),
names)
Exercice 1 : essayez de réécrire sous la forme d'un map le code ci-dessous, qui prend en entrée une liste de noms réels et les remplace par des noms de code produits à l'aide d'une stratégie plus robuste :
(Espérons que les agents secrets ont une bonne mémoire et n'oublieront pas le nom de code de leurs collègues au cours de leur mission secrète.)
Voici ma solution :
3-2. Reduce▲
La fonction reduce prend en entrée une fonction et une collection d'éléments. Elle renvoie une valeur créée en combinant les éléments de la collection.
Voici une réduction simple. Elle renvoie la somme de tous les éléments de la collection :
x est l'élément courant de l'itération et a est l'accumulateur. C'est la valeur renvoyée par l'exécution de la fonction lambda sur l'élément précédent. La fonction reduce() parcourt les éléments de la liste et, pour chacun d'eux, exécute la lambda sur les valeurs courantes de a et de x et renvoie le résultat qui devient le a de l'itération suivante.
Que vaut a lors de la première itération ? Il n'y a pas de résultat d'une itération précédente à lui passer. La fonction reduce() utilise la première valeur de la liste pour a, et commence à itérer à partir de la seconde valeur. Autrement dit, la première valeur de x est le second élément de la liste.
Le programme suivant compte le nombre d'occurrences du mot « Sam » dans une liste de chaînes de caractères :
2.
3.
4.
5.
6.
7.
8.
9.
10.
sentences = ['Mary read a story to Sam and Isla.',
'Isla cuddled Sam.',
'Sam chortled.']
sam_count = 0
for sentence in sentences:
sam_count += sentence.count('Sam')
print sam_count
# => 3
Voici le même programme réécrit avec un reduce :
2.
3.
4.
5.
6.
7.
sentences = ['Mary read a story to Sam and Isla.',
'Isla cuddled Sam.',
'Sam chortled.']
sam_count = reduce(lambda a, x: a + x.count('Sam'),
sentences,
0)
Comment ce programme détermine-t-il la valeur initiale de a ? La valeur de départ pour le nombre d'occurrences de « Sam » ne peut pas être la chaîne de caractères « Mary read a story to Sam and Isla. » La valeur initiale de l'accumulateur est spécifiée dans le troisième argument de la fonction reduce(). Ce mécanisme permet d'utiliser une valeur de départ d'un type différent de celui des valeurs de la collection fournie en entrée.
Pourquoi les fonctions map et reduce sont-elles meilleures ?
Premièrement, le code est plus court et tient souvent en une seule ligne.
Deuxièmement, les parties importantes de l'itération - la collection, l'opération et la valeur de retour - figurent au même endroit dans tous les map et reduce.
Troisièmement, le code d'une boucle peut affecter des variables définies avant la boucle ou le code situé après. Par convention, map et reduce sont fonctionnels (et n'ont donc pas d'effets de bord).
Quatrièmement, map et reduce sont des opérations élémentaires. Chaque fois qu'on lit une boucle for, il faut analyser la logique ligne par ligne. Il existe des éléments récurrents que l'on peut utiliser pour construire un échafaudage permettant d'asseoir la compréhension du code. En revanche, map et reduce constituent immédiatement des briques de construction qui peuvent se combiner pour assembler des algorithmes complexes. Et ce sont des éléments que celui qui lit le code peut comprendre instantanément et abstraire dans son esprit : « Ah, dira-t-il peut-être, cette ligne de code transforme chaque élément de la collection, puis met à la poubelle certains des éléments ainsi transformés. Et il combine le reste pour n'en faire qu'un seul résultat. »
Cinquièmement, les fonctions map et reduce ont de nombreuses amies qui offrent des fonctionnalités modifiées et utiles, par exemple : filter, all, any et find.
Exercice 2 : essayez de réécrire le code ci-dessous en utilisant map, reduce et filter. La fonction filter prend en entrée une fonction et une collection. Elle renvoie une nouvelle collection contenant tous les éléments de la collection d'origine pour laquelle la fonction renvoie une valeur vraie (True).
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
people = [{'name': 'Mary', 'height': 160},
{'name': 'Isla', 'height': 80},
{'name': 'Sam'}]
height_total = 0
height_count = 0
for person in people:
if 'height' in person:
height_total += person['height']
height_count += 1
if height_count > 0:
average_height = height_total / height_count
print average_height
# => 120
Si cela vous paraît semé d'embûches, essayez de ne pas penser du point de vue des opérations sur les données. Pensez plutôt aux états que les données vont connaître, depuis les dictionnaires de personnes au départ jusqu'à la taille moyenne de ces personnes à la fin. N'essayez pas de regrouper des transformations multiples. Mettez chacune de ces transformations dans une ligne distincte et affectez le résultat à une variable ayant un nom descriptif. Une fois que le code fonctionne, vous pouvez songer à le condenser.
Voici ma solution :
4. Écrivez du code déclaratif et non impératif▲
Le programme ci-dessous organise une course entre trois automobiles. À chaque instant, chacune des voitures peut avancer ou rester arrêtée. À chaque fois, le programme affiche la trajectoire des automobiles jusqu'à présent. Après cinq étapes, la course s'arrête.
Voici d'abord l'affichage d'un résultat possible :
-
--
--
--
--
---
---
--
---
----
---
----
----
----
-----Et voici le programme :
Ce programme est écrit en style impératif. Une version fonctionnelle serait déclarative. Elle décrirait ce qu'il faut faire et non comment le faire.
4-1. Utilisez des fonctions▲
Un programme peut être rendu plus déclaratif en assemblant des bouts de code dans des fonctions.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
from random import random
def move_cars():
for i, _ in enumerate(car_positions):
if random() > 0.3:
car_positions[i] += 1
def draw_car(car_position):
print '-' * car_position
def run_step_of_race():
global time
time -= 1
move_cars()
def draw():
print ''
for car_position in car_positions:
draw_car(car_position)
time = 5
car_positions = [1, 1, 1]
while time:
run_step_of_race()
draw()
Pour comprendre ce programme, le lecteur lit simplement la boucle principale : « S'il y a encore du temps, exécute une étape de la course et dessine. Puis vérifie à nouveau s'il reste du temps. » Si le lecteur désire savoir ce que signifie exécuter une étape ou dessiner, il lui suffit de lire ces fonctions.
Les commentaires deviennent inutiles. Le code s'autodocumente.
Répartir le code en fonctions est une excellente façon de rendre le code plus lisible sans demander de gros efforts intellectuels.
Cette technique utilise des fonctions, mais il les utilise comme ce que l'on appelle parfois des sous-routines ou des procédures. Ces fonctions regroupent des lignes de code. Mais ce code n'est pas fonctionnel au sens du fil conducteur. Ces fonctions utilisent des états qui ne lui ont pas été passés sous la forme d'arguments. Elles affectent le code aux alentours en modifiant des variables externes au lieu de renvoyer des valeurs. Pour comprendre ce qu'une fonction fait réellement, le lecteur doit lire soigneusement chaque ligne de code. S'il rencontre une variable externe, il doit en trouver l'origine. Il doit vérifier si d'autres fonctions n'affectent pas cette variable.
4-2. Suppression des états globaux▲
Voici le code d'une version fonctionnelle de la course automobile :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
from random import random
def move_cars(car_positions):
return map(lambda x: x + 1 if random() > 0.3 else x,
car_positions)
def output_car(car_position):
return '-' * car_position
def run_step_of_race(state):
return {'time': state['time'] - 1,
'car_positions': move_cars(state['car_positions'])}
def draw(state):
print ''
print '\n'.join(map(output_car, state['car_positions']))
def race(state):
draw(state)
if state['time']:
race(run_step_of_race(state))
race({'time': 5,
'car_positions': [1, 1, 1]})
Le code est toujours réparti en fonctions, mais ces fonctions sont… fonctionnelles. Trois symptômes le montrent. D'abord, il n'y a plus de variables partagées (global). Les temps et les positions des véhicules sont passés en paramètres à la fonction race(). Ensuite, les fonctions admettent des paramètres. Enfin, il n'y a pas de variables instanciées à l'intérieur des fonctions. Toutes les modifications de données s'effectuent sous la forme de valeurs de retour. La fonction race() s'appelle récursivement avec le résultat de run_step_of_race(). Chaque fois qu'une étape génère un nouvel état, celui-ci est immédiatement passé à l'étape suivante.
Considérons maintenant deux fonctions, zero() et one().
2.
3.
4.
5.
6.
7.
def zero(s):
if s[0] == "0":
return s[1:]
def one(s):
if s[0] == "1":
return s[1:]
La fonction zero() prend en paramètre une chaîne de caractères : s. Si le premier caractère est un « 0 », elle renvoie le reste de la chaîne ; dans le cas contraire, elle renvoie None. La fonction one() fait la même chose, mais pour un premier caractère égal à « 1 ».
Imaginons maintenant une fonction nommée rule_sequence(), qui prend en entrée une chaîne de caractères et une liste de fonctions-règles de la même forme que zero() et one(). Elle appelle la première règle sur la chaîne et appelle la seconde règle en lui passant en paramètre la valeur de retour de la première règle, sauf si cette valeur est None. Elle passe ensuite en paramètre à la troisième règle la valeur renvoyée par la seconde, sauf s'il s'agit de None, et ainsi de suite. Si l'une quelconque des règles renvoie None, rule_sequence() s'arrête et renvoie None. Sinon, elle renvoie la valeur de retour de la dernière règle.
Voici un exemple de données en entrée et en sortie :
2.
3.
4.
5.
print rule_sequence('0101', [zero, one, zero])
# => 1
print rule_sequence('0101', [zero, zero])
# => None
Voici une version impérative de rule_sequence() :
2.
3.
4.
5.
6.
7.
def rule_sequence(s, rules):
for rule in rules:
s = rule(s)
if s == None:
break
return s
Exercice 3 : le programme ci-dessus utilise une boucle pour faire le travail. Rendez-le plus déclaratif en le réécrivant sous une forme récursive.
Voici ma solution :
2.
3.
4.
5.
def rule_sequence(s, rules):
if s == None or not rules:
return s
else:
return rule_sequence(rules[0](s), rules[1:])
5. Utilisation de pipelines▲
Dans la section précédente, nous avons réécrit des boucles impératives sous la forme de récursions appelant éventuellement des fonctions auxiliaires. Ici nous allons réécrire un type différent de boucle impérative à l'aide d'une technique nommée pipeline.
La boucle ci-dessous effectue des transformations sur des dictionnaires qui contiennent le nom, le pays d'origine erroné et le statut (actif ou inactif) de groupes musicaux.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
bands = [{'name': 'sunset rubdown', 'country': 'UK', 'active': False},
{'name': 'women', 'country': 'Germany', 'active': False},
{'name': 'a silver mt. zion', 'country': 'Spain', 'active': True}]
def format_bands(bands):
for band in bands:
band['country'] = 'Canada'
band['name'] = band['name'].replace('.', '')
band['name'] = band['name'].title()
format_bands(bands)
print bands
# => [{'name': 'Sunset Rubdown', 'active': False, 'country': 'Canada'},
# {'name': 'Women', 'active': False, 'country': 'Canada' },
# {'name': 'A Silver Mt Zion', 'active': True, 'country': 'Canada'}]
Le nom de la fonction peut susciter quelque inquiétude. « format » est très vague. Un examen plus attentif du code ne peut que renforcer cette inquiétude. Il se passe trois choses dans la même boucle. Le « pays » est changé en « Canada ». Les signes de ponctuation sont supprimés du nom du groupe, et le nom du groupe est passé en lettres capitales. Il est difficile de dire ce que le code est censé faire, et difficile de dire s'il fait bien ce qu'il paraît faire. Le code est difficile à réutiliser, à tester et à paralléliser.
Comparez avec le code suivant :
2.
3.
print pipeline_each(bands, [set_canada_as_country,
strip_punctuation_from_name,
capitalize_names])
Ce code est facile à comprendre. Il donne l'impression que les fonctions auxiliaires sont fonctionnelles puisqu'elles paraissent chaînées : le résultat d'une fonction devient la donnée en entrée de la suivante. Si elles sont fonctionnelles, elles sont faciles à vérifier et elles sont également faciles à réutiliser, à tester et à paralléliser.
Le but de pipeline_each() est de passer en paramètre les groupes, un à la fois, à une fonction de transformation comme set_canada_as_country(). Une fois cette transformation appliquée à chacun des groupes, la fonction pipeline_each() crée une nouvelle liste de groupes transformée. Elle passe alors chacun de ces groupes à la fonction suivante.
Jetons un coup d'œil aux fonctions de transformation :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
def assoc(_d, key, value):
from copy import deepcopy
d = deepcopy(_d)
d[key] = value
return d
def set_canada_as_country(band):
return assoc(band, 'country', "Canada")
def strip_punctuation_from_name(band):
return assoc(band, 'name', band['name'].replace('.', ''))
def capitalize_names(band):
return assoc(band, 'name', band['name'].title())
Chacune d'entre elles associe une nouvelle valeur à une clef d'un groupe. Ce n'est pas facile à réaliser sans modifier le groupe d'origine. La fonction assoc() résout ce problème en utilisant la fonction deepcopy() pour produire une copie du dictionnaire reçu en paramètre. Chaque fonction de transformation effectue sa modification sur cette copie et renvoie cette copie.
Tout cela semble fonctionner. Les dictionnaires d'origine sont protégés contre la modification quand une nouvelle valeur est affectée à une clef, mais il y a potentiellement deux autres modifications dans le code ci-dessus. Dans strip_punctuation_from_name(), le nom sans ponctuation est généré en appelant replace() sur le nom d'origine. De même, dans capitalize_names(), le nouveau nom en majuscules est généré en appelant title() sur le nom d'origine. Si les fonctions replace() et title() ne sont pas fonctionnelles, alors strip_punctuation_from_name() et replace() ne le sont pas non plus.
Heureusement, il se trouve que les fonctions internes replace() et title() ne modifient pas les chaînes de caractères qui leur sont passées en arguments, parce que les chaînes sont immuables en Python. Par exemple, quand replace() traite le nom d'un groupe, le nom du groupe d'origine est copié et replace() agit sur cette copie. Ouf !
Cette différence de mutabilité entre les chaînes de caractères et les dictionnaires illustre l'intérêt de langages de programmation comme Clojure : le programmeur n'a jamais besoin de se demander si les données sont mutables ou non, elles ne le sont pas.
Exercice 4 : essayez d'écrire la fonction pipeline_each. Pensez à l'ordre des opérations. Les groupes du tableau bands sont passés, un par un, à la première fonction de transformation. Les groupes du tableau résultant sont ensuite passés, un à la fois, à la seconde fonction, et ainsi de suite.
Voici ma solution :
Chacune des trois fonctions de transformation se résume à la modification d'un champ particulier du groupe passé en argument. La fonction call() permet d'en faire une fonction abstraite. Elle reçoit en paramètre la fonction à appliquer et la clef de la valeur à traiter.
2.
3.
4.
5.
6.
7.
set_canada_as_country = call(lambda x: 'Canada', 'country')
strip_punctuation_from_name = call(lambda x: x.replace('.', ''), 'name')
capitalize_names = call(str.title, 'name')
print pipeline_each(bands, [set_canada_as_country,
strip_punctuation_from_name,
capitalize_names])
Ou, si nous sommes prêts à sacrifier un peu de lisibilité sur l'autel de la concision :
2.
3.
print pipeline_each(bands, [call(lambda x: 'Canada', 'country'),
call(lambda x: x.replace('.', ''), 'name'),
call(str.title, 'name')])
Le code de la fonction call() :
2.
3.
4.
5.
6.
7.
8.
9.
10.
def assoc(_d, key, value):
from copy import deepcopy
d = deepcopy(_d)
d[key] = value
return d
def call(fn, key):
def apply_fn(record):
return assoc(record, key, fn(record.get(key)))
return apply_fn
Il se passe beaucoup de choses ici. Décortiquons morceau par morceau :
- call() est une fonction d'ordre supérieur. Une fonction d'ordre supérieur est une fonction qui prend une fonction en argument ou renvoie une fonction. Ou qui, comme dans le cas de call(), fait les deux ;
- apply_fn() ressemble beaucoup aux trois fonctions de transformation. Elle prend en entrée un enregistrement (un groupe) et recherche la valeur de record[key]. Elle appelle fn sur cette valeur, affecte le résultat à une copie de l'enregistrement et renvoie cette copie ;
- call() ne fait aucun travail véritable. C'est apply_fn() qui effectue le vrai travail une fois appelée. Dans l'exemple d'utilisation de pipeline_each() ci-dessus, une instance de la fonction apply_fn() affectera 'Canada' à 'country'. Une autre instance mettra en lettres capitales le nom du groupe ;
- Quand une instance de apply_fn() s'exécute, fn et key ne sont pas dans la portée, puisqu'ils ne sont pas passés en paramètres, ni ne sont déclarés localement dans la fonction. Mais ils sont néanmoins accessibles. Quand une fonction est définie, elle sauvegarde des références sur les variables de l'environnement (en dehors de la fonction) où elle est définie et ces références sont utilisées dans la fonction. On dit qu'elle « se ferme » sur ces variables et qu'une telle fonction est une « fermeture ». Quand une fonction s'exécute et que son code réfère à une variable, Python la recherche parmi les variables locales à la fonction et les paramètres reçus lors de l'appel. S'il n'y trouve pas cette variable, alors il la recherche parmi les références sauvegardées sur les variables sur lesquelles la fonction s'est fermée. Et c'est là qu'il trouvera fn et key ;
-
Le code de call() ne fait aucune référence aux groupes, parce que call() pourrait servir à générer des fonctions de type pipeline pour un programme quelconque, quel que soit son objet. La programmation fonctionnelle consiste en partie à assembler une librairie de fonctions génériques, abstraites, réutilisables et composables ;
Bon boulot. Les fermetures, les fonctions d'ordre supérieur et la portée des variables couvertes en l'espace de quelques paragraphes… Allez, faites une pause et prenez un bon verre de limonade.(8)
Il reste un dernier traitement à effectuer sur nos groupes : tout supprimer à l'exception du nom et du pays. La fonction extract_name_and_country() peut extraire cette information :
Sélectionnez1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.defextract_name_and_country(band): plucked_band={} plucked_band['name']=band['name'] plucked_band['country']=band['country']returnplucked_bandprintpipeline_each(bands, [call(lambdax:'Canada','country'),call(lambdax: x.replace('.',''),'name'),call(str.title,'name'), extract_name_and_country])# => [{'name': 'Sunset Rubdown', 'country': 'Canada'},# {'name': 'Women', 'country': 'Canada'},# {'name': 'A Silver Mt Zion', 'country': 'Canada'}] -
La fonction extract_name_and_country() pourrait s'écrire sous la forme de la fonction générique pluck() qui serait utilisée comme suit :
Sélectionnez1.
2.
3.
4.printpipeline_each(bands, [call(lambdax:'Canada','country'),call(lambdax: x.replace('.',''),'name'),call(str.title,'name'),pluck(['name','country'])]) - Exercice 5 : pluck() prend en paramètre une liste de clefs à extraire de chaque enregistrement. Essayez de l'écrire. Il est nécessaire que ce soit une fonction d'ordre supérieur.
Voici ma solution :
2.
3.
4.
5.
6.
def pluck(keys):
def pluck_fn(record):
return reduce(lambda a, x: assoc(a, x, record[x]),
keys,
{})
return pluck_fn
6. Et maintenant ?▲
Le code fonctionnel coexiste très bien avec du code écrit dans d'autres styles de programmation. Les transformations décrites dans cet article peuvent s'appliquer à une base de code quelconque, presque dans n'importe quel langage de programmation(9). Essayez de les employer dans vos propres programmes.
Pensez à Mary, Isla et Sam. Convertissez vos itérations sur des listes en des map et des reduce.
Pensez à la course automobile. Divisez votre code en fonctions. Rendez ces fonctions fonctionnelles. Transformez une boucle qui se répète en une récursion.
Pensez aux groupes de musiciens. Transformez une suite d'opérations en un pipeline.
7. Remerciements▲
Nous remercions Mary Rose Cook de nous avoir autorisés à traduire et republier son billet initialement publié ici : https://maryrosecook.com/blog/post/a-practical-introduction-to-functional-programming.
Nous remercions lolo78 pour la traduction de ce tutoriel, Laethy et genthial pour la relecture.