Exploration de Python : traitement des séquences avec un style fonctionnel — reduce

Contexte

Ce billet s’inscrit dans une série de billets sur le traitement des séquences avec un style fonctionnel en Python dont le premier portait sur la fonction filter et le second sur la fonction map.

Ce billet est donc le troisième dans la série et traite de la fonction reduce.

Les exemples de ce billet ont été testés avec la version 3.12 de Python.

Principe

Comme filter et map, la fonction reduce transforme une séquence qui lui est fournie en paramètre grâce à une fonction qui lui est également fournie en paramètre en parcourant la séquence de la gauche vers la droite.

A la différence de filter qui modifie la séquence originale en supprimant ses éléments qui sont faux pour un prédicat pour produire une nouvelle séquence ou à la différence de map qui transforme individuellement chaque élément de la séquence pour produire une nouvelle séquence, reduce parcours la séquence de la gauche vers la droite en combinant les éléments afin de transformer la séquence elle-même en un nouvel objet (une valeur scalaire, une nouvelle séquence, etc.).

Nous allons éclairer tout cela par plusieurs exemples, mais il faut noter qu’en Python contrairement à filter et à map, reduce n'est pas (en fait n'est plus) une fonction native : elle se trouve dans le module functools (c’est à priori pour des questions de performance et de lisibilité).

Reductio ad exemplum

L’idée avec la fonction reduce, comme son nom le rappel, est de réduire une séquence à un résultat.

Juste faire une réduction en somme !

L’exemple classique est la somme d’une liste de nombres : je souhaite réduire une liste de nombres à la somme de ces nombres. Prenons la liste des nombres de 1 à 10 qui peuvent nous être donnés en Python avec range(1,11) (rappelons que pour les intervalles en Python la valeur de fin est non incluse) et calculons leur somme.

Commençons par le faire de manière impérative avec for.

sum_of_numbers_1 = 0
for number in range(1, 11):
    sum_of_numbers_1 = sum_of_numbers_1 + number
print("Somme des nombres de 1 à 10 avec une boucle for :", sum_of_numbers_1)

la variable sum_of_numbers_1 initialisée à 0, sert d'accumulateur : dans la boucle on ajoute successivement chaque élément de la liste à cet accumulateur.

>>> sum_of_numbers_1 = 0
>>> for number in range(1, 11):
...     sum_of_numbers_1 = sum_of_numbers_1 + number
...
>>> print("Somme des nombres de 1 à 10 avec une boucle for :", sum_of_numbers_1)
Somme des nombres de 1 à 10 avec une boucle for : 55

C’est très exactement ce que fait reduce :

>>> import functools
>>> functools.reduce(lambda a, b: a + b, range(1, 11))
55

La fonction reduce prend en paramètre une fonction et un iterator. La fonction passée à reduce prend elle-même 2 paramètres en entrée. Elle produit une valeur en sortie qui n'est pas nécessairement du même type que celui des éléments en entrée (même si c'est le cas ici avec l'addition).

Que se passe-t-il la séquence en paramètre n’a qu’un seul élément ?

>>> import functools
>>> functools.reduce(lambda a, b: a + b, [1])
1

Et bien, cet élément est retourné. Et que se passe-t-il avec la liste vide ?

>>> import functools
>>> functools.reduce(lambda a, b: a + b, [])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: reduce() of empty iterable with no initial value

Et bien dans ce cas on a une exception. Cela semble normal, il n’y a aucune valeur cohérente que reduce puisse retourner dans ce cas.

En fait reduce prend un troisième paramètre optionnel qui correspond à une valeur initiale pour démarrer la réduction. Avec ce troisième paramètre, on peut lui passer une séquence vide, c'est cette valeur initiale qui est alors retournée.

>>> import functools
>>> functools.reduce(lambda a, b: a + b, [], 0)
0
>>> functools.reduce(lambda a, b: a + b, range(1, 11), 0)
55
>>> functools.reduce(lambda a, b: a + b, range(1, 11), 5)
60

Cela n’a pas à voir directement avec reduce mais au passage on peut noter que dans le cas précis de l'addition, nous avons une écriture plus compacte que la lambda en utilisant le module operator et la fonction add qui y est définie (entre autre chose) :

>>> import functools
>>> import operator
>>> functools.reduce(operator.add, range(1, 11), 5)
60

Donc reduce permet de combiner l'ensemble des éléments d'une séquence en prenant en compte éventuellement une valeur initiale pour produire un résultat.

Cependant il est peu probable que vous utilisiez reduce pour calculer une somme de nombres en Python. Pourquoi ? Parce qu'il y a une fonction native sum qui est une version spécialisée de reduce et qui calcule la somme des valeurs numériques d'un iterator.

>>> import functools
>>> import operator
>>> numbers_1_to_10 = range(1, 11)
>>> functools.reduce(operator.add, numbers_1_to_10)
55
>>> sum(numbers_1_to_10)
55

