Pour le bannissement de Fibonacci des cours d'introduction à la programmation fonctionnelle

[TropMDR]

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

Code :

1
2
3
4
5
6
7
8
9
type 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)

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.

Mais si on veut vraiment écrire des fonctions purement numériques, on peut trouver autre chose. Pourquoi par Syracuse par exemple?

Code :

1
2
3
4
5
6
7
8
9
let 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);;

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)

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 !!

[gorgonite]

la plupart du temps, à moins d'une récurrence forte au sens propre du terme, les structures trop linéaires sont aussi faciles à implanter en impératif qu'en fonctionnel... (et oui, même sur les listes chaïnées, on fait parfois aussi bien en impératif... mais on manipule explicitement ce que le compilo fonctionnel aurait fait)

les structures N-aire (N>=2) sont souvent bien plus parlantes en fonctionnel... même si à partir d'un certain niveau, il faut bien se dire qu'on est capable de modéliser des structures additionnelles adhoc pour accélérer le traitement et la modularité même en impératif
(mais ça sort du scope débutant )

[gasche]

Moi j'aime bien proposer fibonacci en TD de Caml pour une prépa scientifique (MPSI) : on peut écrire la version naïve, une version efficace (`fibo un2 un1 k` prend le `n-2 `et `n-1`-ième éléments et `k`, et renvoie le `n+k-2`-ième élément), une version par exponentiation rapide de matrices 2x2, et après on leur demande d'écrire la formule close en puissance du nombre d'or et ils se souviennent toute leur vie que "quand j'ai une erreur avec des flottants¹, c'est sans doute qu'il manque un point quelque part".
Un autre détail amusant est le calcul précis de la complexité de la version naïve : combien d'appels récursifs à "fibo" `fibo n` va-t-il effectuer ?

Mais oui, proposer fibonacci "comme ça" ou à des gens qui n'ont pas la formation mathématique qui suit derrière ne sert à rien. Je pense que si on veut le faire, il faut essayer de le faire dans le détail et s'assurer que les gens ont compris l'intérêt, et pas comme un exemple fourni sans explication.

¹: les nombres flottants sont généralement une nuisance, pas seulement en Caml d'ailleurs; ils sont cependant utiles car ils permettent de faire des TDs sur le fractales de Mandelbrot ou Julia, qui passent très bien avec le module Graphics et qui sont toujours un gros, gros succès auprès des élèves.

[TropMDR]

Je précise que ce n'était pas un troll "pourquoi le fonctionnel roxx grave par rapport à l'impératif" Bien sûr que ces choses sont faisables en impératif, la preuve, les gens le font Juste qu'il y a des domaines où les langages avec ADT sont *clairement* supérieures (pour d'autre, ça relève nettement plus de la conviction personnelle)

Et oui, il faut présenter fibo à un moment, parce que c'est une source de questions et d'exemples intéressants. Mais juste pas comme premier exemple

[Yo Eight]

J'essaye en ce moment d'initier à la programmation fonctionnelle en Haskell via la construction d'un parser monadique simple (aucune utilisation du Module Parsec d'Haskell, tout est fait "maison"). Bien sur, je pense bien à ne pas prononcer les mots monad, functor, adt,... même s'ils sont intensivement utilisés dans l'exercice (j'ai toujours eu des regards étranges quand je parle de monads, je sais pas pour vous )

Que pensez-vous de cet exercice ?

[gasche]

Envoyé par Yo Eight

Bien sur, je pense bien à ne pas prononcer les mots monad, functor, adt,... même s'ils sont intensivement utilisés dans l'exercice (j'ai toujours eu des regards étranges quand je parle de monads, je sais pas pour vous )

J'espère qu'on m'excusera cette pédanterie facile, mais ton utilisation abusive du franglais mérite des regards étranges : tu pourrais plutôt ne pas prononcer "monade", "foncteur" ou "type algébrique" (ce dernier terme étant d'ailleurs moins ambigu que "adt" qui désigne aussi bien les types abstraits).

Que pensez-vous de cet exercice ?

Pourquoi pas. Je trouve qu'en pratique la représentation utilisée pour ces parseurs n'est pas forcément un bon exemple de conception : on fait tout avec des fonctions, ça marche bien et c'est joli, mais en dessous ce n'est pas follement efficace et surtout c'est une boîte noire qui empêche d'inspecter après-coup la structure du parser. Dans l'absolu je préfère les conceptions où on a un type de donnée concret (donc ici il faut un GADT pour avoir des informations de typage précise; ou alors oublier l'aspect "parsing" et se contenter d'accepter ou rejeter l'entrée) et une fonction d'évaluation qui le transforme en fonction.

