Posts Tagged ‘Programmation fonctionnelle’

Les fonctions anonymes lambda en Python : print, expressions conditionnelles et récursivité

samedi, décembre 24th, 2016

Si Python n’est pas un langage de programmation fonctionnelle, il possède cependant des fonctions anonymes lambda qui sont typiques de cette famille de langages. Ces fonctions sont réputées peu puissantes en Python car elle ont été volontairement limitées syntaxiquement à une expression, sans possibilité d’utiliser des instructions. Pourtant, nous allons voir qu’elles ont dans ce langage quelques particularités intéressantes.

Print

L’instruction print est devenue une fonction print() – et donc une expression – dans Python 3 suite à la PEP 3105. Ainsi, si vous utilisez print dans une fonction lambda, Python 2 lèvera une exception SyntaxError: invalid syntax alors que Python 3 l’acceptera :

>>> pr = lambda x : print(x)
>>> pr('OK en Python 3')
OK en Python 3

Expressions conditionnelles

Introduites (tardivement) dans Python 2.5 suite à la PEP 308, les expressions conditionnelles sont une manière simplifiée de réaliser grâce à l’opérateur ternaire true_value if condition else false_value la suite d’instructions suivante :

if condition:
    x = true_value
else:
    x = false_value

Comme leur nom l’indique, les expressions conditionnelles sont bien des expressions et elles permettent donc de mettre de la logique dans les fonctions lambda. Cela était déjà possible précédemment, en abusant un peu les opérateurs logiques classiques avec condition and true_value or false_value, mais c’est une méthode que je déconseille car elle n’est pas totalement fiable pour certaines valeurs de condition.

Dans l’exemple suivant, j’utilise une expression conditionnelle avec la fonction print() et donc Python 3, ce dernier me permettant d’utiliser un nom de variable avec le caractère non-ASCII é (PEP 3131) :

>>> majorité = lambda x : print("mineur") if x < 18 else print("majeur")
>>> majorité(15)
mineur
>>> majorité(25)
majeur

Récursivité

Le principe des fonctions anonymes étant de ne pas être nommées, il est donc logiquement difficile de les appeler. Ainsi, les fonctions anonymes de certains langages fonctionnels ne peuvent pas s’appeler, et donc ne peuvent pas être récursives. En Python, les lambda sont un sucre syntaxique limité des fonctions normales mais elles leur sont sémantiquement équivalentes, et elles peuvent donc parfaitement s’appeler récursivement.

En utilisant une expression conditionnelle et la récursivité on peut ainsi facilement implémenter l’algorithme récursif naïf de la très classique suite de Fibonacci :

>>> fib = lambda x : x if x < 2 else fib(x - 1) + fib(x - 2)
>>> fib(1)
1
>>> fib(10)
55
>>> fib(25)
75025

N’essayez pas d’aller beaucoup plus haut pour tester cet algorithme de complexité exponentielle, mais il démontre bien la puissance quelque peu surprenante des fonctions lambda en Python.

Compréhension de liste

On peut enfin ajouter que l’usage de compréhension de liste permet aisément de faire une boucle dans une fonction lambda :

>>> incr = lambda liste : [i + 1 for i in liste]
>>> incr([1, 45, 340])
[2, 46, 341]

La compréhension de liste en Python, une syntaxe moderne pour map() et filter()

lundi, décembre 5th, 2011

La compréhension de liste est un syntactic sugar pour les fonctions classiques de la programmation fonctionnelle que sont map() et filter(). Disponible depuis Python 2.0, la compréhension de liste devrait à terme amener à la disparition des fonctions map() et filter() du langage Python, ce que Guido van Rossum avait déjà envisagé pour Python 3.

Ainsi, si vous avez du « vieux code » utilisant ces fonctions, je vous encourage à le porter vers cette nouvelle syntaxe beaucoup plus lisible et plus pythonique. J’espère que cet article pourra aider certains à éviter les pièges qui pourraient apparaître devant eux lors de cette démarche.

map()
Commençons d’abord par la fonction map(), dont la syntaxe est map(fonction, liste). Prenons un exemple très simple, avec une fonction anonyme lambda qui à tout x élément de la liste des chiffres de 0 à 9 associe 2 fois x.