La fonction sum prend également en paramètre optionnel une valeur initiale qui vaut par défaut 0. Il faut noter que pour les nombres flottants il vaut mieux utiliser la fonction fsum du module math.

>>> import math
>>> import decimal
>>> decimal.Decimal.from_float(sum([1.234556e-20, 1.2e-10, math.pi, math.e, math.sqrt(2), math.tau, math.sqrt(3)]))
Decimal('15.2893241592903965653249542810954153537750244140625')
>>> decimal.Decimal.from_float(math.fsum([1.234556e-20, 1.2e-10, math.pi, math.e, math.sqrt(2), math.tau, math.sqrt(3)]))
Decimal('15.2893241592903965653249542810954153537750244140625')

Jusqu’à au moins Python 3.9, j’avais pu constater que le calcul n’avait pas la même précision en forçant l’affichage de décimal. Néanmoins cela ne semble plus être le cas en Python 3.12. La différence est que fsum renvoie toujours un float alors que le type de retour pour sum dépend du type des éléments de la liste. De plus fsum doit être importé alors que sum est une fonction native utilisable directement.

Ne trouvez-vous pas cocasse qu’une somme de nombres soit au fond une réduction ?

On donne le max !

Après tout, la fonction reduce peut être utilisée à autre chose que le calcul de la somme des nombres d'un itérable. On peut par exemple l'utiliser pour déterminer la maximum et le minimum d'une séquence d'élément.

>>> import functools
>>> numbers_1_to_10 = range(1, 11)
>>> functools.reduce(lambda a, b: a if a > b else b, numbers_1_to_10)
10
>>> functools.reduce(lambda a, b: a if a < b else b, numbers_1_to_10)
1

Mais comme pour la fonction sum, en Python, il existe des fonctions natives max et min dont on préférera l'utilisation à celles de reduce.

>>> numbers_1_to_10 = range(1, 11)
>>> max(numbers_1_to_10)
10
>>> min(numbers_1_to_10)
1

C’est sûr en présentant les choses comme cela, on ne perçoit probablement pas grand intérêt à reduce pour l'instant : les réductions les plus communes le sont tellement qu’elles ont des fonctions dédiées explicites !

House of the Dragon

La fonction reduce est souvent utilisée pour réduire une liste d'éléments à une valeur scalaire mais rien n'oblige à ce que cela soit le cas. On peut utiliser reduce pour combiner les éléments pour produire n'importe quel type de valeur.

Ainsi imaginons que j’ai une liste de noms et que je veuille créer un dictionnaire qui a comme clé ce nom avec comme valeur associée la longueur de ce nom. Je peux m’y prendre comme suit avec reduce.

import functools

houses = {"tyrell", "stark", "lannister", "tarly", "baratheon", "targaryen"}
print("Houses  :", houses)


def aggregate(accumulator, current_item):
    accumulator.update({current_item: len(current_item)})
    return accumulator


length_by_house = functools.reduce(aggregate, houses, {})
print("Longueur du nom par nom de maison avec reduce:", length_by_house)

J’ai une fonction qui combine les éléments de mon iterator en les agrégeant les uns après les autres dans un dictionnaire avec sa taille. On part de l'hypothèse que la séquence n'a pas de doublon pour rester simple. La valeur d'initialisation est le dictionnaire vide. Le premier élément est ajouté dans ce dictionnaire vide et la valeur retournée est le dictionnaire avec ce premier élément et sa taille. Cette valeur retournée est passée comme paramètre accumulator pour le deuxième élément et ainsi de suite. Arrivée en fin de liste, la valeur retournée par reduce est le dictionnaire avec le dernier élément ajouté.

Houses  : {'baratheon', 'stark', 'tyrell', 'targaryen', 'tarly', 'lannister'}
Longueur du nom par nom de maison avec reduce: {'baratheon': 9, 'stark': 5, 'tyrell': 6, 'targaryen': 9, 'tarly': 5, 'lannister': 9}

Bien sûr en Python, vous pouvez obtenir le même résultat avec une compréhension, ce qui donne un code plus compact et probablement plus lisible.

>>> houses = {"tyrell", "stark", "lannister", "tarly", "baratheon", "targaryen"}
>>> {house: len(house) for house in houses}
{'lannister': 9, 'baratheon': 9, 'tarly': 5, 'stark': 5, 'targaryen': 9, 'tyrell': 6}

Il faut reconnaitre qu’encore une fois, il existe une solution en Python plus intéressante que celle basée sur l’utilisation de la fonction reduce. Cependant, une compréhension pourra être utilisée à la place de reduce si le résultat que l'on souhaite obtenir est une list, un tuple, un set, un dict ou un iterator. Si on souhaite réduire à un objet par exemple on ne pourra pas le faire directement avec une compréhension. Prenons un exemple un peu artificiel basé sur l’exemple précédent.

import functools

houses = {"tyrell", "stark", "lannister", "tarly", "baratheon", "targaryen"}