Après c'est peut-être un point de détail; ça n'empêche pas de vendre du rêve aux débutants en leur montrant comment les fonctions c'est rigolo. Mais j'aurais quand même une préférence pour le choix d'un exemple plus simple où on peut raisonnablement montrer ces deux approches et les comparer.

[Yo Eight]

Envoyé par gasche

J'espère qu'on m'excusera cette pédanterie facile, mais ton utilisation abusive du franglais mérite des regards étranges : tu pourrais plutôt ne pas prononcer "monade", "foncteur" ou "type algébrique" (ce dernier terme étant d'ailleurs moins ambigu que "adt" qui désigne aussi bien les types abstraits).

Il y a pas de soucis, j'ai surtout pris cette habitude pour coller au vocabulaire utilisé dans la communauté FP, qui est principalement anglophone.

Envoyé par gasche

Pourquoi pas. Je trouve qu'en pratique la représentation utilisée pour ces parseurs n'est pas forcément un bon exemple de conception : on fait tout avec des fonctions, ça marche bien et c'est joli, mais en dessous ce n'est pas follement efficace et surtout c'est une boîte noire qui empêche d'inspecter après-coup la structure du parser. Dans l'absolu je préfère les conceptions où on a un type de donnée concret (donc ici il faut un GADT pour avoir des informations de typage précise; ou alors oublier l'aspect "parsing" et se contenter d'accepter ou rejeter l'entrée) et une fonction d'évaluation qui le transforme en fonction.

Après c'est peut-être un point de détail; ça n'empêche pas de vendre du rêve aux débutants en leur montrant comment les fonctions c'est rigolo. Mais j'aurais quand même une préférence pour le choix d'un exemple plus simple où on peut raisonnablement montrer ces deux approches et les comparer.

Dans l'absolu, le but de l'initiation n'était pas d'obtenir la solution la plus performante (d'ailleurs les parsers monadiques sont surtout utilisés pour des cas simples car plus facile à mettre en place)

Mon but final est surtout de désacraliser les monades où tout autre concept au nom exotique car je suis persuadé qu'ils constituent le principal frein à l'entrée dans le monde de la FP.

Aurais-tu des exemples d'approche plus intéressantes à enseigner ?

[gasche]

Attention, il ne faut pas prendre mon post comme une critique négative de ton exemple. Je ne dis pas qu'il est plus mauvais qu'un autre, je mentionne juste des défauts; il n'y a pas d'exemple parfait de toute façon.

Pour l'introduction aux monades, j'aime bien utiliser les exemples de Wadler dans Monads for functional programming (PDF) : un petit évaluateur arithmétique simple, avec une monade Maybe, une monade State et une monade Writer (en fait c'est un peu abusif, la deuxième est aussi une monade Writer déguisée) appliquées au même exemple.

Ceci dit, je ne considère pas pour ma part qu'une introduction à la programmation fonctionnelle doive nécessairement inclure une introduction aux monades. C'est un concept relativement abstrait qui peut poser des difficultés de compréhensions. Venant d'un milieu Caml plutôt qu'Haskell je ne l'ai jamais vu enseigner comme notion de base, et je ne suis pas convaincu que ce soit désirable.

Bien sûr, tout dépend du public cible et de ce qu'il sait en arrivant.

[Yo Eight]

Je ne l'ai pas mal pris

Je cherche avant tout à améliorer mon contenu donc toute remarque constructive est bonne à prendre

Merci pour ton lien.

Je suis d'accord avec toi pour les monades mais je voulais les faire manipuler le concept sans le montrer explicitement du doigt. Je pense que cette démarche peut être intéressante car lorsque l'on voit que pleins de développeurs utilisent les instruction try / catch dans des langages impératifs sans se douter une seconde qu'il s'agit d'une monade, on se dit qu'il peut être bon de cacher des choses au début

[SpiceGuid]

Le mauvais tutoriel OCaml

Code OCaml :

1
2
3
let rec fibo n =
  if n < 2 then n
  else fibo (n - 1) + fibo (n - 2)

oh, regardez comme il est simple d'implémenter en fonctionnel la fonction de Fibonacci, alors qu'en impératif, c'est difficile


Le bon tutoriel Coq

Code Coq :

1
2
3
4
Inductive fibo : nat -> Type :=
  | Zero: fibo O
  | One:  fibo (S O)
  | Fork: forall n, fibo n -> fibo (S n) -> fibo (S (S n)).

oh, regardez comme il est simple d'implémenter l'arbre de Fibonacci avec un type dépendant, alors qu'avec un type algébrique, c'est difficile