>>> map(lambda x: 2*x, range(10))
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

On obtient l’équivalent de la fonction map() avec une compréhension de liste de la forme [fonction(x) for x in liste], ce qui donne pour notre exemple :

>>> [2*x for x in range(10)]
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

filter()
La syntaxe de la fonction filter() est filter(fonction, liste). Prenons ici aussi un exemple très simple, avec une fonction anonyme lambda qui n’est Vrai pour chaque x élément de la liste des chiffres de 0 à 9 que s’il est strictement supérieur à 5.

>>> filter(lambda x: x>5, range(10))
[6, 7, 8, 9]

On obtient l’équivalent de la fonction filter() avec une compréhension de liste de la forme [x for x in liste if fonction(x)], et donc notre exemple devient :

>>> [x for x in range(10) if x>5]
[6, 7, 8, 9]

Un des grands intérêts des fonctions est de pouvoir être composées. Cependant, cette opération de composition n’est pas anodine, et il faut bien envisager les différents cas pour ne pas commettre d’erreur.

map o filter()
La composition notée map o filter() revient à map(filter()), c’est-à-dire à appliquer d’abord la fonction filter(), puis la fonction map(). Si nous combinons nos deux premiers exemples, nous obtenons :

>>> map(lambda x: 2*x, filter(lambda x: x>5, range(10)))
[12, 14, 16, 18]


On obtient l’équivalent de la composition de fonction map o filter() avec une compréhension de liste de la forme [fonction_map(x) for x in liste if fonction_filter(x)], ce qui donne ici :

>>> [2*x for x in range(10) if x>5]
[12, 14, 16, 18]

La composition de fonction map o filter() ne pose pas de problème.

On remarque que plus l’on compose des fonctions map() et filter(), plus l’avantage syntaxique de lisibilité et de compréhensibilité des compréhensions de liste augmente.

filter o map()
Mais qu’en est-il de la composition notée filter o map(), qui revient à filter(map()), c’est-à-dire à appliquer d’abord la fonction map(), puis la fonction filter(). Si nous combinons ici aussi nos deux premiers exemples, nous obtenons :

>>> filter(lambda x: x>5, map(lambda x: 2*x, range(10)))
[6, 8, 10, 12, 14, 16, 18]

Le résultat retourné est différent de celui obtenu à l’exemple précédent avec une compréhension de liste de la forme [fonction_map(x) for x in liste if fonction_filter(x)]. En fait, la bonne compréhension de liste est :

>>> [2*x for x in range(10) if 2*x>5]
[6, 8, 10, 12, 14, 16, 18]

Nous voyons que la composition de fonction filter o map() pose des problèmes, et qu’il faudra y porter une attention particulière en cas de conversion de vieux code fonctionnel en compréhensions de liste.

filter o filter()
La composition notée filter o filter() revient à filter(filter()), c’est-à-dire à appliquer deux fois de suite la fonction filter(). Nous allons donc rajouter une deuxième condition à notre premier exemple de filter(), qui sera que chaque élément x devra en plus être strictement inférieur à 8.

>>> filter(lambda x: x<8, filter(lambda x: x>5, range(10)))
[6, 7]

Le même résultat est obtenu en inversant l’ordre des deux conditions :

>>> filter(lambda x: x>5, filter(lambda x: x<8, range(10)))
[6, 7]

La composition filter o filter() est commutative, et peut en fait facilement se factoriser sous la forme :

>>> filter(lambda x: x>5 and x<8, range(10))
[6, 7]

On obtient l’équivalent de la composition de fonction filter o filter() avec une compréhension de liste de la forme [x for x in liste if fonction_filter_1(x) and fonction_filter_2(x)], ce qui donne ici :

>>> [x for x in range(10) if x>5 and x<8]
[6, 7]

La composition de fonction filter o filter() ne pose pas de problème.

map o map()
Mais qu’en est-il de la composition notée map o map(), qui revient à map(map()), c’est-à-dire à appliquer deux fois de suite la fonction map() ? Rajoutons une deuxième fonction à notre premier exemple de map(), qui à chaque x associera x plus 1.

>>> map(lambda x: x+1, map(lambda x: 2*x, range(10)))
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

et

