Programmation fonctionnelle

Histoire

La programmation fonctionnelle est née avec le langage Lisp (List Processing) créé par John McCarthy en 1958, comme mise en oeuvre du lambda-calcul . Le langage Lisp a eu ensuite de nombreux descendants dont Common Lisp et Scheme.

Le langage ML , créé par Robin Milner en 1970, a initialement été destiné à l’écriture de démonstrateurs. Son typage fort en fait un langage formel très robuste et adapté aux preuves. Le langage ML a eu de nombreux descendants dont Standard ML, CAML (INRIA, 1985) et Haskell (1990, à évaluation paresseuse).

Les idées introduites par ces langages ont été reprises dans la plupart des langages modernes qui offrent la possibilité, entre autres, de programmer en suivant un paradigme fonctionnel.

Exemple introductif - Traitement de listes

Voici comment s’écrit la définition d’une fonction calculant le dernier élément d’une liste.

En Lisp, les listes se notent avec des parenthèses et le traitement de listes repose sur deux primitives car et cdr pour accéder au premier élément et au reste d’une liste. On remarque la notation préfixée des opérateurs et l’usage abondant des parenthèses qui servent à la fois à structurer les données et les programmes.

(defun dernier (liste)
  (cond ((null (cdr liste)) (car liste))
        (t (dernier (cdr liste)))))

