Chapitre 13. Techniques de programmation fonctionnelle

Ce chapitre couvre

Citoyens de première classe, fonctions d’ordre supérieur, currying et application partielle
Structures de données persistantes
Évaluation paresseuse et listes paresseuses généralisant les flux Java
Pattern matching et comment le simuler en Java
Transparence référentielle et mise en cache

Au chapitre 13, vous avez vu comment penser fonctionnellement; penser en termes de méthodes sans effets secondaires peut vous aider à écrire du code plus maintenable. Dans ce chapitre, nous présentons des techniques de programmation fonctionnelle plus avancées. Vous pouvez voir ce chapitre comme un mélange de techniques pratiques à appliquer dans votre code ainsi que des informations académiques qui feront de vous un programmeur plus expérimenté. Nous discutons des fonctions d’ordre supérieur, de l’exécution, des structures de données persistantes, des listes paresseuses, de la correspondance de modèles (pattern matching), de la mise en cache avec la transparence référentielle et des combinateurs.

14.1. Fonctions partout

Dans le chapitre 12, nous avons utilisé l’expression «programmation de style fonctionnel» pour signifier que le comportement des fonctions et des méthodes devrait être semblable à celui des fonctions de style mathématique – aucun effet secondaire. Les programmeurs en langage fonctionnel utilisent souvent l’expression avec plus de généralité pour signifier que les fonctions peuvent être utilisées comme d’autres valeurs: passées en arguments, retournées comme résultats, et stockées dans des structures de données. De telles fonctions qui peuvent être utilisées comme d’autres valeurs sont appelées des fonctions de première classe. C’est exactement ce que Java 8 ajoute sur les versions précédentes de Java: vous pouvez utiliser n’importe quelle méthode comme valeur de fonction, en utilisant l’opérateur :: pour créer une référence de méthode, et les expressions lambda (par exemple, (int x) -> x + 1 ) pour exprimer directement les valeurs de fonction. En Java 8, il est parfaitement possible de stocker la méthode Integer.parseInt dans une variable en utilisant une référence de méthode comme suit:

14.1.1. Fonctions d’ordre supérieur

Jusqu’à présent, nous avons principalement utilisé le fait que les valeurs de fonction soient de première classe uniquement pour les passer aux opérations de traitement de flux Java 8 (comme dans les chapitres 4-7) et pour atteindre l’effet très similaire du paramétrage du comportement. :: isGreen-Apple comme valeur de fonction pour filterApples dans les chapitres 1 et 2. Mais ce n’était qu’un début. Un autre exemple intéressant est l’utilisation de la méthode statique Comparator.comparing, qui prend une fonction en paramètre et retourne une autre fonction (un comparateur), comme illustré dans le code suivant et la figure 14.1:

Figure 14.1. La comparaison prend une fonction en paramètre et renvoie une autre fonction.

Nous avons fait quelque chose de similaire lorsque nous composions des fonctions dans le chapitre 3 pour créer un pipeline d’opérations:

Les fonctions (comme Comparator.comparing) qui peuvent faire au moins l’une des opérations suivantes sont appelées fonctions d’ordre supérieur dans la communauté de programmation fonctionnelle:

Prendre une ou plusieurs fonctions en paramètre
Renvoie une fonction comme résultat

Ceci est directement lié aux fonctions de Java 8 car elles peuvent non seulement être passées en arguments mais aussi être renvoyées en tant que résultats, assignées à des variables locales, ou même insérées dans des structures. Par exemple, un programme de calcul de poche peut avoir une Map <String, Function <Double, Double >>, qui mappe la String « sin » à la fonction Function<Double, Double> pour contenir la référence de méthode Math :: sin. Nous avons fait quelque chose de similaire lorsque nous avons introduit le design pattern Factory dans le chapitre 8.

Pour les lecteurs qui ont aimé l’exemple du calcul à la fin du chapitre 3, vous pouvez considérer le type de différenciation comme

car il prend une fonction comme argument (par exemple, (Double x) -> x * x) et renvoie une fonction comme résultat (dans cet exemple (Double x) -> 2 * x). Nous avons écrit ceci comme un type de fonction (la fonction la plus à gauche) pour affirmer explicitement le fait que vous pourriez passer cette fonction de différenciation à une autre fonction. Mais il est bon de rappeler que le type de différenciation et la signature

disent la même chose.

Les effets secondaires et les fonctions d’ordre supérieur

Nous avons noté au chapitre 7 que les fonctions transférées aux opérations de flux devraient généralement être sans effets secondaires, et nous avons noté les problèmes qui en découlent (tels que des résultats incorrects). Ce principe s’applique également en général lorsque vous utilisez des fonctions d’ordre supérieur. Lors de l’écriture d’une fonction ou d’une méthode d’ordre supérieur, vous ne savez pas à l’avance quels arguments lui sera transmis – et si les arguments ont eux même des effets secondaires, alors qu’est-ce que ceux-ci pourraient faire! Il devient beaucoup trop compliqué de raisonner sur ce que fait votre code s’il utilise des fonctions passées en arguments qui font des changements imprévisibles à l’état de votre programme; ils pourraient même interférer avec votre code d’une manière difficile à déboguer. C’est donc un bon principe de conception de documenter les effets secondaires que vous êtes prêt à accepter à partir des fonctions passées en paramètre, et «none» est le meilleur de tous!

Nous passons maintenant au currying: une technique qui peut vous aider à modulariser les fonctions et à réutiliser le code.

14.1.2. Currying

Avant de donner la définition théorique du currying, regardons un exemple. Les applications doivent presque toujours être internationalisées, et la conversion d’un ensemble d’unités à un autre est un problème qui revient à plusieurs reprises.

La conversion d’unités implique toujours un facteur de conversion et, de temps en temps, un facteur d’ajustement de base. Par exemple, la formule pour convertir Celsius en Fahrenheit est CtoF(x)= x * 9/5 + 32.

