Pour le bannissement de Fibonacci des cours d'introduction à la programmation fonctionnelle
Suite à un n-ième message sur la fonction de Fibonacci, je voulais vous faire part de mon profond désaccord vis à vis de l'utilisation quasi systématique de cette fonction comme exemple de programmation fonctionnelle:
Dans quasiment tous les cours d'introduction à la programmation fonctionnelle, que ce soit dans le milieu scolaire (fac ou prépas), dans les bouquins, sur internet, etc, on retrouve systématiquement l'exemple de la fonction de Fibonacci: oh, regardez comme il est simple d'implémenter en fonctionnel la fonction de Fibonacci, alors qu'en impératif, bouh c'est difficile".
Je pense que cet exemple est l'un des pire que l'on pourrait imaginer ! Alors oui, la définition en Caml de Fibonacci colle au plus près à la définition mathématique de la suite, alors qu'une version plus impérative s'en éloigne forcément plus. Le seul problème, c'est que cette jolie implémentation a une complexité spaciale linéaire (taille max de la pile) et temporelle exponentielle, alors que la version "naturelle" (programmation dynamique) en impératif a une complexité spatiale et temporelle linéaire, qu'on passe à une complexité spatiale constante trivialement en réalisant qu'on n'a besoin uniquement des deux derniers, et pire que tout, en réfléchissant un peu, on arrive à une complexité temporelle logarithmique !
Pourquoi continue-t-on à montrer comme "hello world" de la programmation fonctionnelle un programme qui pour n'importe quelle entrée non ridicule prend l'age de l'univers à s'exécuter alors qu'il existe une solution en temps pseudo constant ?
Alors je ne suis pas contre l'étude de cette fonction: c'est bien sûr très intéressant de voir qu'une implémentation naïve peut être écrabouillée par un peu de réflexion. Mais pas comme espèce de "killer example" !
On pourrait quand même imaginer plein d'autre exemples. En un peu "difficile", parce qu'il faut introduire directement un type, on pourrait imaginer la hauteur d'un arbre
Effectivement, le code est moins triviale, mais il permet d'ouvrir tellement de question intéressante, et est tellement plus simple à écrire que dans n'importe quel langage impératif/objet ! Ce sont quand même ces structures de données qui sont les exemples les plus convaincants de la programmation fonctionnelles, avec du polymorphisme, le maping d'une fonction, les différents types de parcours, j'en passe et des meilleurs.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9type tree = | Leaf | Node of tree * int * tree let rec height tree = match tree with | Leaf -> 0 | Node (left, _ right) -> 1+ max (height left) (height right)
Mais si on veut vraiment écrire des fonctions purement numériques, on peut trouver autre chose. Pourquoi par Syracuse par exemple?
On peut ensuite la compléter avec l'impression des différents nombres, d'un décompte du nombre d'étapes, du calcules du plus haut point de l'envolée, qu'en sais-je ? Et on peut l'utiliser pour parler des optimisations "tail-rec" qui font que cette fonction n'est pas aussi horrible qu'il y parait en la regardant (contrairement à Fibonacci, on a une optimisation présent dans tous les compilateurs/interpreteur de langages fonctionnels qui manque toujours dans des environnements comme celui de java)
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9let rec syracuse n = if n = 1 then print_string "On a atteind 1 !\n" else if n mod 2 = 0 then syracuse (n / 2) else syracuse (3 * n + 1);;
Il y a sans doute plein d'autres idées possibles. Mais je pense qu'il sera difficile de trouver pire que Fibonacci.
Donc s'il vous plait, arrêtez d'utiliser Fibonacci comme exemple introductif à la programmation fonctionnelle !!
Répondre avec citation
)
Bien sûr que ces choses sont faisables en impératif, la preuve, les gens le font 
Envoyé par Yo Eight
d'implémenter en fonctionnel la fonction de Fibonacci, alors qu'en impératif, 
c'est difficile
Partager