Guide de survie au royaume du fonctionnel — Partie II

Dans le dernier article, je vous avais légèrement maltraité en vous parlant de programmation fonctionnelle. Je sais que vous avez aimé alors je vous propose d’en remettre une couche aujourd’hui.

Prenons donc l’exemple bien connu de la fonction factorielle.

Pour rappel, la factorielle de n sera calculée ainsi : f(n) -> 1 * 2 * 3 * … * n

Une première approche impérative serait de boucler sur la valeur de n et de cumuler le résultat de chaque multiplication.

Cela nous donnerait le code JavaScript suivant :

function f(n) {
  let res = 1;

  for (let i = 1; i <= n; i++) {
    res *= i;
  }

  return res;
}

La récursivité

“In order to understand recursion you must first understand recursion”.

Une première idée d’amélioration serait de faire un algorithme récursif. Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions d’instances plus petites du même problème. De manière plus concrète, la fonction va s’appeler elle-même afin de cumuler les résultats qu’elle renvoie.

Exemple :

function f(n) {
  if (n === 1) {
    return 1;
  }
  else {
    return n * f(n-1);
  }
}

Si ce n’est n’est pas votre premier rodéo avec la récursivité, vous pouvez passer à la partie suivante, sinon vous devriez avoir la même migraine que la dernière fois où vous avez essayé de débattre sur la fin d’Inception.

D’un point de vue théorique, la logique est toujours la même, car on va boucler pour cumuler des valeurs, ça ne change pas. Pour cela, on fait une simple multiplication qui va s’appliquer autant de fois que d’appels de fonctions et ces derniers s’arrêteront une fois que la valeur de n aura atteint 1.

Examinons l’ordre des actions pour f(2) :

• n = 2 donc on passe dans la branche else
• on souhaite retourner 2 * f(1), nous devons calculer f(1)
• n = 1 donc on passe dans la première branche
• on retourne 1 qui vient se cumuler à notre valeur de retour précédente
• nous avons la valeur de retour finale: 2 * 1
• !2 = 2 l’algo a réussi.

Les lambda

Les fonctions lambda sont simplement un autre nom pour les fonctions anonymes, ces dernières ne possèdent pas de nom, mais on trouve directement les instructions définissant la fonction introduite par une syntaxe particulière.

En JavaScript, elle prendra la forme suivante : 

// Une lambda qui renvoie le carré de son paramètre
(x) => x * x;

// On peut l'affecter à une variable
const myLambda = (x) => x * x;

// La passer elle-même en tant que paramètre de fonction
// (Souvenez-vous des High Order Function)
myArray.map((x) => x * x);

Ce principe nous permet d’écrire des fonctions élégantes pouvant être utilisées dans de nombreux cas. N’hésitez pas à en abuser notamment lors de l’utilisation de second order function.

Le pattern matching

Derrière ce nouveau mot mystique se cache encore une fois un concept simple. Il s’agit juste d’un mécanisme nous permettant de vérifier qu’un élément possède un motif (un format) correspondant à ce qui est attendu et d’ajuster le comportement de la fonction relativement à ce filtrage. Ex : J’ai une liste de nombres, j’aimerais que ma fonction se comporte différemment selon si l’itération courante est un nombre pair ou impair.

JavaScript ne possède pas (encore ?) cette possibilité, donc je vous propose un peu d’Ocaml pour combler ce vide.

(* Notre fonction lambda de l'exemple précédent *)
let square x = x * x ;;

(* Une liste de nombres entiers, sans surprises *)
let my_list = [1; 2; 3; 4] ;;

(* On met au carré les nombres impaires de la liste *)
let square_odd x = match (x mod 2) with
	| 0 -> x
	| _ -> square x
;;

(* On souhaite appliquer square_odd sur tous les éléments *)
let new_list = List.map square_odd my_list ;;

Le pattern matching est bien visible sur la fonction square_odd. C’est un peu comme si on avait des if dont le rôle est uniquement de vérifier “l’aspect” de la valeur.

On peut combiner cela avec la récursivité aussi, dans une fonction chargée de vérifier la présence d’un nombre dans une liste par exemple.

let my_list = [1; 2; 3] ;;

let rec exist_in_list x list = match list with
	| [] -> false
	| head::tail -> (x = head) or (exist_in_list x tail)
;;

Dans cette fonction, on va tester la première valeur de la liste avant de relancer un appel sur la suite de la liste jusqu’à ce que cette dernière soit vide. Une fois vide, le pattern matching nous permettra de renvoyer false pour terminer la boucle.

Le pipe operator

Un petit passage bonus lié à une proposition d’évolution pour JavaScript.

Lorsque l’on programme en fonctionnel, on se retrouve rapidement à imbriquer des appels de fonctions comme ceci :

const doubleSay = (str) => str + ", " + str;
const exclaim = (str) => str + '!';

console.log(exclaim(doubleSay("hello")));
// => hello, hello!

Au fur et à mesure de l’évolution du programme, la lecture de ce code peut devenir très compliquée. C’est pourquoi les langages de programmation fonctionnelle ont intégré un mécanisme permettant de chaîner ces fonctions, on l’appelle le pipe operator.

"hello"
|> doubleSay
|> exclaim
|> console.log
// => hello, hello!

Cela permet bien de voir les différentes étapes et rend le code beaucoup plus lisible. Hormis la syntaxe, le seul concept à comprendre est que chaque expression renvoie une valeur en tant que premier argument de la fonction suivante et ainsi de suite jusqu’à la fin de la chaîne de fonctions.

L’info bonus : Ocaml ne possède pas cet opérateur dans les versions antérieures à la 4.04.2… mais vu que ce langage est plein de surprises (et que l’opérateur n’est pas compliqué en soi) on peut l’implémenter facilement :

let ( |> ) x f = f x ;;

Conclusion

Les mécanismes présentés dans cet article pourraient bien vous faire cogiter un moment. N’ayez pas peur d’expérimenter et de tordre ces programmes dans tous les sens possibles.

Et si vous commencez à trouver cela trop simple pour vous, n’hésitez pas à jeter un œil à Haskel ou Ocaml, bien que parfaitement inutile dans le monde réel, ils vous en apprendront beaucoup sur la programmation fonctionnelle.

L’équipe Synbioz.
Libres d’être ensemble.