Le pattern de base de toutes les conversions d’unités est le suivant:

1. Multipliez par le facteur de conversion.

2. Ajustez la ligne de base si nécessaire.

Vous pouvez exprimer ce pattern avec la méthode générale suivante:

Ici, x est la quantité que vous voulez convertir, f est le facteur de conversion, et b est la référence. Mais cette méthode est un peu trop générale. Vous trouverez généralement que vous avez besoin d’un grand nombre de conversions entre la même paire d’unités, de kilomètres à miles, par exemple. Vous pouvez évidemment appeler la méthode du convertisseur avec trois arguments à chaque fois, mais fournir le facteur et la ligne de base à chaque fois serait fastidieux et vous pourriez les confondre accidentellement.

Vous pouvez écrire une méthode complètement nouvelle pour chaque application, mais cela manquerait la réutilisation de la logique sous-jacente.

Voici un moyen facile de tirer parti de la logique existante tout en personnalisant le convertisseur pour des applications particulières. Vous pouvez définir une «factory» qui fabrique des fonctions de conversion à un argument pour illustrer l’idée de la correction:

Maintenant, tout ce que vous avez à faire est de passer le facteur de conversion et la ligne de base (f et b), et il retournera obligeamment une fonction (de x) pour faire exactement ce que vous avez demandé. Par exemple, vous pouvez maintenant utiliser la factory pour produire le convertisseur dont vous avez besoin:

Parce que DoubleUnaryOperator définit une méthode applyAsDouble, vous pouvez utiliser vos convertisseurs comme suit:

En conséquence, votre code est plus flexible et il réutilise la logique de conversion existante! Réfléchissons à ce que vous faites ici. Au lieu de passer tous les arguments x, f et b à la fois à la méthode du convertisseur, vous ne demandez que les arguments f et b et renvoyez une autre fonction qui, lorsqu’elle reçoit un argument, renvoie x * f + b. Cela vous permet de réutiliser la logique de conversion et de créer différentes fonctions avec différents facteurs de conversion.

Définition théorique du Currying

Le Currying est une technique où une fonction f de deux arguments (x et y, disons) est vue à la place comme une fonction g d’un argument qui retourne une fonction aussi d’un argument. La valeur renvoyée par la dernière fonction est la même que la valeur de la fonction d’origine, c’est-à-dire f (x, y) = (g (x)) (y).

Bien sûr, ceci généralise: vous pouvez utiliser une fonction à six arguments pour prendre d’abord les arguments numérotés 2, 4 et 6 retournant une fonction prenant l’argument 5, qui retourne une fonction en prenant les arguments restants, 1 et 3.

Lorsque certains, mais moins que l’ensemble complet des arguments ont été passés, nous disons souvent que la fonction est partiellement appliquée.

Nous passons maintenant à un autre aspect de la programmation fonctionnelle. Pouvez-vous vraiment programmer en utilisant des structures de données s’il vous est interdit de les modifier?

14.2. Structures de données persistantes

Dans cette section, nous explorons l’utilisation des structures de données utilisées dans les programmes fonctionnels. Ceux-ci se relèvent sous différents noms, tels que structures de données fonctionnelles et structures de données immuables, mais les structures de données persistantes sont peut-être les plus courantes (malheureusement, cette terminologie se heurte à la notion de persistance dans les bases de données).

La première chose à noter est qu’une méthode de style fonctionnel n’est pas autorisée à mettre à jour une structure de données globale ou une structure passée en paramètre. Pourquoi? Parce que l’appeler deux fois est susceptible de produire des réponses différentes – violant la transparence référentielle et la capacité de comprendre la méthode comme un simple mappage des arguments aux résultats.

14.2.1. Mises à jour destructrices ou dans un style fonctionnel

Supposons que vous représentez les trajets en train de A à B comme une classe TrainJourney mutable (une simple implémentation d’une liste à lien unique), avec un champ int modélisant certains détails du voyage tels que le prix de l’étape actuelle du voyage. Les voyages vous demandant de changer de train auront plusieurs objets TrainJourney liés utilisant le champ onward; un train direct ou une étape finale d’un voyage aura le champ onward qui sera nul;

Supposons maintenant que vous ayez des objets TrainJourney distincts représentant un trajet de X à Y et de Y à Z. Vous pouvez créer un trajet qui relie les deux objets (c’est-à-dire X à Y à Z).

Une méthode impérative traditionnelle simple pour lier (link) ces voyages en train est la suivante:

Cela fonctionne en trouvant la dernière étape dans le TrainJourney pour a et en remplaçant le null marquant la fin de la liste par la liste b (vous avez besoin d’un cas spécial si a n’a aucun élément).

Voici le problème: supposons qu’une variable firstJourney contienne l’itinéraire de X à Y et une variable secondJourney contient l’itinéraire de Y à Z. Si vous appelez link (firstJourney, secondJourney), ce code met à jour de manière destructive firstJourney pour contenir également secondJourney, donc en plus à l’utilisateur unique qui demande un voyage de X à Z en voyant le voyage combiné comme prévu, le trajet de X à Y a été mis à jour de manière destructive. En effet, la variable firstJourney n’est plus une route de X à Y mais une de X à Z! Cela va casser le code qui dépend de firstJourney n’étant pas modifié! Supposons que firstJourney ait représenté le train Londres-Bruxelles tôt le matin. Tous les usagers suivants qui tenteront de se rendre à Bruxelles seront surpris de voir qu’il leur faut une étape ultérieure, peut-être vers Cologne. Nous avons tous affronté de tels bugs concernant la visibilité d’un changement dans une structure de données.