(dernier '(2 4 3 9))

9

À condition de définir au préalable les fonctions utilisées, on peut, en Python, définir la fonction dernier, selon le paradigme fonctionnel.

def listevide():
     return []

def premier(liste):
    return liste[0]

def reste(liste):
    return liste[1:]

def dernier(liste):
    return premier(liste) if reste(liste) == listevide() else dernier(reste(liste))

print(dernier([2, 4, 3, 9]))

9

Exemple introductif - Calcul arithmétique

Pour calculer le pgcd de deux nombres entiers positifs donnés, on peut, dans un style impératif, écrire une boucle qui remplace le couple (a, b) par (b, a modulo b) jusqu’à ce que le reste soit nul.

def pgcd(a, b):
    x, y = a, b
    while y != 0:
        x, y =y, x % y
    return x

print(pgcd(56, 184))

8

Dans un style fonctionnel, on écrit une fonction qui renvoie le résultat en précisant la valeur dans les cas simples et en se ramenant, le cas échéant, par appel récursif, à des cas plus simples.

def pgcd(a, b):
    return a if b == 0 else pgcd(b, a) if b > a else pgcd(a - b, b)

print(pgcd(56, 184))

8

Le paradigme fonctionnel

Les notions de programmation utilisées dans les deux exemples introductifs sont :

• la notion de fonction qui est évidemment centrale,
• la composition de fonctions, qui permet de faire deux calculs successifs : par exemple dernier(reste(liste)) applique la fonction dernier au résultat de l’application de la fonction reste à la liste liste,
• la possibilité d’écrire des expressions conditionnelles, en Python sous la forme : exp1 if cond else exp2,
• la récursivité qui permet de réduire un calcul complexe à un cas plus simple.

L’usage de toutes ou une partie de ces quatre notions est caractéristique de la programmation fonctionnelle.

Par contre, on n’a pas utilisé :

• de variable,
• d’instruction élémentaire : affichage ou affectation,
• de boucle pour répéter des instructions
• de séquence pour enchaîner des instructions
• d’instruction conditionnelle.

Ces notions sont, quant à elles, les briques de base de la programmation impérative.

Correspondances

• En programmation fonctionnelle, la composition remplace la séquence.
• L’écriture d’expressions - en particulier conditionnelles - remplace l’écriture d’instructions.
• La récursivité remplace l’itération.

Activité. Écrire en Python, selon le paradigme fonctionnel, une fonction inverse(s) qui renvoie une chaîne de caractères inversée, en n’utilisant que s[0], s[1:], la chaîne vide '' et l’opération +. Voir la fiche d’exercices pour d’autres problèmes de réécriture impératif vers fonctionnel.

Les fonctions d’ordre supérieur

Dans un langage fonctionnel, une fonction est une expression comme une autre, qui peut donc être passée en paramètre ou renvoyée comme résultat.

En Python, une fonction peut être écrite par la notation lambda, puis être nommée - ou pas.

double = lambda x: 2 * x

print(double(16))

32

Fondamentalement, cela permet de considérer un programme comme une donnée et donc de fabriquer des programmes qui fabriquent ou testent ou vérifient d’autres programmes.

Cela peut amener à écrire des programmes très abstraits mais fort utiles dans au moins deux cas d’usage :

• les fonctions usuelles de bibliothèques qui admettent une fonction en entrée ;
• les schémas de récurrence classiques sur les listes.

Utiliser des fonctions en paramètres

La fonction standard sorted prend en paramètre - nommé key - une fonction calculant la clé sur laquelle effectuer le tri. Pour comparer deux éléments, ce sont leurs clés qui sont comparées.

help(sorted)

Help on built-in function sorted in module builtins:

sorted(iterable, /, *, key=None, reverse=False)
    Return a new list containing all items from the iterable in ascending order.

    A custom key function can be supplied to customize the sort order, and the
    reverse flag can be set to request the result in descending order.

animaux = ['veau', 'vache', 'cochon', 'anaconda', 'chat', 'chien', 'ver', 'poule', 'souris']
print(sorted(animaux))

['anaconda', 'chat', 'chien', 'cochon', 'poule', 'souris', 'vache', 'veau', 'ver']

On peut utiliser la fonction len pour trier les chaines selon leur longueur.

animaux = ['veau', 'vache', 'cochon', 'anaconda', 'chat', 'chien', 'ver', 'poule', 'souris']
print(sorted(animaux, key = len))

['ver', 'veau', 'chat', 'vache', 'chien', 'poule', 'cochon', 'souris', 'anaconda']

On peut aussi fournir comme clé une fonction écrite avec la notation lambda. Dans cet exemple, on trie des points selon leur distance de Manhattan au point (0,0).

points = [(2, 4), (3, 5), (1, 1), (7,5), (3,1), (5,0)]
print(sorted(points, key = lambda p: p[0] + p[1]))

[(1, 1), (3, 1), (5, 0), (2, 4), (3, 5), (7, 5)]

Activité. Trier la liste d’enregistrements [[5012, 'Jean', 'Dupond'], [4086, 'Jacques', 'Dupond'], ...] par ordre alphabétique de nom, puis de prénom si les noms sont identiques. Voir la fiche d’exercices pour d’autres problèmes de tri avec sorted et lambda.

Utiliser une fonction d’ordre supérieur

Les mêmes schémas de récurrence se retrouvent fréquemment. Par exemple, après avoir calculé la liste des doubles des nombres de 0 à 9, la liste des cubes d’une liste d’entiers, la liste des longueurs d’une liste de chaînes de caractères… on peut généraliser en constatant qu’on a, à chaque fois, calculé la liste des résultats d’un calcul appliqué successivement à chaque élément d’une liste.

double = lambda x: 2 * x

def listedouble (liste):
    return ([] if liste == [] else [double(liste[0])] + listedouble(liste[1:]))

print(listedouble([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]))

[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

La fonction map peut faire ce travail, si on lui fournit une fonction et une liste. On applique la fonction list après map, car sinon, le résultat est un itérateur, qui ne calcule pas immédiatement la liste de ses valeurs successives.

double = lambda x: 2 * x

print(list(map(double, range(10))))

[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

print(list(map(lambda x: x ** 3, [3, 8, 2, 1])))

[27, 512, 8, 1]

print(list(map(len, ['veau', 'vache', 'cochon', 'anaconda', 'ver'])))

[4, 5, 6, 8, 3]

L’usage de map peut cependant être évité en Python, grâce à l’écriture par compréhension qui effectue le même calcul en construisant la liste des résultats.

double = lambda x: 2 * x

liste_doubles = [double(i) for i in range (10)]

print(liste_doubles)

[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

La fonction filter

La fonction filter sélectionne les éléments d’une liste qui vérifient une condition donnée. Comme map, elle prend une fonction en paramètre (un prédicat, c’est-à-dire une fonction renvoyant un booléen) et renvoie un itérateur.

nombres = [3, 7, 2, 9, 4, 1, 8, 5]
pairs = list(filter(lambda x: x % 2 == 0, nombres))
print(pairs)

[2, 4, 8]

On peut combiner filter et map pour sélectionner puis transformer :

nombres = [-3, 5, -1, 8, -2, 7]
absolus_negatifs = list(map(abs, filter(lambda x: x < 0, nombres)))
print(absolus_negatifs)

[3, 1, 2]

L’équivalent en compréhension est souvent plus lisible en Python :

absolus_negatifs = [abs(x) for x in nombres if x < 0]

La fonction reduce

Complément hors programme. La fonction reduce n’est pas exigible au baccalauréat ; elle complète map et filter.

La fonction reduce du module functools accumule un résultat en appliquant une fonction de deux arguments successivement à chaque élément d’une liste, de gauche à droite.

from functools import reduce
somme = reduce(lambda acc, x: acc + x, [3, 7, 2, 9], 0)
print(somme)

21

Le troisième argument (0) est la valeur initiale de l’accumulateur. À chaque étape, acc prend la valeur du résultat précédent et x prend l’élément suivant de la liste : 0+3=3, puis 3+7=10, puis 10+2=12, puis 12+9=21.

Contrairement à map et filter qui renvoient un itérateur (à convertir avec list), reduce renvoie une valeur unique. C’est une fonction d’ordre supérieur classique en programmation fonctionnelle.

Fonctions pures et effets de bord

Un concept central du paradigme fonctionnel est celui de fonction pure. Une fonction est pure si elle vérifie deux propriétés :

• elle renvoie toujours le même résultat pour les mêmes arguments (déterminisme) ;
• elle ne produit aucun effet de bord : pas de modification de variable globale, pas d’écriture dans un fichier, pas d’affichage.

# Fonction pure : toujours le même résultat, aucune modification extérieure
def double(x):
    return 2 * x

# Fonction impure : modifie une variable globale (effet de bord)
compteur = 0

def incrementer():
    global compteur
    compteur += 1
    return compteur

Après deux appels à incrementer(), les résultats sont différents (1 puis 2), alors que double(5) renvoie toujours 10.

Un piège fréquent en Python concerne la mutation des listes :

# Fonction impure : modifie la liste passée en paramètre
def ajouter(x, L):
    L.append(x)
    return L

# Fonction pure : crée une nouvelle liste
def ajouter_pur(x, L):
    return L + [x]

Avec ajouter(4, ma_liste), la liste originale est modifiée (effet de bord). Avec ajouter_pur(4, ma_liste), l’originale reste intacte. En programmation fonctionnelle, on préfère toujours créer de nouvelles structures plutôt que modifier les existantes.

Synthèse : comparer les trois paradigmes

Le programme de NSI distingue trois grands paradigmes de programmation : impératif, fonctionnel et objet. Pour bien les différencier, résolvons un même problème avec chacun d’eux.

Problème. On dispose d’une liste de notes (entiers entre 0 et 20). On souhaite calculer la moyenne des notes supérieures ou égales à 10.

Style impératif

On utilise des variables, des boucles et des instructions d’affectation. Le programme décrit étape par étape comment obtenir le résultat.

def moyenne_au_dessus_imperatif(notes):
    somme = 0
    compteur = 0
    for note in notes:
        if note >= 10:
            somme = somme + note
            compteur = compteur + 1
    if compteur == 0:
        return 0
    return somme / compteur

print(moyenne_au_dessus_imperatif([8, 15, 12, 7, 18, 9, 14]))

14.75

Le paradigme impératif se caractérise par l’utilisation de variables modifiables, de boucles et d’instructions séquentielles. C’est le style le plus intuitif pour les débutants.

Style fonctionnel

On compose des fonctions sans modifier de variables. Le programme décrit ce que l’on veut obtenir plutôt que comment l’obtenir.

def moyenne_au_dessus_fonctionnel(notes):
    au_dessus = list(filter(lambda n: n >= 10, notes))
    return sum(au_dessus) / len(au_dessus) if au_dessus else 0

print(moyenne_au_dessus_fonctionnel([8, 15, 12, 7, 18, 9, 14]))

14.75

Le paradigme fonctionnel repose sur la composition de fonctions, l’absence d’effets de bord (pas de modification de variables) et l’utilisation de fonctions d’ordre supérieur comme filter. On aurait pu aussi utiliser une liste en compréhension : [n for n in notes if n >= 10].

Style objet

On modélise le problème à l’aide d’un objet qui encapsule les données et les traitements associés.

class ReleveDeNotes:
    def __init__(self, notes):
        self.notes = notes

    def au_dessus(self, seuil):
        return [n for n in self.notes if n >= seuil]

    def moyenne_au_dessus(self, seuil):
        selection = self.au_dessus(seuil)
        if len(selection) == 0:
            return 0
        return sum(selection) / len(selection)

releve = ReleveDeNotes([8, 15, 12, 7, 18, 9, 14])
print(releve.moyenne_au_dessus(10))

14.75

Le paradigme objet organise le code autour d’objets qui regroupent des attributs (les données) et des méthodes (les traitements). L’avantage est la modularité : on peut réutiliser la classe ReleveDeNotes dans d’autres contextes, l’enrichir de nouvelles méthodes, etc.

Récapitulatif

Python est un langage multiparadigme : il permet de programmer dans les trois styles, et même de les combiner dans un même programme. Le choix du paradigme dépend du problème à résoudre et du contexte.