Salut à tous !

Suite à un récent topic-exo sur les décorateurs, où il a été évoqué que les débutants avaient du mal à se familiariser avec certains aspects de Python proches de la programmation fonctionnelle, j'ai décidé de créer ce topic-TP, qui permettra, je l'espère, de démystifier le sujet, et d'habituer les débutants à utiliser ces notions quelque peu inhabituelles, quoique très puissantes.

La programmation fonctionnelle, c'est quoi ?

Comme on vous l'a déjà probablement trop répété, il existe plusieurs paradigmes de programmation. Parmi eux, on pourra citer le paradigme impératif (à l'image du langage C) et le paradigme objet (que l'on retrouve Java et en C++, par exemple), qui sont grosso-modo les deux plus populaires. Si cette notion de paradigmes ne vous semble pas claire, je vous renvoie à Wikipédia, qui saura vous expliquer cela bien mieux que moi.

L'important à retenir, c'est que ces paradigmes ne sont pas des notions figées dans le marbre, et qu'un même langage peut donner accès à des styles de programmation empruntés à plusieurs paradigmes à la fois. C'est le cas de Python, qui permet de programmer, dans un style impératif, objet, ou fonctionnel.

Tout est objet, même les fonctions !

Ce qui différencie le plus la programmation fonctionnelle des autres styles, c'est probablement la notion que les fonctions sont des entités que l'on peut manipuler comme les autres dans un programme. En ce sens, le fait qu'en Python « tout est objet » nous autorise à manipuler les fonctions comme de simples variables ; on peut donc :

• Assigner une fonction à une variable :
  

  >>> def x2(n):
  ...     return n*2
  ... 
  >>> ma_fonction = x2
  >>> ma_fonction(4)
  8
  

  
  
• Passer une fonction en argument d'une autre fonction :
  

  >>> def applique(fn, arg):
  ...     print("application de la fonction")
  ...     return fn(arg)
  ... 
  >>> applique(x2, 4)
  application de la fonction
  8
  

  
  
• Retourner une fonction, lui assigner des attributs, etc.

Mais… ça sert à quoi ?

Bonne question !
Cela ne sert fondamentalement à rien de plus que ce que vous faites déjà en Python, sauf, dans plusieurs cas que nous allons voir, à le faire de façon plus concise, plus élégante, ou tout simplement plus marrante.

Par exemple, nous allons voir que certaines fonctions classiques de la programmation fonctionnelle permettent d'exprimer une boucle en une seule instruction, sans perdre en lisibilité ni en compréhension.

D'ailleurs, vous ne le savez peut-être pas encore, mais les list comprehensions et les expressions génératrices, que vous utilisez peut-être déjà, sont des notions qui viennent de la programmation fonctionnelle.

Ce topic

Dans ce topic, je vais vous présenter plusieurs petits exercices qui vont, je l'espère, vous familiariser avec la manipulation de fonctions un petit peu à la façon des langages fonctionnels tels que Haskell ou CamL.

Certaines des fonctions que je vais vous demander de programmer en exercice existent déjà dans la bibliothèque standard de Python. Néanmoins, j'ai pu remarquer que la plupart du temps, lorsque l'on apprend un langage fonctionnel, on commence par récrire soi-même ces quelques fonctions de façon à comprendre comment elles marchent, et donc se forger une bonne intuition sur leur utilisation. Je ne vais donc pas déroger à la règle, et les exercices qui vont suivre vont vous faire coder ces quelques incontournables.

Pour réussir ce TP, vous allez devoir suivre une, et une seule règle très simple :



Malgré mes efforts pour rendre mes explications les plus claires possibles, ces exercices vous sembleront peut-être peu intuitifs, trop difficiles, totalement inutiles ou juste sadiques. Si c'est le cas, et que vous bloquez sur quelque-chose, il est inutile de vous énerver. Vous pouvez tout simplement poser des questions sur ce qui ne vous semble pas clair. Le but est que vous réussissiez, avec ou sans aide, à les résoudre vous-mêmes, et non que vous les réussissiez en 30 secondes chrono.

Attaquons !

Map

Connaissez-vous la fonction map ?
Il s'agit d'une fonction built-in de python qui permet d'appliquer, en une seule instruction, une fonction donnée à tous les éléments d'une liste.

Par exemple, au lieu d'écrire :

>>> liste = [1,2,3,4,5]
>>> result = []
>>> for elt in liste:
...     result.append(elt * 2)
... 
>>> result 
[2, 4, 6, 8, 10]

On pourra écrire :

>>> result2 = list(map(x2, liste))
>>> result2
[2, 4, 6, 8, 10]

Note: en Python2, l'appel à list n'est pas nécessaire.

Écrivez une fonction mymap qui prend une fonction et une liste en argument, et retourne une liste contenant le résultat de l'application de la fonction à chaque élément de la liste d'entrée.

[Optionnel] Écrivez une fonction génératrice mymap_gen qui prend un objet itérable en argument et se comporte comme un générateur, qui applique la fonction d'entrée à chaque élément.

Reduce

Il vous est probablement déjà arrivé de coder une fonction qui calcule la somme de tous les éléments d'une liste. En voici un exemple :

>>> def somme(liste):
...     accumulateur = 0
...     for elt in liste:
...         accumulateur = accumulateur + elt
...     return accumulateur
... 
>>> maliste = [1,2,3,4,5]
>>> somme(maliste)
15

Qu'est-ce qui se passe dans cette fonction ?
On définit un accumulateur, on traverse toute la liste en lui ajoutant la valeur de l'élément courant, et on le retourne à la fin.

La fonction reduce permet de généraliser ceci.

>>> def som(acc, val):
...     return acc + val
... 
>>> from functools import reduce
>>> reduce(som, maliste, 0)
15

On lui passe :

• Une fonction qui permet de transformer l'accumulateur :
  ici,
  acc = som(acc, val)
  est strictement équivalent à
  acc = acc + val
  
• une liste sur laquelle on applique cet accumulateur
  
• la valeur initiale de l'accumulateur
  

Écrivez une fonction myreduce qui agit exactement de la même façon que reduce.

Une chose qu'il peut être très intéressant de remarquer, c'est que la fonction map n'est qu'un cas particulier de la fonction reduce, dans lequel l'accumulateur est une liste. C'est la raison pour laquelle je vous propose l'exercice suivant qui vous demandera probablement de réfléchir un coup :

[Optionnel] Écrivez une fonction mymap2, qui réalise la même opération que map, mais en utilisant la fonction reduce. (bonus : Cette fonction peut s'écrire en une seule ligne)

Composition de fonctions

On rentre maintenant dans le vif du sujet. Imaginons que nous voulions appliquer plusieurs fonctions de façon séquencielle. Par exemple :

>>> x2 = lambda a: a * 2
>>> plus5 = lambda a: a + 5
>>> plus5(x2(3)) # (3 * 2) + 5
11
>>> x2plus5 = lambda a: plus5(x2(a))
>>> x2plus5(3)
11

Ici, on dit que la fonction x2plus5 est la composée des fonctions x2 et plus5, c'est-à-dire qu'elle applique à son argument, successivement, la fonction x2 puis la fonction plus5.

Écrivez une fonction compose1 qui prend deux arguments (deux fonctions), et en retourne la fonction composée. Les fonctions en argument seront donnés dans l'ordre de leur application

[Optionnel] Écrivez une fonction compose2 qui prend un nombre arbitraire de fonctions en argument (vous pouvez pour cela utiliser la notation *args), et retourne une fonction qui applique séquenciellement toutes ces fonctions à son entrée ("à la chaîne").

(bonus: 150000 points) cette dernière fonction peut s'écrire en une seule instruction. Regardez les exos précédents. Je détaillerai cette solution plus tard, car une fois que vous avez compris tout ce qui précède, ceci est l'exemple parfait pour vous montrer qu'en réfléchissant "en fonctionnel", on peut réaliser des trucs aussi compliqués au moyen d'une fonction très simple.

Voilà. Ça devrait suffire pour le moment. J'ai d'autres idées d'exercices d'un niveau encore un petit peu plus élevé (presque des décorateurs), que je rajouterai peut-être ici plus tard.

Correction

Ici.

Je les fais pas tous.

mymap2 = lambda f, li : reduce(lambda acc, x : acc + [f(x)], li, [])

compose = lambda *args : lambda x : reduce(lambda acc, f : f(acc), args, x)

Bonjour, excellent topic alors je ne sais pas si j'ai bien compris l'énoncé du premier exercice mais ma solution ressemble à cela (Je suis débutant):

def x2(n):
    return n*2

def mymap(fonc, liste):

    limap = list()

    for e in liste:
        limap.append(fonc(e))

    return limap

liste = [1, 2, 3, 4, 5]

print(mymap(x2, liste))

C'est bien
Maintenant essaie de coder les autres.

Asimoov, c'est un très bon départ.
N'hésite pas à poser des questions si tu bloques sur les autres exos.

Oui, pour la fonction génératrice:

def x2(n):
    return n*2

def mymap_gen(fonc, liste):

    for e in liste:
        yield fonc(e)
    
liste = [1, 2, 3, 4, 5]

for x in mymap_gen(x2, liste):
    
    print(x)

La fonction mymap, le reste je le mettrais en edit quand j'ai un peu de temps

def mymap(fonction, liste):
    return [fonction(i) for i in liste if callable(fonction)]

Citation : fred1599

La fonction mymap […]

Cette réponse est intéressante parce qu'elle montre que les "maps" ne sont rien d'autre qu'une façon générale d'écrire certaines list comprehensions, mais de façon peut-être plus concise.

Edit: oui je m'étais trompé, c'est "map" qui est plus spécifique qu'une list-comprehension.

Pourquoi vérifier si la liste de fonctions est bien une liste de fonctions ?
C'est certainement un choix justifiable mais j'aimerais le comprendre (surtout que de la façon dont tu le fais, tu risques de masquer silencieusement des erreurs).

Ma solution pour l'énoncé n°2:

Écrivez une fonction myreduce qui agit exactement de la même façon que reduce.

def som(acc, val):
    return acc + val

def myreduce(function, iterable, initializer):

    for e in iterable:
        function(initializer, e)
        initializer += e

    return initializer

liste = [1, 2, 3, 4, 5]

print(myreduce(som, liste, 0))

Edit: le mieux c'est quoi qu'on mette toutes ses réponses dans un même message ?

Bonsoir,

Je bloque bien sur le recodage de map via reduce.
Aussi, vous pourriez me dire si au moins ma fonction reduce actuelle est correcte?
C'est bien le fonctionnement attendu?

C'est également valable pour mymap et mymap_gen.

BTW, voici une correction non-détaillée pour la composition. Je fournirai les explications et le raisonnement qui permettent d'arriver à ce résultat plus tard, quand plus de gens auront tenté le coup.



GurneyH : Ta fonction reduce est à un tout petit détail près la bonne.
Son seul défaut est l'ordre des arguments dans la fonction "accumulatrice". On doit passer l'accumulateur en premier argument, en principe.
Sur ton exemple ce n'est pas grave, mais il y a des cas où cela joue.

Pour coder map avec reduce, qu'est-ce qui te pose problème exactement ?
L'accumulateur est une liste, à laquelle tu ajoutes au fur et à mesure le résultat de l'application d'une fonction à un élément de la liste d'entrée.

Citation : Asimoov

Ma solution pour l'énoncé n°2:

Écrivez une fonction myreduce qui agit exactement de la même façon que reduce.

def som(acc, val):
    return acc + val

def myreduce(function, iterable, initializer):

    for e in iterable:
        function(initializer, e)
        initializer += e

    return initializer

liste = [1, 2, 3, 4, 5]

print(myreduce(som, liste, 0))

Edit: le mieux c'est quoi qu'on mette toutes ses réponses dans un même message ?

Non, c'est mieux pour suivre là. Par contre vérifie le comportement de ta fonction reduce, ce n'est pas celui attendu. Attention, elle ne doit pas marcher que sur des additions, et la fonction n'est pas une fonction qui « fait » mais qui « renvoie » quelque chose.

gurneyh, ta fonction est bonne, mais attention au choix de l'accumulateur de départ. Tu as pris 0, ce qui est intéressant pour l'addition, mais si je veux utiliser ta fonction pour faire le produit de tous les éléments de ma liste, le 0 n'est pas intéressant. Une bonne solution serait de rendre cet argument par défaut égal au premier élément de la liste (attention à ne pas le compter dans la boucle du coup). Il y a plusieurs façons de faire.

En effet Orrita, merci.

Dans ce genre, c'est mieux, non?


edit:
Nohar, désolé je n'avais pas vu ta réponse précédente.
Heu oui, en effet j'inversais l'ordre des arguments.



Pour mes difficultés, à recoder la fonction map, je sais pas comment l'expliquer.
J'ai l'impression d'avoir un argument en trop.

GurneyH, c'est beaucoup mieux, mais ta fonction accumulatrice prend encore ses arguments dans le mauvais ordre.

Ça va poser problème plus loin.

Ok merci Orrita:

def som(acc, val):
    return acc + val

def myreduce(function, iterable, initializer):

    for e in iterable:
        initializer = function(initializer, e)

    return initializer

liste = [1, 2, 3, 4, 5]

print(myreduce(som, liste, 0))

@GurneyH, OK, je vais t'aider un peu plus.

Reduce accumule le résultat de l'application d'une fonction à tous les éléments d'une liste, dans un objet accumulateur. Pour cela, il faut lui passer la fonction accumulatrice, la liste à réduire, et l'état initial de l'accumulateur.

On peut considérer, d'autre part, que map, quant à elle, "accumule" ("empile") le résultat de l'application d'une fonction à tous les éléments d'une liste, dans une nouvelle liste.
Ainsi, il faut passer à reduce la fonction accumulatrice, la liste à "réduire" (ici c'est à "mapper") et l'état initial de la liste dans laquelle on accumule (on empile) les résultats.

C'est plus clair ?

Ce qui est un petit peu compliqué là-dedans, c'est que tu dois définir la fonction accumulatrice par rapport à la fonction passée en argument de map. Donc en gros, tu dois définir ta fonction accumulatrice "à l'intérieur" de ta fonction map. C'est peut-être ça qui bloque…

Pour résumer, ta fonction aura cette forme :

def map(fn, liste):
    def accumule(liste_acc, element):
        # faire quelquechose qui dépend de 'fn'

    return reduce(accumule, liste, [])

@Asimoov: c'est bon.

Bon étant donné qu'il y a pas mal de réponses je met à la suite des posts

def myreduce(fonction, liste):
    for ind, _ in liste:
        try:
            acc += fonction(liste[ind], liste[ind+1])
        except IndexError:
            pass
    return acc

Edit: Gouré

Fred, c'est beaucoup plus simple que ça.

Déroule mentalement ton exemple dans le cas d'une somme avec la fonction som…

Edit : je n'ai pas montré la fonction d'exemple de cette manière dans l'exo par hasard.
Autre indice : tu n'as as besoin de l'opérateur +=. Il va t'embrouiller plus qu'autre-chose.

Merci beaucoup nohar, tu m'as mâché le travail.

j'ai compris je pense après ton explication, mais je n'aurai pas pondu ça seul, je pense.

Citation : GurneyH

Merci beaucoup nohar, tu m'as mâché le travail.

Y'a pas de soucis. Le plus rigolo reste à venir.

Alors je ne sais pas si ça marche pour tous les cas et si c'est une méthode très conventionnelle, mais j'ai souhaité vraiment simuler la fonction reduce à savoir si on omet l'initialisateur cela marche quand même:

def som(acc, val):
    return acc * val

def myreduce(function, iterable, initializer= 0):

    while True:
        for e in iterable:
            initializer = function(initializer, e)
        if initializer != 0:
            break
        else:
            initializer = 1

    return initializer

liste = [1, 2, 3, 4, 5]

print(myreduce(som, liste))

Edit: Effectivemment ça ne marche pas à tous les coups

@Asimoov : c'est bien plus compliqué que nécessaire.

L'idée, quand on omet de préciser l'état initial de l'accumulateur, c'est d'initialiser celui-ci avec le premier élément de la liste (même si ce comportement n'est pas toujours applicable, comme tu le verras à la question suivante).

En ce sens, tu ne peux pas parier sur le fait que l'accumulateur va contenir des nombres : ça peut être absolument tout et n'importe quoi ; des nombres, des strings, des objets, des fonctions…, donc le mettre par défaut à None est une meilleure idée.

Bon je l'ai pas aimé celui là ce qui prouve que j'ai du mal avec le fonctionnel

def myreduce(fonction, liste, acc=0):
    for i in liste:
        acc = fonction(acc, i)
    return acc

def func(a, b):
    return a*b

print(myreduce(func, [12, 5, 9], 1))

Fred : c'est pas un drame si tu mets du temps à choper le truc hein.

C'est avant tout une façon de penser les fonctions qui est différente de ce à quoi on peut être habitué, donc c'est sûr que ça peut ne pas rentrer du premier coup.

Enfin sinon, en l'occurence, ta fonction myreduce est la bonne, à ceci près que la valeur par défaut de acc devrait être None plutôt que 0, comme je l'ai expliqué juste au-dessus.

Ok merci beaucoup à toi.
Je viens de voir la réponse de GurneyH.

Le dernier pour ce soir.



Ce qui m'intrigue, c'est que je pensais que la fonction inter n'était pas accessible en dehors de compose1.
Enfin, elle ne l'est pas, mais je le comprend comme:
On retourne une référence à cette fonction.

C'est particulier, je trouve.

edit:

En effet orrita.
En y pensant c'est pareil, lorsque je retourne une liste par exemple.
je n'ai pas accès au nom qui l'identifie dans la fonction, mais elle existe tout de même.
Je pense trop C.

Remplace inter par n'importe quelle valeur non fonctionnelle : ça marche pareil en fait

Oufff mon crâne, c'est le dernier pour moi ce soir aussi, j'ai fais la mymap2

def mymap2(fonction, liste):
    def another(x):
        return fonction(x)
    return [another(i) for i in liste]

Edit : Ah non c'est pas celle là

@GurneyH:

Tu es en train de toucher intuitivement du doigt la notion de closure (fermeture), en effet.

Tu retournes une fonction interne, qui est définie en fonction des arguments de la fonction externe, donc on pourrait croire que ça devrait poser problème (les "constantes" de la fonction interne seront-elles encore définies ?) mais ce n'est pas si différent que ça de l'implémentation de map au moyen de reduce.

Un truc intéressant à remarquer, c'est que tu as créé une fonction qui prend des fonctions en argument, et retourne une nouvelle fonction comme résultat. C'est exactement ce qui se passe lorsque l'on crée un décorateur.

Il ne te reste plus à faire que la question la plus intéressante (mais qui demande vraiment, pour trouver l'astuce, de considérer que les fonctions ne sont que des objets comme les autres).

@Fred: presque ! Mais tu n'appelles pas reduce… C'est gênant !