aboutsummaryrefslogtreecommitdiff
path: root/content/Informatique/2012-11-09-fonctionnel.rst
blob: 06d75d0b587957311226db380f908fd4f79bf5c0 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
Programmation fonctionnelle
###########################

:date: 2012-11-09
:tags: Programmation

Dans cet article, je vais essayer de présenter différents cas de programmation
fonctionnelle en essayant de partir d'un cas pratique pour présenter les
difficultés et solutions disponibles.

Je vais présenter ici des exemples dans le langage python, par ce qu'il s'agit
d'un langage simple, pouvant être utilisé de manière fonctionnelle (dans une
certaine limite). Je me contente d'un python `basique` et ne vais pas chercher
entrer dans des syntaxes spécifiques, le but étant ici de servir de support, et
non pas de présenter le langage.

Un besoin
=========

Imaginons la situation suivante : une application reçoit des données d'un
client et doit les traiter. Ces données arrivent dans des fichiers textes,
chaque ligne du fichier correspond à une donnée à traiter.

Un programme
============

Commençons le programme, pour lire le fichier commençons par le localiser :

.. code-block:: python

    def get_file(nom):
        chemin = os.path.join("repertoire", nom)
        return open(chemin)

Cette fonction est simple : elle prend en argument un nom de fichier, et
retourne le fichier correspondant. On peut également dire qu'elle effectue la
transformation suivante :

.. code-block:: ocaml

    get_file: String -> File

Cette notation indique que le type de la fonction est le suivant : elle prend
un string en entrée, et retourne un file en sortie. Nous l'utiliserons
régulièrement dans cet article.

Dans notre cas, nous n'avons pas un fichier a traiter, mais une série de
fichiers. Nous allons donc devoir appeler la fonction sur tous nos nom de
fichiers. La première solution est la solution itérative, à travers une boucle
:

.. code-block:: python

    def transforme(noms):
        fichiers = []
        for nom in noms
            fichiers.append(get_file(nom))
        return fichiers

À la fin de l'exécution de la boucle, la liste `fichiers` contient la liste des
fichiers construits à partir de la liste `noms`.

C'est une opération très fréquente et bien qu'elle soit très courte. Essayons
de réfléchir un peu à ce que nous venons de faire en terme de type : notre but
est de transformer une liste de String en liste de File de la manière suivante
:

.. code-block:: ocaml

    transforme: List[String] -> List[File]

Si l'on généralise, on peut essayer de créer une fonction qui aurait le schéma
suivant :

.. code-block:: ocaml

    transforme: List[A] -> List[B]

Cette fonction a par contre besoin d'une transformation à appliquer pour
transformer A en B, dans notre cas, cette transformation a déjà été créée plus
haut !

Notre schéma devient donc le suivant :

.. code-block:: ocaml

    transforme: (A -> B) -> List[A] -> List[B]

Récrivons donc notre fonction transforme de cette manière:

.. code-block:: python

    def transforme(func, source):
        results = []
        for nom in source
            results.append(func(nom))
        return results

    fichiers = transforme(get_file, noms)

Et voilà ! Nous avons maintenant notre fonction générique, destinée à changer
le contenu de notre liste. Qu'est ce que cela apporte par rapport à la version
impérative que nous avons écrit tout à l'heure ? En fait pas grand chose. Sauf
que la fonction `transforme` est présente nativement dans python. Elle
s'appelle en fait `map`, et effectue le même travail.

Nous aurions donc tout aussi bien pu écrire :

.. code-block:: python

    fichiers = map(get_file, noms)

Une réflexion
=============

Pourquoi avoir écrit tout ça ? Par ce que semblant de rien, nous avons changé
notre manière de concevoir le programme : au lieu d'écrire une suite
d'instructions qui s'exécutent séquentiellement, nous venons d'appliquer des
transformations dans un contexte : la liste des noms de fichiers est notre
contexte de base, sur lequel nous appliquons des transformations pour créer un
autre contexte.

Ces transformations ne modifient pas notre contexte initial, et par la suite
les transformations que nous continueront d'appliquer ne modifieront rien non
plus de notre environnement. Dans cet esprit, l'ensemble du programme peut être
perçu comme un grande transformation qui s'applique sur un point d'entrée
initial.

Une théorie
===========

La fonction `map` que nous venons de présenter ici, s'inscrit en fait dans un
cadre de fonctions plus vaste : les foncteurs_. Il s'agit d'une notion
mathématique que l'on retrouve appliquée en informatique.

.. _foncteurs: http://fr.wikipedia.org/wiki/Foncteur

Comme vu précédemment, un objet foncteur F est un objet ayant la signature
suivante :

.. code-block:: ocaml

    map: (A -> B) -> F[A] -> F[B]

Le foncteur a deux contraintes, qui sont plutôt intuitives:

identité
--------

Soit la fonction `id` défini comme suit:

.. code-block:: python

    def id(x):
        return x

alors on a l'égalité suivante :

.. code-block:: python

    map(id, fichiers) == fichiers

Autrement dit, le foncteur ne doit pas modifier la structure de la donnée. On
peut essayer de repenser la fonction `transforme` écrite plus haut pour briser
cette règle, je laisse au lecteur le soin de réfléchir à cette question.

composition
-----------

La deuxième contrainte est celle de la composition : 
    
.. code-block:: python

    map(f(g), source) = map(f, map(g, source))

C'est à dire qu'il est possible de composer les fonctions les entre elles :
c'est encore heureux, car cela permet de chaîner les traitements entre eux…

Une conclusion
==============

Notre contexte est ici une liste, mais nous allons voir par la suite qu'il en
existe beaucoup d'autres, ce qui va nous faciliter la vie… Cela va venir dans
les articles qui suivent.

Une fois les deux contraintes validées, nous allons pouvoir construire de
nouveaux types basés sur ce foncteur. Et derrière la solution informatique mise
en place, je vais essayer de présenter les concepts mathématiques qui sont
derrière.