L’approche fonctionnelle de ce problème consiste à interdire de telles méthodes d’effets secondaires. Si vous avez besoin d’une structure de données pour représenter le résultat d’un calcul, vous devez en créer une nouvelle et ne pas muter une structure de données existante comme précédemment. C’est souvent la meilleure pratique dans la programmation orientée objet standard. Une objection commune à l’approche fonctionnelle est qu’elle provoque une copie excessive et que le programmeur dit: «Je me souviendrai juste» ou «Je documenterai simplement» qu’il a des effets secondaires. Mais cela laisse des pièges pour les programmeurs de maintenance qui devront ensuite gérer votre code. Ainsi, la solution de style fonctionnel est la suivante:

Ce code est clairement un style fonctionnel (il n’utilise aucune mutation, même localement) et ne modifie aucune structure de données existante. Notez, cependant, que le code ne crée pas un TrainJourney entièrement nouveau – si a est une séquence de n éléments et b a une séquence de m éléments, alors il renvoie une séquence de n + m éléments dont les n premiers éléments sont de nouveaux nœuds et les derniers éléments m partagent avec le TrainJourney b. Notez que les utilisateurs sont également tenus de ne pas muter le résultat de append, car ils peuvent ainsi corrompre les trains transmis en tant que séquence b. Les figures 14.2 et 14.3 illustrent la différence entre l’appe

nd destructeur et l’append fonctionnel.

Figure 14.2. La structure de données est mise à jour de manière destructive.

Figure 14.3. Style fonctionnel, aucune modification de la structure de données

14.2.2. Un autre exemple avec les arbres

Avant de quitter ce sujet, considérons une autre structure de données, celle d’un arbre de recherche binaire qui pourrait être utilisé pour implémenter une interface similaire à une HashMap. L’idée est qu’un arbre qui contient une String représentant une clé et un entier représentant une valeur, peut-être des noms et des âges:

Vous voulez utiliser l’arbre de recherche binaire pour rechercher des valeurs de String pour produire un int. Considérons maintenant comment vous pourriez mettre à jour la valeur associée à une clé donnée (pour plus de simplicité, vous commencerez en supposant que la clé est déjà présente dans l’arborescence):

L’ajout d’un nouveau noeud est plus délicat. le plus simple est de faire en sorte que la mise à jour de la méthode retourne l’arbre qui vient d’être traversé (Il ne sera pas modifié sauf si vous devez ajouter un nouveau noeud). Ce code est maintenant légèrement plus maladroit (parce que l’utilisateur doit se souvenir que update essaie de mettre à jour l’arbre, en renvoyant le même arbre que passé plutôt. Mais si l’arbre d’origine était vide, un nouveau noeud est retourné):

Notez que les deux versions de mise à jour mutent à nouveau l’arborescence existante, ce qui signifie que tous les utilisateurs de la Map stockés dans l’arborescence verront la mutation.

14.2.3. Utiliser une approche fonctionnelle

Alors, comment pourriez-vous faire cela fonctionnellement? Vous devez créer un nouveau noeud pour la nouvelle paire clé-valeur, mais vous devez également créer de nouveaux noeuds sur le chemin qui va de la racine de l’arbre au nouveau noeud (en général, ce n’est pas très cher, si l’arbre est de profondeur d et raisonnablement bien équilibré, alors il peut avoir des entrées 2d, donc vous en re-créez seulement une petite fraction):

Nous avons écrit ceci comme une seule expression conditionnelle au lieu d’utiliser if-then-else pour souligner l’idée que le corps n’est qu’une seule expression sans effets secondaires, mais vous pouvez préférer écrire une chaîne équivalente if-then-else, chacun contenant un retour.

Alors, quelle est la différence entre update et fupdate? Nous avons noté précédemment que la mise à jour de la méthode suppose que chaque utilisateur souhaite partager la même structure de données et voir les mises à jour causées par n’importe quelle partie du programme. Il est donc essentiel (mais souvent négligé) dans le code non fonctionnel que chaque fois que vous ajoutez une forme de valeur structurée à un arbre, vous le copiez, car, qui sait, quelqu’un peut supposer qu’il peut le mettre à jour. En revanche, fupdate est purement fonctionnel. Cela crée un nouvel arbre mais partage le plus possible avec son argument. La figure 14.4 illustre cette idée. Vous avez un arbre composé de noeuds stockant un nom et l’age d’une personne. Appeler fupdate ne modifie pas l’arborescence existante mais crée de nouveaux nœuds «vivant à côté de» l’arborescence sans nuire à la structure de données existante.

Figure 14.4. Aucune structure de données existante n’a été endommagée lors de la réalisation de cette mise à jour de l’arborescence.

De telles structures de données fonctionnelles sont souvent appelées persistantes – leurs valeurs persistent et sont isolées des changements qui se produisent ailleurs – en tant que programmeur, vous êtes sûr que fupdate ne mutera pas les structures de données passées en arguments. Il y a une seule condition: de l’autre côté du traité, vous exigez que tous les utilisateurs de structures de données persistantes suivent l’exigence de ne pas muter. Si ce n’est pas le cas, un programmeur qui ne tient pas compte de ceci pourrait muter le résultat de fupdate (par exemple, changer les 20 d’Emily). Cela serait alors visible comme un changement inattendu et retardé (presque certainement indésirable) de la structure de données passée en argument à fupdate!

Vu en ces termes, fupdate peut souvent être plus efficace: la règle « no mutation of existing structure » permet que des structures qui ne diffèrent que légèrement les unes des autres (par exemple, l’Arbre vu par l’utilisateur A et la version modifiée vue par l’utilisateur B) puissent partager le stockage pour les parties communes de leur structure. Vous pouvez vous aider du compilateur pour appliquer cette règle « pas de mutation de la structure existante » en déclarant les champs key, val, left et right de la classe Tree comme étant final; mais rappelez-vous que le mot clé final ne protège qu’un champ et non l’objet pointé, ce qui peut nécessiter que ses propres champs soient eux même définis comme final pour le protéger, et ainsi de suite.

