Contexte

Ce billet s’inscrit dans une série de billets sur le traitement des séquences avec un style fonctionnel en Python.

NB : La version de Python utilisée dans les exemples de code est la version 3.

Principe

Comme filter et map, la fonction reduce transforme une séquence qui lui est fourni 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 avant il faut également 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.

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 la 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) et calculons leur somme.

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

1
2
3
4

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’acummulateur : dans la boucle on ajoute successivement chaque élément de la liste à cet accumulateur.

1

Somme des nombres de 1 à 10 avec une boucle for : 55

C’est très exactement ce que va faire reduce :

1
2
3
4
5

import functools


sum_of_numbers_2 = functools.reduce(lambda a, b: a + b, range(1, 11))
print("Somme des nombres de 1 à 10 avec reduce :", sum_of_numbers_2)

La fonction reduce prend en paramètre une fonction et un iterator. On notera que cette 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).

1

Somme des nombres de 1 à 10 avec une boucle for : 55

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

1
2
3
4
5

import functools


sum_of_numbers_3 = functools.reduce(lambda a, b: a + b, [1])
print("Somme de la liste à un élément [1] avec reduce :", sum_of_numbers_3)

Et bien, cet élément est retourné.

1

Somme de la liste à un élément [1] avec reduce : 1

Et que se passe-t-il avec la liste vide ?

1
2
3
4
5

import functools


sum_of_numbers_4 = functools.reduce(lambda a, b: a + b, [])
print("Somme de la liste vide [] avec reduce :", sum_of_numbers_4)

Et bien dans ce cas on a une exception

1
2
3
4

Traceback (most recent call last):
  File "xxx.py", line yy, in <module>
    sum_of_numbers_4 = functools.reduce(lambda a, b: a + b, [])
TypeError: reduce() of empty sequence with no initial value

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 optionel qui correspond à une première 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 sera retournée.

1
2
3
4
5
6
7
8

sum_of_numbers_4 = functools.reduce(lambda a, b: a + b, [], 0)
print("Somme de la liste vide [] avec reduce et une valeur initiale :", sum_of_numbers_4)

sum_of_numbers_5 = functools.reduce(lambda a, b: a + b, range(1, 11), 0)
print("Somme des nombres de 1 à 10 avec reduce et une valeur initiale de 0 :", sum_of_numbers_5)

sum_of_numbers_6 = functools.reduce(lambda a, b: a + b, range(1, 11), 5)
print("Somme des nombres de 1 à 10 avec reduce et une valeur initiale de 5 :", sum_of_numbers_6)

1
2
3

Somme des nombres de 1 à 10 avec reduce et une valeur initiale de 0 : 55
Somme de la liste vide [] avec reduce et une valeur initiale : 0        
Somme des nombres de 1 à 10 avec reduce et une valeur initiale de 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 que nous avons ici, nous avons une écriture plus compacte que la lambda en utilisant le module operator et la fonction add qui y est défini (entre autre chose) :

1
2

sum_of_numbers_7 = functools.reduce(operator.add, range(1, 11), 5)
print("Somme des nombres de 1 à 10 avec reduce et une valeur initiale de 5 :", sum_of_numbers_7)

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.

1
2
3
4
5
6
7

import functools
import operator

numbers_1_to_10 = range(1, 11)
sum_numbers_1_to_10 = functools.reduce(operator.add, numbers_1_to_10)
print("Somme des nombres de 1 à 10 avec reduce :", sum_numbers_1_to_10)
print("Somme des nombres de 1 à 10 avec sum :", sum(numbers_1_to_10))

1
2

Somme des nombres de 1 à 10 avec reduce : 55
Somme des nombres de 1 à 10 avec sum : 55

La fonction sum prend également en paramètre optionel 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.

1
2
3
4
5
6
7
8

import math
import decimal


print("Somme de nombres flottants avec sum : ",
      decimal.Decimal.from_float(sum([1.234556e-20, 1.2e-10, math.pi, math.e, math.sqrt(2)])))
print("Somme de nombres flottants avec fsum : ",
      decimal.Decimal.from_float(math.fsum([1.234556e-20, 1.2e-10, math.pi, math.e, math.sqrt(2)])))

En forçant l’affichage de de décimal, on voit que le calcul n’a pas la même précision :

1
2

Somme de nombres flottants avec sum :  7.27408804454193269606321337050758302211761474609375
Somme de nombres flottants avec fsum :  7.27408804454193358424163307063281536102294921875

Entre nous, je trouve cela rigolo qu’une somme de nombres soit au fond une réduction !

On donne le max !

Après tout, reduce peut être utilisé à 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.

1
2
3
4
5
6
7

import functools


print("Le plus grand nombre pour l'intervalle de 1 à 10 avec reduce :",
      functools.reduce(lambda a, b: a if a > b else b, numbers_1_to_10))
print("Le plus petit nombre pour l'intervalle de 1 à 10 avec reduce :",
      functools.reduce(lambda a, b: a if a < b else b, numbers_1_to_10))

1
2

Le plus grand nombre pour l'intervalle de 1 à 10 avec reduce : 10
Le plus petit nombre pour l'intervalle de 1 à 10 avec reduce : 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.

1
2
3
4
5
6
7

import functools


print("Le plus grand nombre pour l'intervalle de 1 à 10 avec max :",
      max(numbers_1_to_10))
print("Le plus petit nombre pour l'intervalle de 1 à 10 avec min :",
      min(numbers_1_to_10))

1
2

Le plus grand nombre pour l'intervalle de 1 à 10 avec max : 10
Le plus petit nombre pour l'intervalle de 1 à 10 avec min : 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.

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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 aggré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 sera ajoutée dans ce dictionnaire vide et la valeur retournée sera le dictionnaire avec ce premier élément et sa taille. Cette valeur retournée sera 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 sera le dictionnaire avec le dernier élément ajouté.

1
2

Houses  : {'tarly', 'lannister', 'tyrell', 'baratheon', 'targaryen', 'stark'}
Length of the name by House name (reduce): {'tyrell': 6, 'stark': 5, 'lannister': 9, 'tarly': 5, 'baratheon': 9, 'targaryen': 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 compact.

1
2
3
4
5
6

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


print("Longueur du nom par nom de maison avec compréhension:",
      {house: len(house) for house in houses})

Il faut reconnaitre qu’encore une fois, il existe une solution en Python plus intéressante que celle de 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import functools


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

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

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

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.

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’aura pas besoin car on aura une solution plus simple à mettre en oeuvre.

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.

Commencçons par filter.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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.

1
2

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’objet est ici bien sûr de montrer le principe de fonctionnement.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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.

1
2

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.

séquence, réduisant cette séquence grâce à cette fonction ; cette dernière doit prendre en paramètre 2 éléments du même type que les éléments de la séquence ; elle combine successivement chaque élément de la liste avec la fonction. Elle prend éventuellement un troisième paramètre optionnel qui sert de valeur de départ., appliquant la fonction sur les éléments de la séquence pour produire un résultat qui n’est pas nécessairement une séquence, dans le cas de reduce. On verra plus loin que filter et map sont des spécialisations de reduce.

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.

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.

Les exemples de code du billet sont disponibles dans un gist.

Ressources