>>> map(lambda x: 2*x, map(lambda x: x+1, range(10)))
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

ne donnent pas les mêmes résultats. La composition map o map() n’est pas commutative. On obtient l’équivalent de la composition de fonction map o map() avec une compréhension de liste de la forme [fonction_map_2(x) for x in [fonction_map_1(x) for x in liste]], ce qui donne ici :

>>> [x+1 for x in [2*x for x in range(10)]]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

et

>>> [2*x for x in [x+1 for x in range(10)]]
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

Il est possible de factoriser les deux fonctions map() comme nous l’avons fait pour les fonctions filter(), mais il faut faire très attention à l’ordre de composition des fonctions. Dans le premier cas on a (2*x)+1 = 2*x+1 qui donne :

>>> [2*x+1 for x in range(10)]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

et dans le deuxième cas on obtient 2*(x+1) = 2*x+2 qui produit :

>>> [2*x+2 for x in range(10)]
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

Nous voyons que la composition de fonction map o map() pose des problèmes.

Pour ne pas tomber dans des pièges, il suffit de retenir que toutes les compositions de fonctions qui commencent par une fonction map() sont dangereuses, alors que celles commençant par une fonction filter() sont sans danger.

Pour mon plus grand bonheur, la syntaxe de compréhension de liste rend particulièrement pythonique et centrale au langage Python une partie de la sémantique de la programmation fonctionnelle qui y était jusqu’à présent mal intégrée et mal aimée. Encore une fois, et même si certains de mes professeurs d’informatique ne l’ont jamais accepté, sans une bonne syntaxe, une sémantique géniale n’est rien.

Head et tail de liste en Python 3

samedi, avril 23rd, 2011

Bien que Python ne soit pas un langage de programmation fonctionnelle, il incorpore un certain nombre de fonctionnalités typiques de ces langages. Ainsi les fonctions anonymes lambda, la compréhension de liste, ou encore les fonctions built-in map(), filter() et reduce() (cette dernière ayant été supprimée dans Python 3).

La programmation fonctionnelle est caractérisée par une utilisation intensive des listes, et en particulier par de nombreuses opérations récursives sur ces dernières. On est donc souvent amené à vouloir récupérer le premier élément d’une liste, sa tête ou head, et l’ensemble des éléments restants, sa queue ou tail. Ce qui s’écrit donc trivialement avec la fonction f() retournant une liste :

head, tail = f()[0], f()[1:]

Le premier problème ici est le double appel de la fonction f(), que l’on peut facilement corriger grâce à l’utilisation d’une variable intermédiaire result :

result = f()
head, tail = result[0], result[1:]

Le second problème est la lourdeur syntaxique de l’ensemble, avec la variable intermédiaire et le double usage du [] (le __getitem__ des listes en Python). On aimerait bien à la place avoir une syntaxe plus adaptée, c’est-à-dire plus proche de celles utilisées par les langages de programmation fonctionnelle, comme par exemple Erlang :

[Head|Tail] = Result

Et comme toujours avec Python, le langage se bonifie grâce à une PEP (Python Enhancement Proposal), en l’occurence la PEP 3132 intitulée Extended Iterable Unpacking. Ainsi, depuis Python 3.0, on peut utiliser une nouvelle syntaxe qui reprend celle des star-args (*args) des fonctions Python :

head, *tail = result

Ceci se teste facilement dans un shell Python 3 :

>>> result = [1, 2, 3, 4]
>>> head, *tail = result
>>> head
>>> 1
>>> tail
>>> [2, 3, 4]

On a donc maintenant une syntaxe tout à fait satisfaisante, très lisible et facilitant un style de programmation fonctionnel. Ce qui est encore plus intéressant avec cette notation, c’est qu’elle ne se limite pas au couple head et tail, et peut ainsi être déclinée de bien des manières tout à fait intéressantes comme par exemple :

>>> result = [1, 2, 3, 4]
>>> head, *body, tail = result
>>> head
>>> 1
>>> body
>>> [2, 3]
>>> tail
>>> 4

Python 3 est sorti depuis plus de deux ans et, sans être révolutionnaire, il apporte de nombreuses améliorations à Python 2 qui valent le coup d’être découvertes et utilisées !