La Prog Fonctionnelle, Partie I

[b0fh]

La Prog Fonctionnelle, Partie I

Sommaire

• Partie 1: Introduction, Lambdas, Listes, Map/Zip/Fold, compréhensions
  
• Partie 1bis: MapReduce
  
• Partie 2: Closures, Décorateurs
  
• Partie 3: Evaluation Paresseuse, Coroutines et Générateurs
  
• Partie 4: Application Partielle, Currying, Cata/Ana/Hylomorphismes
  

Introduction

La programmation fonctionnelle, c'est quoi ?

Simplement un style, ou un langage, dans lequel les fonctions sont des valeurs, qu'on peut stocker dans des variables, passer en argument, et manipuler.

On peut utiliser un style fonctionnel dans la plupart des langages, mais le langage peut rendre ceci plus ou moins facile.

On appelle "fonction d'ordre supérieur" (ou parfois foncteur, fonctionnelle, ou combinateur) une fonction qui reçoivent des fonctions en argument.

Voici, en plusieurs langages, un exemple d'un combinateur très simple, qui se contente d'appeler son argument deux fois.

Python:

Code PYTHON :

def hello():
    print("Hello World!")

def run2(f):
    f()
    f()

run2(hello)

Perl:

Code PERL :

sub hello { print "Hello World!" }
sub run2 { $_[0]->(); $_[0]->(); }

run2(\&hello);

C est partiellement fonctionnel (on verra plus tard pourquoi partiellement):

Code C :

void hello() {
    printf("Hello World");  
}

void run2(void (*f)()) {
    f(); f();
}

int main() {
    run2(hello);
    return 0;
}

En général, Orienté Objet et fonctionnel cohabitent plus ou moins bien. En Java 8: Runnable hello = () -> System.out.println("Hello World");

Code JAVA :

public void run2(Runnable r) {
    r.run(); r.run();
}

...
   run2(hello);

Oui, mais à quoi sert tout ce bouzin ?

Principalement à se faciliter la vie; au lieu de devoir coder en dur des structures de contrôle dans le langage, on peut en faire des fonctions de bibliothèque, les combiner, ou les raffiner.

Les Lambdas

Pour apprécier pleinement le style fonctionnel, le langage doit permettre de définir facilement des petites fonctions utilitaires. Une telle construction doit pouvoir être utilisable comme une expression, sans forcément lui donner un nom. Voici quelques exemples de la fonction incrément, qui retourne son argument plus 1.

En Python:

Code PYTHON :

incrément = lambda x: x+1

En Java:

Code JAVA :

Runnable increment = (x) -> x + 1;

En Perl:

Code PERL :

my $increment = sub { $_[0] + 1 };

En C: pas de bol, vous êtes baisés

Les Listes et Fonctions Associées

Il est difficile d'écrire des programmes intéressants sans utiliser au moins une structure de données exprimant une répétition, par exemple les tableaux ou les listes. Il est aussi difficile d'écrire un programme intéressant travaillant sur ces structures, sans utiliser au moins une boucle. Nous allons voir quelques combinateurs utiles pour exprimer des opérations courantes sur des listes

Map

Prenons l'archétype suivant de boucle, qui calcule une fonction arithmétique sur une liste d'éléments:

Code PYTHON :

my_modified_list = []
for x in my_list:
    my_modified_list.append(x*2 + 1)

Le cas se présente suffisament souvent pour qu'il vaille la peine d'en faire une fonction de bibliothèque:

Code PYTHON :

def map(f, input):
    output = []
    for x in input:
        output.append(f(x))
    return output

On peut alors faire:

Code PYTHON :

my_modified_list = list(map(lambda x: x*2 + 1, my_list))

