====== Programmation fonctionnelle ======

===== Paradigmes =====

Supposons que l'on cherche le **minimum** d'un tableau

=== style impératif en mode itératif ===

<code lang-none>
MINIMUM tableau:
    m = tableau[0]
    POUR item DANS tableau:
        SI item < m:
            m = item
    RENVOYER m
</code>

On constate l'utilisation d'une variable ''m'' susceptible de changer de valeur et de structure de contrôle du flux d'exécution : ''POUR'', ''SI''

=== style impératif en mode récursif ===

<code lang-none>
MINIMUM tableau:
    m = tableau[0]
    SI LONGUEUR(tableau) == 1:
        RENVOYER m
    SINON:
        n = MINIMUM tableau[1:]
        SI m <= n:
            RENVOYER m
        SINON:
            RENVOYER n
</code>

=== style déclaratif ===

<code lang-none>
MINIMUM tableau:
    plus petite valeur entre tableau[0] et MINIMUM(tableau[1:])
</code>

Dans cette approche il n'y a pas de variable et il n'y a pas de structure de flux de contrôle.

<WRAP tip>On trouve des ''if'' en programmation fonctionnelle. Difficile de faire sans. Ils sont néanmoins plus contraignants.</WRAP>

Dans le style déclaratif on rencontre trois cas :

  * Le paradigme **descriptif** : //HTML//, //LaTex//... le programme se contente de décrire.
  * Le paradigme **fonctionnel** : //Caml//, //Lisp//, //Haskell// pour lesquels les programmes sont des listes de fonctions mathématiques
  * Le paradigme **logique** : //Prolog//. Le programme est une liste de déclaration logiques.

**Remarque :** Les langages fonctionnels vont avoir une préférence pour les structures récursives et donc pour les récursions terminales.

===== Effets de bords =====

On appelle **effet de bord** -- traduction mot-à-mot de //side-effect// qui se traduirait plutôt par //effet secondaire// -- la situation où une fonction peut interagir avec le contexte extérieur.

La programmation fonctionnelle a pour objectif d'**interdire les effets de bords**.

==== Premier exemple, l'extérieur agit sur l'intérieur ====

<code python>
def ma_fonction(x):
    if i > 0:
        return 2*x
    else:
        return 3*x
</code>

Dans cette fonction ''i'' n'étant pas définie à l'intérieur de la fonction, lors de l'exécution, Python **cherchera** un ''i'' définit **à l'extérieur**. Testons en console.

<code python>
>>> i = 1
>>> ma_fonction(3)
6
>>> i = 0
>>> ma_fonction(3)
9
</code>

Le fonction n'est pas une fonction mathématique car ''ma_fonction(3)'' n'a pas une seule valeur possible. Autrement dit, ''ma_fonction(x)'' a une entrée cachée.

Il sera difficile de contrôler les erreurs.

==== Deuxième exemple, l'intérieur agit sur l'extérieur ====

Prenons une fonction calculant la somme des valeurs d'un tableau mais qui pour cela vide le tableau.

<code python>
def somme(tableau):
    s = 0
    while len(tableau) > 0:
        s += tableau.pop()
    return s        
</code>

Normalement, quand on fournit un argument à une fonction, on s'attend à ce que la fonction ne modifie pas l'argument. Mais ici :

<code python>
>>> tableau = [1, 4, 9, 17]
>>> somme(tableau)
31
>>> tableau
[]
</code>

Le passage par la fonction ''somme'' a vidé le tableau.

===== Types immuables =====

<wrap tip>On rencontre parfois l'anglicisme **immutable**.</wrap>

En Python, les types ''str'' et ''tuple'' sont **immuables**.

Cela peut sembler contraignant mais a des avantages : Des types immuables ne risquent pas les effets de bords.

Prenons un exemple d'une fonction ajoutant un caractère au bout d'une chaîne.

<code python>
# Attention : ce code contient des erreurs
def ajout_car(texte, car):
    texte.append(car) # il n'y a pas de append sur les str
</code>

Si ce code était autorisé, alors la fonction modifierait le ''texte'' fourni en argument, ce qui est un effet de bord.

En Python ou dans un langage fonctionnel on préfère :

<code python>
def ajout_car(texte, car):
    return texte + car
</code>