Ah, mais vous pourriez dire: «Je veux que les mises à jour de l’arbre soient vues par certains utilisateurs (mais pas par d’autres)». Il y a deux choix: l’un est la solution Java classique (attention à la mise à jour) pour vérifier si vous avez besoin de le copier en premier). L’autre est la solution de style fonctionnel: vous créez logiquement une nouvelle structure de données chaque fois que vous effectuez une mise à jour (donc rien n’est jamais muté) et juste s’assurer de passer la bonne version de la structure de données aux utilisateurs. Cette idée pourrait être appliquée via une API. Si certains clients de la structure de données doivent avoir des mises à jour visibles, ils doivent passer par une API qui renvoie la dernière version. Les clients qui ne veulent pas de mises à jour visibles (comme pour une analyse statistique de longue durée) utilisent simplement la copie qu’ils ont récupérée, sachant qu’elle ne peut pas être mutée sous en étant sous leur responsabilité.

On pourrait remarquer que cette technique est comme « mettre à jour » un fichier sur un CD-R, ce qui permet d’écrire un fichier une seule fois en le gravant au laser; plusieurs versions du fichier sont stockées sur le CD (le logiciel de création de CD Smart peut même partager des parties communes de plusieurs versions), et vous passez le bon bloc d’adresse du début du fichier (ou un nom de fichier codant la version dans son nom) afin de sélectionner la version que vous voulez utiliser. En Java, les choses sont plutôt meilleures que sur un CD, dans la mesure où les anciennes versions de la structure de données qui ne peuvent plus être utilisées seront récupérées.

14.3. Évaluation paresseuse avec des flux

Vous avez vu dans les chapitres précédents que les flux sont un excellent moyen de traiter une collection de données. Mais pour diverses raisons, y compris une implémentation efficace, les concepteurs de Java 8 ont ajouté des flux à Java d’une manière plutôt spécifique. En particulier, une limitation est que vous ne pouvez pas définir un flux de manière récursive, car un flux ne peut être consommé qu’une seule fois. Nous montrons dans la section à venir comment cela peut parfois être problématique.

Mais cette solution est quelque peu embarrassante: vous devez parcourir chaque nombre à chaque fois pour voir si il peut être divisée par un nombre en entrée. (En fait, vous n’avez besoin que de tester avec des nombres qui ont déjà été classés comme premiers.)

Idéalement, le flux devrait filtrer les nombres divisibles par le nombre qu’il produit en déplacement! Cela semble fou, alors nous allons essayer d’esquisser comment cela pourrait fonctionner:

1. Vous avez besoin d’un flux de nombres à partir duquel vous allez sélectionner les nombres premiers.

2. A partir de ce flux, vous prenez le premier nombre (la tête du flux), qui sera un nombre premier (à l’étape initiale, ce sera 2).

3. Vous filtrez ensuite tous les nombres divisibles par ce nombre à partir de la queue du flux.

4. La queue qui en résulte est le nouveau flux de nombres que vous pouvez utiliser pour trouver les nombres premiers. Essentiellement, vous revenez à l’étape 1, donc cet algorithme est récursif.

Notez que cet algorithme est « médiocre » pour plusieurs raisons. Essayons d’écrire cet algorithme en utilisant l’API Streams.

Vous pouvez obtenir un flux infini de nombres à partir de 2 en utilisant la méthode IntStream.iterate, que nous avons décrite au chapitre 5 comme suit:

Étape 1: Obtenez un flux de chiffres

Étape 2: Prenez la tête

Un IntStream est livré avec la méthode findFirst, qui peut être utilisée pour retourner le premier élément:

Étape 3: Filtrer la queue

Définir une méthode pour obtenir la queue d’un flux:

Étape 4: Créer récursivement un flux de nombres premiers

Voici la partie délicate. Vous pourriez être tenté d’essayer de renvoyer le flux filtré résultant afin que vous puissiez prendre sa tête et filtrer plus de nombres, comme ceci:

Mauvaises nouvelles

Malheureusement, si vous exécutez le code à l’étape 4, vous obtiendrez l’erreur suivante: « java.lang.IllegalStateException: le flux a déjà été exploité ou fermé. » En effet, vous utilisez deux opérations terminales pour diviser le flux en sa tête et sa queue: findFirst et skip. Souvenez-vous du chapitre 4 qu’une fois que vous appelez une opération terminale sur un flux, ilest consommée pour toujours!

Évaluation paresseuse

Il y a un problème supplémentaire, plus important: la méthode statique IntStream.concat attend deux instances d’un flux. Mais son second argument est un appel récursif direct aux nombres premiers, aboutissant à une récursion infinie! Pour de nombreuses applications Java, les restrictions sur les flux Java 8 telles que «aucune définition récursive» ne posent aucun problème et donnent à vos requêtes de type base de données une expressivité et une capacité de parallélisation. Néanmoins, les caractéristiques plus générales et les modèles de flux des langages fonctionnels tels que Scala et Haskell peuvent être un ajout utile à votre boîte à outils de programmation. Ce dont vous avez besoin est un moyen d’évaluer paresseusement l’appel à la méthode primes dans le second argument de concat. (Dans un vocabulaire de langage de programmation plus technique, nous parlons d’évaluation paresseuse, d’évaluation sans contrainte ou même d’appel par nom.) C’est seulement lorsque vous devez traiter les nombres premiers (par exemple avec la méthode limit) que le flux doit être évalué. Scala (que nous explorons dans le chapitre suivant) fournit un support pour cette idée. Dans Scala, vous pouvez écrire l’algorithme précédent comme suit, où l’opérateur # :: fait une concaténation paresseuse (les arguments sont évalués uniquement lorsque vous devez consommer le flux):