Ce qui a l'intérêt d'être plus clair (quand on a l'habitude), et de réduire le risque d'erreur, puisque le code est plus simple. Surprise, surprise, cette fonction existe déja dans la lib standard, et sous ce nom !

Notez l'utilisation de list(), parce que nous n'avons pas encore abordé les coroutines, ça viendra après.

Notez que map existe également en Perl sous le même nom.

Maps Imbriquées

Quid du cas des boucles imbriquées (produit cartésien sur deux listes) ?

Code :

xs = [1,2,3]
ys = [10,100,1000]
out = []
for x in xs:
    for y in ys:
        out.append(x*y)

# out == [10,100,1000,20,200,2000,30,300,3000]

Ceci peut être approximé avec des maps:

Code :

out = list(map(lambda x: map(lambda y: f(x,y), ys), xs))
# out = [[10,100,1000],[20,200,2000],[30,300,3000]]

Il va nous falloir aplatir la liste. Pour l'instant, écrivons une fonction concat. On verra dans le paragraphe sur fold/reduce comment l'écrire plus élégamment:

Code PYTHON :

def concat(ls):
    out = []
    for l in ls:
        out += l
    return out

On aura donc

Code PYTHON :

out = concat(map(lambda x: map(lambda y: f(x,y), ys), xs))

Zip

Quid des fonctions utilisant plusieurs arguments ? Imaginons le code suivant:

Code PYTHON :

# my_xs = [...]
# my_ys = [...]

try:
    idx = 0
    diffs = []
    while True:
        x = my_xs[idx]
        y = my_ys[idx]
        diffs.append(x*x - y*y)
        idx += 1
except IndexError:
    pass

La aussi, ce pattern est suffisamment courant pour qu'il mérite d'être mis en librairie. Dans un langage typé comme Haskell, cette fonction se nomme zip. Pour python, qui supporte facilement les fonctions variadiques, il s'agit simplement d'une généralisation de map:

Code PYTHON :

diffs = list(map(lambda (x,y): x*x - y*x, my_xs, my_ys))

Filter

Un autre pattern récurrent, filtrer une liste pour n'en garder que certains éléments:

Code PYTHON :

dest = []
for x in source:
    if (x % 5 == 0):
        dest.append(x).

La aussi, on peut faire de la condition une variable passée en argument:

Code PYTHON :

def filter(f, items):
    out = []
    for x in items:
        if f(x):
            out.append(x)
    return out

Et appeler:

Code PYTHON :

dest = filter(lambda x: x % 5 == 0, source)

Note: en Perl, filter se nomme "grep".

Compréhensions de Listes

Les Map et Filters imbriqués sont suffisament courants pour que certains langagent fournissent une syntaxe dédiée pour les exprimer: les compréhensions de listes.

En python, la construction

Code PYTHON :

[ expression for var in list if condition ]

Est traduite par le compilateur en:

Code PYTHON :

list(map(lambda var: expression, filter(lambda var: condition, list)))

Par exemple, on peut écrire

Code PYTHON :

out = [ x*3 + 1 for x in src if x % 5 == 0 ]

Comme équivalent plus lisible de

Code PYTHON :

out = list(map(lambda x: x*3 + 1, filter(lambda x: x % 5 == 0), src))

Lui même une alternative au verbeux:

Code PYTHON :

out = []
for x in src:
    if x % 5 == 0:
        out.append(x*3 + 1)

Fold/reduce

Nous avons vu des fonctions transformant des listes en listes. Mais quid des fonctions générant ou consommant des listes ?

La fonction d'ordre supérieur la plus courante pour consommer des listes est fold (appelée reduce en python).

Prenons les fonctions suivantes:

Code PYTHON :

def sum(xs):
    res = 0
    for x in xs:
        res += x
    return res

def product(xs):
    res = 1
    for x in xs:
        res *= x
    return res

Il y a clairement un point commun entre ces deux fonctions. Extrayons les différences pour en faire un paramètre:

Code PYTHON :

def reduce(op,start,list):
    for x in list:
        start = op(start,x)
    return start

On peut maintenant écrire:

Code PYTHON :

def sum(xs):
    return reduce(lambda (x,y): x+y, 0, xs)

def product(xs):
    return reduce(lambda (x,y): x*y, 1, xs)

Si vous avez été attentifs, vous aurez remarqué que la définition de sum() se rapproche énormément de celle de concat(), vue plus haut. En fait, on peut écrire

Code PYTHON :

def concat(xs):
    return reduce(lambda (x,y): x+y, [], xs)

Puisque par chance c'est le même symbole (+) qui représente l'addition et la concaténation.

En python, reduce() est disponible dans le module functools. Il existe aussi une fonction sum(), dont la définition est la suivante:

Code PYTHON :

def sum(vals, zero=0):
    return reduce(lambda (x,y): x+y, zero, vals)

Ce qui fait qu'on peut écrire concat() en utilisant le sum() de la lib standard:

Code :

>>> sum([[1,2],[3,4],[5,6]],[])
[1, 2, 3, 4, 5, 6]

Vous avez certainement entendu parler de MapReduce, le framework théorique derrière les DB NoSQL récentes (Hadoop, MongoDB, CouchDB...). De par leur nature, les fonctions écrites en combinant une opération Map et une opération Reduce peuvent très facilement se paralleliser sur plusieurs machines. On y reviendra dans un article ultérieur.

[lanodan]

Faire du fonctionnel dans des languages pas très orienté fonctionnel est pas mal mais le mieux reste des languages purement fonctionnels (comme erlang ou haskell) ce qui permet quelques trucs sympa (erlang et sa gestion de crash/erreurs, haskell pour la feinéantise et son coté très math)