Dans ce cas, la fonction ne modifie pas ''texte'', elle crée une **copie** de ''texte'' avec le caractère en plus.

Avec ce genre de structure, on crée beaucoup de copies mais on garantit l'absence d'effet de bord. De plus, le fait que le texte ne puisse pas être modifié permet d'optimiser l'utilisation de la mémoire.

En effet, le type ''list'' est mutable et on peut ajouter ou enlever des éléments à une variable de type ''list'', mais cela occasionne des ralentissement car le contenu en mémoire doit se réorganiser à chaque ajout / suppression.

<WRAP important>**Dans un langage fonctionnel pur, tout est immuable !**</WRAP>

===== Fonction d'ordre supérieur =====

Dans un langage fonctionnel, les fonctions sont considérées comme un type ordinaire, au même titre que les entiers, les caractères... Et on peut passer une fonction comme argument à une autre fonction.

Cette façon de faire est très puissante. Voici un exemple.

<code python>
def map(tableau, fct):
    return [fct(item) for item in tableau]
</code>

Cette fonction ''map'' sert à exécuter une fonction ''fct'' sur chaque ''item'' d'un ''tableau'' et à réunir les résultats dans un nouveau tableau. Par exemple on pourrait définir :

<code python>
def square(x):
    return x**2
</code>

Puis //mapper// cette fonction sur un tableau :

<code python>
>>> tableau = [1, 7, 5, 22]
>>> map(tableau, square)
[1, 49, 25, 484]
</code>

<WRAP tip>
Notez bien que quand nous fournissons ''square'' en argument, nous ne mettons pas les ''()''. ''square'' sans les ''()'' désigne la fonction elle-même. Quand on ajoute les ''()'', c'est que l'on veut exécuter la fonction.
</WRAP>

Puisque ''map'' agit en utilisant une fonction, on peut qualifier ''map'' de fonction d'ordre supérieur.

===== Fonction anonyme =====

Supposez que je dispose d'une fonction ''f(x)'' et que je veuille calculer la fonction pour ''x = 3''. Je n'ai pas envie d'écrire

<code python>
x = 3
f(x)
</code>

Je veux écrire directement

<code python>
f(3)
</code>

De la même façon, supposons que je dispose d'un tableau et que je veuille élever tous les éléments du tableau au carré. Si je veux utiliser la méthode précédente, je dois définir une fonction ''square'' que j'utiliserai ensuite avec ''map''.

Mais je ne veux pas avoir à écrire la fonction de façon habituelle avec ''def square(x):'' -- de même qu'on ne voulait pas écrire ''3'' dans la variable ''x'' dans l'exemple précédent.

Souvent, si la fonction est à usage unique, on préfère ne pas polluer notre programme avec des noms inutiles et on préfère ne pas donner de nom à la fonction et éviter si possible de passer par une une définition formelle.

C'est possible, on parle de **fonction anonyme**. En Python, c'est une fonction **lambda**.

<code python>
lambda x: x**2
</code>

Dans ce code, ''lambda'' n'est pas un nom de fonction, c'est un mot-clé comme ''return'' ou ''def''. Il permet de définir une fonction simple, ici $x \mapsto x^2$, sans lui donner de nom.

Ainsi on pourrait écrire :

<code python>
>>> tableau = [1, 7, 5, 22]
>>> map(tableau, lambda x: x**2)
[1, 49, 25, 484]
</code>

C'est une approche efficace et élégante.

<WRAP tip>
Cette approche est par exemple beaucoup utilisée pour le tri. En effet, les langages disposent en général d'une fonction de tri, mais on veut pouvoir customiser le critère de tri. Pour cela on peut passer une fonction qui se charge de préciser le critère de tri.

<code python>
>>> tableau = [("Paul", "Dupont", "19/08/1986"),
               ("Michelle", "Lepic", "11/11/2001"),
               ("Alia", "Benala", "14/08/1988")
              ]
>>> sorted(tableau, key=lambda item:item[0])
[("Alia", "Benala", "14/08/1988"), ("Michelle", "Lepic", "11/11/2001"), ("Paul", "Dupont", "19/08/1986")]
</code>

''%%key = lambda item:item[0]%%'' signifie que la clé de tri sera, pour chaque ''item'' trié, la valeur de ''item[0]'', c'est à dire ici le prénom.
</WRAP>