Ne vous inquiétez pas pour ce code. Son seul but est de vous montrer une zone de différence entre Java et d’autres langages de programmation fonctionnels. Il est bon de réfléchir juste un instant sur la façon dont les arguments sont évalués. En Java lorsque vous appelez une méthode, tous ses arguments sont entièrement évalués immédiatement. Mais dans Scala en utilisant # ::, la concaténation est retourné immédiatement et les éléments sont évalués seulement si nécessaire. Nous passons maintenant à l’implémentation de cette idée de listes paresseuses directement en Java.

14.3.2. Votre propre liste paresseuse

Les flux Java 8 sont souvent décrits comme paresseux. Ils sont paresseux dans un aspect particulier: un flux se comporte comme une boîte noire qui peut générer des valeurs sur demande. Lorsque vous appliquez une séquence d’opérations à un flux, celles-ci sont simplement sauvegardées. Ce n’est que lorsque vous appliquez une opération terminale à un flux que quelque chose est réellement calculé.Vous remarquez l’avantage quand vous appliquez plusieurs opérations (peut-être un filtre et une map suivies d’une opération terminale,reduce par exemple) à un flux; alors le flux doit être traversé seulement une fois au lieu de plusieurs fois pour chaque méthodes intermédiaire.

Dans cette section, nous considérons la notion de listes paresseuses, qui sont une forme d’un flux plus général (les listes paresseuses forment un concept similaire à un flux). Les listes paresseuses fournissent également une excellente façon de penser aux fonctions d’ordre supérieur; vous placez une valeur de fonction dans une structure de données, la plupart du temps elle peut rester inutilisée, mais lorsqu’elle est appelée (c’est-à-dire à la demande), elle peut créer plus de structure de données. La figure 14.5 illustre cette idée.

Figure 14.5. Les éléments d’une LinkedList existent (sont étalés) en mémoire. Mais les éléments d’une liste LazyList sont créés à la demande par une fonction, vous pouvez les voir comme étalés dans le temps.

Assez parlé, voyons comment cela fonctionne. Ce que vous voulez accomplir est de générer une liste infinie de nombres premiers en utilisant l’algorithme que nous avons décrit précédemment.

Une liste chaînée basic

Rappelez-vous que vous pouvez définir une classe de style de liste liée simple appelée MyLinkedList en Java en l’écrivant comme suit (ici, nous considérons seulement une interface MyList minimale):

Vous pouvez maintenant construire un exemple de valeur MyLinkedList comme suit:

Une liste paresseuse basic

Un moyen facile d’adapter cette classe au concept d’une liste paresseuse est de faire en sorte que la queue ne soit pas présente en une seule fois mais d’avoir un Supplier<T> que vous avez vu au chapitre 3 (vous pouvez également le voir comme une factory avec un descripteur de fonction void -> T), qui produit le noeud suivant de la liste. Cela conduit à ce qui suit:

L’appel de la méthode get du supplier provoque la création d’un nœud de la Lazy liste (car une factory créerait un nouvel objet).

Vous pouvez maintenant créer la liste paresseuse infinie de nombres commençant à n comme suit, en passant un Supplier comme argument de queue du constructeur LazyList, qui crée l’élément suivant dans la série de nombres:

Si vous essayez le code suivant par vous-même, vous verrez que les appels suivants afficheront « 2 3 4 ». En effet, les numéros sont générés à la demande. Vous pouvez le vérifier en insérant System.out.println de manière appropriée ou en notant que from(2) s’exécuterait à jamais s’il essayait de calculer avec impatience tous les nombres à partir de 2!

Retour à la génération des nombres premiers

Voyez si vous pouvez utiliser ce que vous avez fait jusqu’à présent pour générer une liste paresseuse de nombres premiers (ce que vous n’avez pas pu faire avec l’API Streams). Si vous deviez traduire le code qui utilisait l’API Streams plus tôt en utilisant notre nouvelle version de LazyList, cela ressemblerait à ceci:

Implémenter un filtre paresseux

Malheureusement, une LazyList (plus précisément l’interface List) ne définit pas de méthode de filtrage, donc le code précédent ne sera pas compilé! Réglons cela et en déclarons un:

Votre code compile maintenant et est prêt à l’emploi! Vous pouvez calculer les trois premiers nombres premiers en enchaînant les appels à la queue et à la tête:

Cela imprimera « 2 3 5 », qui sont les trois premiers nombres premiers. Vous pouvez maintenant vous amuser; par exemple, vous pouvez imprimer tous les nombres premiers (le programme s’exécutera infiniment en écrivant une méthode printAll, qui imprime de façon itérative la tête et la queue d’une liste:

Ceci étant un chapitre de programmation fonctionnelle, nous devrions vous expliquer que vous pouvez le faire de façon récursive:

Mais ce programme ne fonctionnerait pas à l’infini; Malheureusement, il échouera éventuellement en raison du débordement de la pile, car Java ne prend pas en charge l’élimination de l’appel tail, comme indiqué au chapitre 13.
Ouf!

Vous avez donc construit beaucoup de technologie: des listes paresseuses et des fonctions qui les utilisent simplement pour définir une structure de données contenant tous les nombres premiers. Pourquoi? Quelle est l’utilisation pratique? Eh bien, vous avez vu comment placer des fonctions dans des structures de données (parce que Java 8 vous le permet), et ces fonctions peuvent être utilisées pour créer des parties de la structure de données à la demande plutôt que lorsque la structure est créée. Cela peut être utile si vous écrivez un programme de jeu, peut-être pour les échecs; vous pouvez avoir une structure de données qui représente théoriquement tout l’arbre des mouvements possibles (beaucoup trop gros pour calculer avec empressement) mais qui peut être créé à la demande. Ce serait un arbre paresseux par opposition à une liste paresseuse. Nous nous sommes concentrés sur les listes paresseuses car elles fournissent un lien vers une autre fonctionnalité de Java 8, les flux, et nous pourrions ensuite discuter des avantages et des inconvénients des flux par rapport aux listes paresseuses.

Reste la question de la performance. Il est facile de supposer que faire les choses paresseusement sera mieux que de faire les choses avec empressement – il est préférable de calculer uniquement les valeurs et les structures de données requises par un programme à la demande plutôt que de créer toutes ces valeurs. . Malheureusement, le monde réel n’est pas si simple. Les frais généraux engendrés par le fait de faire les choses paresseusement (par exemple, les fournisseurs supplémentaires entre chaque élément de votre liste LazyList) l’emportent sur l’avantage théorique, sauf si vous explorez, disons, moins de 10% de la structure de données. Enfin, il existe une manière subtile dans laquelle vos valeurs LazyList ne sont pas vraiment paresseuses. Si vous parcourez une valeur LazyList, par exemple from(2), peut-être jusqu’au 10e élément, elle crée également tous les nœuds deux fois, créant ainsi 20 nœuds au lieu de 10. C’est à peine paresseux. Le problème est que le Supplier dans tail est appelé à plusieurs reprises sur chaque exploration à la demande de la lazy liste; Vous pouvez résoudre ce problème en vous assurant que le Supplier dans la méthode tail ne soit appelé que sur la première exploration à la demande – et que sa valeur résultante soit mise en cache – ce qui consolide la liste à ce stade. Cela peut être réalisé en ajoutant un champ Private Optional<LazyList<T>>alreadyComputed à votre définition de LazyList et en faisant en sorte que la méthode tail la consulte et la mette à jour de manière appropriée. Le langage fonctionnel pur Haskell fait en sorte que toutes ses structures de données sont correctement paresseuses dans ce dernier sens. Lisez l’un des nombreux articles sur Haskell si vous êtes intéressé.

Notre ligne directrice est de se rappeler que les structures de données paresseuses peuvent être une arme utile dans votre arsenal de programmation. Utilisez-les lorsqu’ils facilitent la programmation d’une application. Réécrivez-les dans un style plus traditionnel seulement s’ils causent une inefficacité inacceptable.

Passons maintenant à une autre caractéristique de presque tous les langages de programmation fonctionnels, mais qui manque à Java: la correspondance de modèle(le pattern matching).

14.4. Correspondance de modèle

Il y a un autre aspect important à ce qui est généralement considéré comme la programmation fonctionnelle, et c’est la correspondance (structurelle) de modèle (à ne pas confondre avec la correspondance de modèle et la regex). Rappelons que le chapitre 1 s’est terminé en observant que les mathématiques peuvent écrire des définitions telles que

tandis qu’en Java, vous devez écrire une instruction if-then-else ou une instruction switch. À mesure que les types de données deviennent plus complexes, la quantité de code (et d’encombrement) nécessaire pour les traiter augmente. L’utilisation du pattern matching peut réduire ce fouillis.

Pour illustrer, prenons une structure arborescente que vous aimeriez traverser. Considérons un langage arithmétique simple composé de nombres et d’opérations binaires:

Supposons que l’on vous demande d’écrire une méthode pour simplifier certaines expressions. Par exemple, 5 + 0 peut être simplifié à 5. En utilisant notre domaine, new BinOp (« + », new Number (5), new Number (0)) pourrait être simplifié en nombre (5). Vous pouvez traverser une structure Expr comme suit:

Vous pouvez voir que cela devient rapidement très laid!

14.4.1. Modèle de conception de visiteur

Une autre façon de déballer le type de données en Java consiste à utiliser le design pattern visiteur. En substance, vous pouvez créer une classe distincte qui encapsule un algorithme pour « visiter » un type de données spécifique.

Comment ça marche? La classe visiteur doit prendre en entrée une instance spécifique du type de données. Il peut alors accéder à tous ses membres. Voici un exemple de comment cela fonctionne. Tout d’abord, vous ajoutez la méthode accept à BinOp, qui prend comme argument l’argument SimplifyExprVisitor et lui transmet sa propre instance (vous ajoutez également une méthode similaire pour Number):

Le SimplifyExprVisitor peut maintenant accéder à un objet BinOp et le déplier (unwrap):

14.4.2. Pattern matching à la rescue

Il existe une solution plus simple utilisant une fonctionnalité appelée pattern matching. Il n’est pas disponible en Java, nous allons donc utiliser de petits exemples du langage de programmation Scala pour illustrer la correspondance de modèles. Cela vous donnera une idée de ce qui pourrait être possible en Java si la correspondance de modèles était supportée.

Étant donné le type de données Expr représentant les expressions arithmétiques, dans le langage de programmation Scala (nous l’utilisons car sa syntaxe est la plus proche de Java), vous pouvez écrire le code suivant pour décomposer une expression:

Cette utilisation du pattern matching donne une manière extrêmement concise et expressive de manipuler de nombreuses structures de données arborescentes. Il est généralement utile lors de la création de compilateurs ou de moteurs pour le traitement des règles métier. Notez que la syntaxe Scala

est très similaire à la syntaxe Java

La principale différence syntaxique visible est que Scala est orienté vers l’expression alors que Java est plus axé sur les déclarations, mais la principale différence d’expressivité pour le programmeur est que les patterns Java sont limités à quelques types primitifs, énumérations, quelques classes spéciales qui enveloppent certains types primitifs, et les chaînes. L’un des plus grands avantages pratiques de l’utilisation des langages avec correspondance de modèle est que vous pouvez éviter d’utiliser de grandes chaînes de commutateurs ou des instructions if-then-else imbriquées dans des opérations de sélection de champs.

Ici, il est clair que le pattern matching de Scala gagne en facilité d’expressivité sur Java, et vous ne pouvez vous attendre qu’à un futur Java permettant des instructions de Switch plus expressives. Nous faisons une proposition concrète pour cela au chapitre 16.

En attendant, voyons comment Java 8 lambdas peut fournir un moyen alternatif d’obtenir un code semblable à un pattern en Java. Nous décrivons cette technique uniquement pour que vous puissiez voir une autre application intéressante de lambdas.

Faking pattern correspondant en Java

Tout d’abord, considérons à quel point la forme d’expression de pattern matching de Scala est riche. Par exemple, le cas

signifie « vérifier que expr est un BinOp, extraire ses trois composants (opname, left, rigth), puis faire correspondre ces composants-le premier par rapport à la String +, le second par rapport à la variable e (qui correspond toujours), puis le troisième contre le motif Number (0). »En d’autres termes, la correspondance des formes dans Scala (et beaucoup d’autres langages fonctionnels) est multiniveau. Notre simulation du pattern matching en utilisant les lambdas de Java 8 ne donnera qu’une correspondance de modèle à un seul niveau; dans l’exemple précédent cela signifierait des cas tels que BinOp (op, l, r) ou Number(n) mais pas BinOp (« + », e, Number (0)).

D’abord, nous faisons une observation légèrement surprenante. Maintenant que vous avez des lambdas, vous ne pouvez en principe jamais utiliser if-then-else dans votre code. Vous pourriez remplacer le code tel que condition?e1:e2 avec un appel de méthode:

Quelque part, peut-être dans une bibliothèque, vous auriez une définition (générique dans le type T):

Le type T joue le rôle du type résultat de l’expression conditionnelle. En principe, des astuces similaires peuvent être faites avec if-then-else.

Bien sûr, dans le code normal, cela rendrait votre code plus obscur parce que if-then-else capture parfaitement cet idiome. Mais nous avons noté que le Switch de Java et if-then-else ne capturent pas l’idiome du pattern matching, et il s’avère que les lambdas peuvent coder(à un seul niveau) le pattern matching de façon très simple – et plus nettement que les chaînes de if-then-else.

Pour revenir aux valeurs de pattern matching de la classe Expr, qui a deux sous-classes, BinOp et Number, vous pouvez définir une méthode patternMatchExpr (à nouveau générique en T, le type de résultat de la correspondance de modèle):

Le résultat est que l’appel de méthode

déterminera si e est un BinOp (et, si tel est le cas, lance la méthode binopcode, qui a accès aux champs de BinOp via les identifiants op, l, r), ou s’il s’agit d’un Number (lance la méthode numcode et qui a accès à la valeur n). La méthode prévoit même un code par défaut, qui serait exécuté si quelqu’un créait plus tard un nœud d’arbre qui n’était ni un BinOp ni un Number.

La figure suivante montre comment commencer à utiliser patternMatchExpr en simplifiant les expressions d’addition et de multiplication.

Figure 14.1. Implémentation de la correspondance de modèle pour simplifier une expression

Vous pouvez maintenant appeler la méthode simplify comme suit:

Vous avez vu beaucoup d’informations à ce jour: fonctions d’ordre supérieur, currying, structures de données persistantes, listes paresseuses et correspondance de formes! Nous regardons maintenant certaines subtilités, que nous avons différées jusqu’à la fin pour éviter de trop compliquer le texte.

14.5. Recueil

Dans cette section, nous explorons deux subtilités: celle d’être fonctionnel et d’avoir une transparence référentielle; l’un concerne l’efficacité et l’autre concerne le retour du même résultat. Ce sont des questions intéressantes, mais nous les plaçons ici parce qu’elles sont des subtilités concernant les effets secondaires plutôt que le concept en lui même. Nous explorons également l’idée des combinateurs – méthodes ou fonctions qui prennent deux ou plusieurs fonctions et retournent une autre fonction; cette idée a inspiré de nombreux ajouts à l’API Java 8.

14.5.1. Mise en cache ou mémo

Supposons que vous ayez une méthode sans effet secondaire, computeNumberOfNodes (Range) qui calcule le nombre de nœuds à l’intérieur d’une plage donnée dans un réseau avec une topologie arborescente. Supposons que le réseau ne change jamais (c’est-à-dire que la structure est immuable), mais l’appel de la méthode computeNumberOfNodes est coûteux étant donné que la structure doit être parcourue récursivement. Vous voudrez peut-être calculer les résultats encore et encore. Si vous avez de la transparence référentielle, il y a une manière astucieuse d’éviter cette surcharge supplémentaire. Une solution standard à ce problème est la mémorisation – ajouter un cache (par exemple, un HashMap) à la méthode en tant que wrapper – lorsque le wrapper est appelé. Il consulte d’abord le cache pour voir si la paire (argument, résultat) est déjà dans le cache; si c’est le cas, il peut retourner le résultat stocké immédiatement; sinon, vous appelez computeNumberOfNodes, mais avant de retourner le resultat, vous stockez d’abord la nouvelle paire (argument, résultat) dans le cache. Strictement parlant, il s’agit d’une solution non fonctionnelle car elle mute une structure de données partagée par plusieurs appelants, mais la version enveloppée du code est référentiellement transparente.

En pratique, cela fonctionnerait comme suit:

Java 8 améliore l’interface Map avec une méthode computeIfAbsent pour de tels cas d’utilisation. Nous le mentionnons dans l’annexe B. Mais pour votre information vous pouvez utiliser la méthode computeIfAbsent comme suit pour écrire du code plus clair:

Il est clair que la méthode computeNumberOfNodesUsingCache est référentiellement transparente (en supposant que la méthode computeNumberOfNodes est également référentiellement transparente). Mais le fait que numberOfNodes soit un état partagé mutable, et que HashMap ne soit pas synchronisé, signifie que ce code n’est pas thread-safe. Même l’utilisation de Hashtable (verrouillé) ou de ConcurrentHashMap (concurrent sans verrouillage) au lieu de HashMap peut ne pas donner les résultats attendues s’il y a des appels parallèles à numberOfNodes à partir de plusieurs cœurs, car il y a une situation de compétition entre le fait que vous trouviez que range ne soit pas dans la Map et l’insertion de la paire (argument, résultat) dans la Map. Cela signifie que plusieurs processus peuvent calculer la même valeur à ajouter à la map.

Peut-être la meilleure chose à retenir de cette lutte est que mélanger l’état mutable avec la concurrence est plus délicat que vous ne l’imaginez, et la programmation fonctionnelle évite complètement, sauf pour les hacks de performance de bas niveau tels que la mise en cache. Une deuxième chose est que, mis à part la mise en cache, si vous codez dans un style fonctionnel, vous n’aurez jamais besoin de savoir si une autre méthode fonctionnelle que vous appelez est synchronisée, car vous savez qu’elle n’a pas d’état mutable partagé.

14.5.2. Que signifie « retourner le même objet »?

Considérons à nouveau l’exemple de l’arbre binaire de la section 14.2.3. Dans la figure 14.4, la variable t pointe vers un arbre existant, et la figure montre l’effet de l’appel de fupdate (« Will », 26, t) pour produire un nouvel arbre, que nous supposerons assigné à la variable t2. La figure montre clairement que t, et toutes les structures de données accessibles à partir de celle-ci, ne sont pas mutées. Supposons maintenant que vous effectuez un appel textuellement identique:

Maintenant, t3 pointera vers trois autres noeuds nouvellement créés, contenant les mêmes données que celles de t2. La question est la suivante: « fupdate est-il référentiellement transparent? » Referentiellement transparent signifie « arguments égaux (le cas ici) impliquent des résultats égaux. » Le problème est que t2 et t3 sont des références différentes et donc (t2 == t3) est faux, il semble que vous deviez conclure que fupdate n’est pas référentiellement transparent. Mais lors de l’utilisation de structures de données persistantes qui ne doivent pas être modifiées, il n’y a logiquement aucune différence entre t2 et t3.

Nous pouvons débattre longuement de ce point, mais l’adage le plus simple est que la programmation fonctionnelle utilise généralement equals pour comparer les valeurs structurées plutôt que == (égalité de référence) parce que les données ne sont pas modifiées et sous ce modèl fupdate est référentiellement transparent.

14.5.3. Combinateurs

En programmation fonctionnelle, il est courant et naturel d’écrire une fonction d’ordre supérieur (peut-être écrite comme une méthode) qui accepte, par exemple, deux fonctions et produit une autre fonction combinant ces fonctions. Le terme combinateur est généralement utilisé pour cette idée. Une grande partie de la nouvelle API Java 8 est inspirée par cette idée; par exemple, thenCombine dans la classe CompletableFuture. Cette méthode prend deux CompletableFutures et une BiFunction pour produire un autre CompletableFuture.

Bien qu’une discussion détaillée des combinateurs dans la programmation fonctionnelle dépasse la portée de ce tutoriel, il vaut la peine d’examiner quelques cas particuliers pour donner une idée de la façon dont les opérations qui prennent et retournent les fonctions sont une pratique de programmation fonctionnelle très courante. La méthode suivante encode l’idée de la composition de fonction:

Il prend les fonctions f et g comme arguments et renvoie une fonction dont l’effet est de faire f d’abord, puis g. Vous pouvez ensuite l’utiliser pour définir une opération, qui capture l’itération interne en tant que combinateur. Regardons le cas où vous souhaitez prendre des données et appliquez la fonction f à répétition, disons n fois, comme dans une boucle. Votre opération, appelons la repeat, prend une fonction, f, disant ce qui se passe dans une itération et renvoyant une fonction qui dit ce qui se passe dans n itérations. Un appel tel que

donnera x -> (2 * (2 * (2 * x))) ou x -> 8 * x.

Vous pouvez le tester en écrivant

qui imprime 80.

La méthode repeat peut être codée comme suit (notez le cas particulier d’une boucle de zéro-déclenchement):

Des variantes de cette idée peuvent modéliser des notions plus riches d’itération, y compris avoir un modèle fonctionnel d’état mutable passé entre les itérations. Mais il est temps de passer à autre chose. Le rôle de ce chapitre est de donner un résumé de la programmation fonctionnelle comme base de Java 8. Il existe de nombreux excellents livres explorant la programmation fonctionnelle de manière plus approfondie.

14.6. Résumé

Voici les concepts clés que vous devriez retenir de ce chapitre:

Les fonctions de première classe sont des fonctions qui peuvent être passées en arguments, renvoyées en tant que résultats et stockées dans des structures de données.
Une fonction d’ordre supérieur est une fonction qui prend au moins une ou plusieurs fonctions en entrée ou renvoie une autre fonction. Les fonctions d’ordre supérieur typiques en Java comprennent comparing, andThen, et compose.
Currying est une technique qui vous permet de moduler des fonctions et de réutiliser du code.
Une structure de données persistante préserve sa version précédente lorsqu’elle est modifiée. En conséquence, elle peut empêcher la copie défensive inutile.
Les flux en Java ne peuvent pas être auto-définis.
Une liste paresseuse est une version plus expressive d’un flux Java. Une liste paresseuse vous permet de produire des éléments de la liste à la demande en utilisant un supplier qui peut créer d’avantages d’éléments de la structure de données.
Le pattern matching est une fonctionnalité qui vous permet de unwraper des types de données. Cela peut être vu comme une généralisation de l’instruction switch de Java.
La transparence référentielle permet aux calculs d’être mis en cache.
Les combinateurs sont une idée fonctionnelle qui combine deux ou plusieurs fonctions ou d’autres structures de données.