def aggregate(accumulator, current_item):
    accumulator.update({current_item: len(current_item)})
    return accumulator


class HousesOfWesteros:
    def __init__(self):
        self.name_length_by_name = {}

    def update(self, dictionary):
        self.name_length_by_name.update(dictionary)

    def __str__(self):
        return str(self.name_length_by_name)


print(
    "Longueur du nom par nom de maison avec reduce sur un objet :",
    functools.reduce(aggregate, houses, HousesOfWesteros()),
)

La classe HousesOfWesteros est juste une enveloppe autour d'un dictionnaire. En soit elle n'a pas grand intérêt, si ce n'est pour les besoins de la démonstration ici. En effet, ce qui est intéressant avec reduce c'est qu'on peut réduire une séquence a à peu près n'importe quoi. On notera au passage, l'utilisation du Duck Typing et la réutilisation de la fonction aggregate définie précédemment, qui est utilisée aussi bien sur un dict que sur la classe HousesOfWesteros, ce qui est important est que l'on puisse appliquer sur l'un et l'autre la fonction update.

Longueur du nom par nom de maison avec reduce sur un objet : {'baratheon': 9, 'stark': 5, 'tarly': 5, 'tyrell': 6, 'targaryen': 9, 'lannister': 9}

Le point est que la fonction reduce est très générique mais qu'en Python pour la plupart des besoins courants, on n'en n'a pas besoin car on a généralement une solution plus simple à mettre en œuvre.

La fonction reduce est vraiment générique

Comme cela vient d’être écrit la fonction reduce est très générique, à tel point que l'on peut exprimer les fonctions filter et map avec reduce. D'une certaine manière filter et map sont des versions spécialisées de reduce. Commençons par filter.

import functools


def my_filter(predicate, seq):
    def filter_and_aggregate_as_list(accumulator, current_elt):
        if predicate(current_elt):
            accumulator.append(current_elt)
        return accumulator

    return functools.reduce(filter_and_aggregate_as_list, seq, [])


print(
    "Nombres pairs entre 1 à 9 avec my_filter:",
    my_filter(lambda x: x % 2 == 0, range(1, 10)),
)
print(
    "Nombres pairs entre 1 à 9 avec filter:",
    list(filter(lambda x: x % 2 == 0, range(1, 10))),
)

On peut constater que cela nous donne bien le même résultat qu’avec le filter natif.

Nombres pairs entre 1 à 9 avec my_filter: [2, 4, 6, 8]
Nombres pairs entre 1 à 9 avec filter: [2, 4, 6, 8]

L’implémentation repose sur la fonction de réduction qui réalise le filtrage de la liste originale. On notera quand même que dans l’ implémentation que je propose c’est une liste qui est retournée et non un iterator. L'objectif est ici bien sûr de montrer le principe de fonctionnement.

Si nous passons à map, on pourrait avoir une implémentation de la forme :

import functools


def my_map(fun, seq):
    def apply_function_and_aggregate_as_list(accumulator, current_elt):
        accumulator.append(fun(current_elt))
        return accumulator

    return functools.reduce(apply_function_and_aggregate_as_list, seq, [])


print(
    "Puissances de 2 des nombres entre 1 à 9 avec my_map:",
    my_map(lambda x: x**2, range(1, 10)),
)
print(
    "Puissances de 2 des nombres entre 1 à 9 avec map:",
    list(map(lambda x: x**2, range(1, 10))),
)

On obtient des résultats similaires, au détail prêt encore une fois que l’implémentation proposée retourne une list et non un iterator.

Puissances de 2 des nombres entre 1 à 9 avec my_map: [1, 4, 9, 16, 25, 36, 49, 64, 81]
Puissances de 2 des nombres entre 1 à 9 avec map: [1, 4, 9, 16, 25, 36, 49, 64, 81]

Le principe est le même que pour filter, la fonction de réduction crée la liste d'éléments transformés par l'application de la fonction passée à map.

Synthèse

La fonction reduce est une fonction générique qui transforme une séquence d'éléments grâce à la fonction qui lui est passée en paramètre et qui sert à combiner les éléments de cette séquence 2 à 2 en la parcourant de la gauche vers la droite :

• cette fonction doit prendre en paramètre 2 éléments du même type que les éléments de la séquence ;
• la séquence est réduite en combinant ainsi successivement chaque élément de la séquence avec la fonction.
• la fonction reduce prend éventuellement un troisième paramètre optionnel qui sert de valeur de départ ;
• le résultat n’est pas nécessairement une séquence.

La fonction reduce est extrêmement puissante et est une fonction clé aux traitements des séquences dans les langages fonctionnels. Néanmoins en Python, si elle est présente, elle n'est souvent pas la solution privilégiée par rapport à des solutions plus spécialisées mais plus lisibles.

Il y a bien sûr un gist avec les sources des exemples.

J’avais publié une première version de ce billet sur mon blog personnel.

Remerciement

Je remercie mon collègue Anthony Tenneriello pour sa relecture attentive et ses remarques.