Livre "Programme et type"

Bonjour, Habitants! De nombreuses erreurs de programmation sont causées par des incohérences de type de données. Un système de type fort évite toute une classe d'erreurs et garantit l'intégrité des données dans toute l'application. En apprenant à maîtriser les types dans la pratique quotidienne, un développeur créera un meilleur code et économisera le temps qu'il faudrait pour trouver des erreurs de données délicates.



Le livre vous montre comment utiliser la saisie pour créer des logiciels non seulement sûrs et fonctionnant sans problème, mais également faciles à entretenir.



Des exemples de résolution de problèmes, écrits en TypeScript, vous aideront à développer vos compétences dans le travail avec les types, des types de données simples aux concepts plus complexes tels que les foncteurs et les monades.



Dans ce livre:

• Création de structures de données basées sur des types simples, des tableaux et des références.
• Programmation et types orientés objet.
• Utilisation de génériques et de types d'ordre supérieur.

Ce livre nécessite une expérience avec l'un des langages de programmation courants tels que TypeScript, Java, JavaScript, C # ou C ++.

Pour qui est ce livre

Le livre est destiné aux programmeurs pratiquants. Le lecteur doit être doué pour écrire du code dans l'un des langages de programmation tels que Java, C #, C ++ ou JavaScript / TypeScript. Les exemples de code sont en TypeScript, mais la plupart du matériel est applicable à n'importe quel langage de programmation. En fait, les exemples n'utilisent pas toujours TypeScript typique. Dans la mesure du possible, ils se sont adaptés pour que les programmeurs d'autres langages de programmation puissent les comprendre. L'assemblage d'exemples de code est décrit dans l'annexe A, et une courte feuille de triche TypeScript est décrite dans l'annexe B.



Si vous êtes impliqué dans le développement de code orienté objet pour le travail, vous avez peut-être entendu parler des types de données algébriques (ADT), des expressions lambda, des génériques, des foncteurs, des monades et souhaitez mieux comprendre ce que sont ces derniers et comment les utiliser dans votre travail .



Ce livre vous montrera comment utiliser le système de type d'un langage de programmation pour concevoir un code moins sujet aux erreurs, plus modulaire et compréhensible. Vous verrez comment transformer les erreurs d'exécution qui peuvent faire planter tout le système en erreurs de compilation et les attraper avant qu'elles ne se posent des problèmes.



La majeure partie de la littérature sur les systèmes de types est très formalisée. Le livre se concentre sur les applications pratiques des systèmes de type; il y a donc très peu de mathématiques dedans. Cependant, il est conseillé d'avoir une compréhension des concepts de base de l'algèbre tels que les fonctions et les ensembles. Cela est nécessaire pour clarifier certains des concepts dont nous avons besoin.

Algorithmes et interateurs généralisés

Dans ce chapitre

• L'utilisation des opérations map (), filter () et reduction () ne concerne pas uniquement les tableaux.

• Résoudre un large éventail de problèmes à l'aide d'un ensemble d'algorithmes communs.

• Fournir un support de type de données générique pour le contrat souhaité.

• Implémentation d'une variété d'algorithmes utilisant différentes catégories d'itérateurs.

• Implémentation d'algorithmes adaptatifs.

Ce chapitre se concentre entièrement sur des algorithmes génériques et réutilisables adaptés à une grande variété de types et de structures de données.



Nous avons examiné une version de chacune des opérations map (), filter () et reduction () au chapitre 5 lorsque nous avons discuté des fonctions d'ordre supérieur. Ces fonctions fonctionnent avec des tableaux, mais comme nous l'avons vu dans les chapitres précédents, les itérateurs sont une excellente abstraction pour travailler avec n'importe quelle structure de données. Nous commencerons par implémenter des versions génériques des trois algorithmes ci-dessus qui fonctionnent avec des itérateurs et sont donc applicables au traitement des arbres binaires, des listes, des tableaux et de toute autre structure de données itérable.



Les opérations map (), filter () et reduction () ne sont pas uniques. Nous parlerons d'autres algorithmes génériques et bibliothèques d'algorithmes disponibles dans la plupart des langages de programmation modernes. Nous verrons pourquoi il est préférable de remplacer la plupart des boucles par des appels à des algorithmes de bibliothèques. Nous parlerons également un peu des API fluides et des interfaces d'algorithmes conviviales.



Ensuite, nous allons passer en revue les contraintes des types de paramètres; les structures de données génériques et les algorithmes peuvent spécifier les capacités qui doivent être présentes dans leurs types de paramètres. Cette spécialisation conduit à des structures de données et des algorithmes un peu moins universels qui ne sont pas utilisables partout.



Nous entrerons plus en détail sur les itérateurs et parlerons de leurs différentes catégories. Plus un itérateur est spécialisé, plus des algorithmes efficaces sont possibles avec sa participation. Cependant, toutes les structures de données ne sont pas capables de prendre en charge des itérateurs spécialisés.



Enfin, nous examinerons rapidement les algorithmes adaptatifs. Ils permettent des implémentations plus polyvalentes mais moins efficaces pour les itérateurs avec moins de fonctionnalités et des implémentations plus efficaces mais moins polyvalentes pour les itérateurs avec plus de fonctionnalités.

10.1. Amélioration des opérations de mappage (), de filtrage () et de réduction ()

Dans le chapitre 5, nous avons parlé des opérations map (), filter () et reduction () et avons examiné l'une des implémentations possibles de chacune. Ces algorithmes sont des fonctions d'ordre supérieur car ils prennent une autre fonction comme argument et l'appliquent à une séquence de données.



L'opération map () applique une fonction à chaque élément de la séquence et renvoie les résultats. L'opération filter () applique une fonction de filtre à chaque élément et renvoie uniquement ceux pour lesquels cette fonction renvoie true. L'opération reduction () regroupe toutes les valeurs dans une séquence à l'aide d'une fonction et renvoie une valeur unique en conséquence.



Notre implémentation du chapitre 5 utilisait le type de paramètre générique T et représentait les séquences sous forme de tableaux d'éléments de type T.

10.1.1. Opération Map ()

Rappelons-nous comment nous avons implémenté l'opération map (). Nous avions deux types-paramètres: T et U. La fonction prend comme argument un tableau de valeurs de type T et une fonction qui convertit de T en U comme second argument. Il renvoie un tableau de valeurs U, comme indiqué dans l'extrait 10.1.





Maintenant, avec notre connaissance des itérateurs et des générateurs, voyons dans le Listing 10.2 comment implémenter map () pour qu'il puisse fonctionner avec n'importe quel Iterable <T>, pas seulement des tableaux.





Alors que l'implémentation d'origine était limitée aux tableaux, celle-ci peut fonctionner avec n'importe quelle structure de données qui fournit un itérateur. De plus, le code est devenu beaucoup plus compact.

10.1.2. Fonctionnement du filtre ()

Faisons de même avec filter () (extrait 10.3). Notre implémentation originale attendait un tableau d'éléments de type T et un prédicat en entrée. Permettez-moi de vous rappeler qu'un prédicat est une fonction qui prend un élément d'un certain type et renvoie un booléen. Si une fonction donnée renvoie true pour une valeur qui lui est transmise, on dit que la valeur satisfait le prédicat.





Comme pour l'opération map (), nous utiliserons un Iterable <T> au lieu d'un tableau et implémenterons cet Iterable en tant que générateur qui produit des valeurs qui satisfont le prédicat, comme indiqué dans l'extrait 10.4.





Encore une fois, une implémentation plus laconique s'est avérée, capable de fonctionner non seulement avec des tableaux. Enfin, nous modifions la fonction reduction ().

10.1.3. Réduire () opération

Notre implémentation originale de reduction () attendait un tableau d'éléments de type T, une valeur initiale de type T (au cas où le tableau serait vide) et une opération op (). Cette opération est une fonction qui prend deux valeurs de type T comme arguments et renvoie une valeur de type T. L'opération reduction () applique l'opération à la valeur initiale et le premier élément du tableau, stocke le résultat, applique le même opération au résultat et à l'élément suivant du tableau, et etc. (extrait 10.5)





Vous pouvez réécrire cette fonction pour utiliser Iterable <T> au lieu d'un tableau et travailler avec n'importe quelle séquence, comme indiqué dans le Listing 10.6. Dans ce cas, nous n'avons pas besoin de générateur. Contrairement aux deux fonctions précédentes, Reduce () ne renvoie pas une séquence d'éléments, mais une seule valeur.





Le reste de l'implémentation n'a pas changé.

10.1.4. Filtrer () / réduire () pipeline

Voyons comment combiner ces algorithmes dans un pipeline qui ne sélectionne que des nombres pairs dans un arbre binaire et les résume. Utilisons la classe BinaryTreeNode <T> du chapitre 9 avec son parcours d'arborescence centré et concaténons-la avec un filtre de nombre pair et une fonction reduction () qui utilise l'addition comme opération (extrait 10.7).





Cet exemple est une preuve vivante de l'efficacité des types génériques. Au lieu d'implémenter une nouvelle fonction pour parcourir un arbre binaire et additionner des nombres pairs, nous formons simplement un pipeline de traitement spécifiquement pour le scénario souhaité.

10.1.5. Des exercices

1. Créez un pipeline pour gérer un itérable de type string: la concaténation de toutes les chaînes non vides.
2. Créez un pipeline pour traiter un itérable de type nombre: en sélectionnant tous les nombres impairs et en les mettant au carré.

10.2. Algorithmes courants

Nous avons discuté des algorithmes map (), filter () et reduction (), et avons également mentionné take () au chapitre 9. De nombreux autres algorithmes sont souvent utilisés dans les pipelines. J'en énumérerai quelques-uns. Nous n'allons pas examiner les implémentations - je vais simplement décrire quels arguments (en plus d'itérable) ils reçoivent et comment ils traitent les données. De plus, je listerai les différents noms auxquels ces algorithmes peuvent être référés:

• map () prend en entrée une séquence de valeurs de type T et une fonction (valeur: T) => U, et retourne une séquence de valeurs de type U après avoir appliqué cette fonction à toutes les valeurs de l'entrée séquence. Il apparaît également sous les noms fmap (), sélectionnez ();

• filter() T (value: T) => boolean, T, , true. where();

• reduce() T T (x: T, y: T) => T. reduce() T. fold(), collect(), accumulate(), aggregate();

• any() T (value: T) => boolean. true, ;

• all() T (value: T) => boolean. true, ;

• none() T (value: T) => boolean. true, ;

• take() T n. , n . limit();

• drop() T n. , , n. skip();

• zip() T U, , T U, , .

Il existe de nombreux autres algorithmes pour trier, inverser, fractionner et concaténer des séquences. Heureusement, ces algorithmes sont si utiles et applicables dans tellement de domaines que vous n'avez pas besoin de les implémenter vous-même. Pour la plupart des langages de programmation, il existe des bibliothèques avec des implémentations prêtes à l'emploi. JavaScript a des packages underscore.js et lodash, chacun avec de nombreux algorithmes similaires. (Au moment d'écrire ces lignes, ces bibliothèques ne prennent pas en charge les itérateurs - uniquement les types de tableau et d'objet JavaScript intégrés.) En Java, ils se trouvent dans le package java.util.stream. En C #, ils se trouvent dans l'espace de noms System.Linq. En C ++, dans le fichier d'en-tête de la bibliothèque standard <algrithm>.

10.2.1. Algorithmes au lieu de boucles

Vous pourriez être surpris, mais il existe une bonne règle de base: chaque fois que vous écrivez un algorithme, vérifiez s'il existe un algorithme de bibliothèque ou un pipeline pour la tâche. Les boucles sont généralement écrites pour traiter des séquences - exactement ce que font les algorithmes décrits ci-dessus.



Les algorithmes de bibliothèque sont préférés aux boucles personnalisées car il y a moins de risques d'erreur. Les algorithmes de bibliothèque sont éprouvés et mis en œuvre efficacement, et peuvent être utilisés pour rendre le code plus lisible en spécifiant explicitement des opérations.



Nous avons examiné plusieurs implémentations dans ce livre pour mieux comprendre les éléments internes, mais vous avez rarement besoin d'implémenter les algorithmes vous-même. Si vous rencontrez une tâche qui dépasse la puissance des algorithmes existants, il est préférable de créer une implémentation générique et réutilisable qu'une implémentation ponctuelle et spécialisée.

10.2.2. Mettre en place un pipeline de fluide

La plupart des bibliothèques fournissent une API fluide pour les algorithmes de pipelining. Les API Fluid sont des API chaînées qui facilitent la lecture de votre code. Regardons la différence entre une API fluide et une API non fluide en utilisant le pipeline de filtre / convolution de la section 10.1.4 (extrait 10.8) comme exemple.





Et bien que nous appliquions d'abord l'opération filter (), puis que nous transmettions le résultat à l'opération reduction (), lorsque nous lirons le code de gauche à droite, nous verrons réduire () avant filter (). Il est également assez difficile de déterminer quels arguments font référence à une fonction particulière dans un pipeline. L'API fluide rend votre code beaucoup plus facile à lire.



Actuellement, tous nos algorithmes prennent un objet itérable comme premier argument et renvoient un itérateur. La programmation orientée objet améliorera notre API. Il est possible de rassembler tous nos algorithmes dans une classe wrapper itérable. Et puis appelez l'un des itérables sans le spécifier explicitement comme premier argument, car maintenant l'itérable est un membre de la classe. Nous allons le faire pour map (), filter () et reduction (), en les regroupant dans une nouvelle classe FluentIterable <T> qui encapsule un objet Iterable, comme indiqué dans l'extrait 10.9.





Sur la base de Iterable <T>, nous pouvons créer un FluentIterable <T>, afin que nous puissions réécrire notre pipeline de filtre / réduction pour être plus fluide. Créons un objet FluentIterable <T>, appelons filter () dessus, créons un nouvel objet FluentIterable <T> basé sur ses résultats et appelons reduction () dessus, comme indiqué dans l'extrait 10.10.





Maintenant, filter () vient avant reduction (), et il est assez clair que les arguments se réfèrent à cette fonction. Le seul problème est la nécessité de créer un nouveau FluentIterable <T> après chaque appel de fonction. Vous pouvez améliorer cette API en réécrivant les fonctions map () et filter () pour renvoyer un FluentIterable <T> au lieu d'un IterableIterator <T>. Notez que vous n'avez pas besoin de changer la méthode reduction () car reduction () renvoie une seule valeur de type T, pas une itération.



Mais puisque nous utilisons des générateurs, nous ne pouvons pas simplement changer le type de retour. La raison d'être des générateurs est de fournir une syntaxe pratique pour les fonctions, mais ils renvoient toujours un IterableIterator <T>. Au lieu de cela, nous pouvons déplacer les implémentations dans deux méthodes privées, mapImpl () et filterImpl (), et convertir de IterableIterator <T> en FluentIterable <T> dans les méthodes publiques map () et filter (), comme indiqué dans l'extrait 10.11.







Cette implémentation améliorée facilite l'enchaînement des algorithmes car ils renvoient désormais tous un FluentIterable dans lequel tous les algorithmes sont décrits comme des méthodes, comme indiqué dans l'extrait 10.12.





Maintenant, dans cette version vraiment fluide, le code est facile à lire de gauche à droite, et la syntaxe pour concaténer n'importe quel nombre d'algorithmes qui composent le pipeline semble assez naturelle. Une approche similaire est utilisée dans la plupart des bibliothèques algorithmiques, ce qui facilite au maximum le chaînage de plusieurs algorithmes.



Selon le langage de programmation, l'un des inconvénients des API Fluent est d'encombrer la classe FluentIterable avec des méthodes pour tous les algorithmes, ce qui rend son extension difficile. S'il est inclus dans la bibliothèque, le code appelant n'a aucun moyen d'ajouter un nouvel algorithme sans modifier la classe. C # a des méthodes dites d'extension qui vous permettent d'ajouter des méthodes à une classe ou une interface sans avoir à modifier son code. Cependant, toutes les langues n'ont pas de telles fonctionnalités. Néanmoins, dans la plupart des cas, il est préférable d'utiliser une bibliothèque d'algorithmes existante plutôt que d'en implémenter une nouvelle à partir de zéro.

10.2.3. Des exercices

1. Étendez la classe FluentIterable pour inclure un algorithme take () qui renvoie les n premiers éléments de l'itérateur.
2. Étendez la classe FluentIterable pour inclure un algorithme drop () qui ignore les n premiers éléments de l'itérateur et renvoie tout le reste.

10.3. Limiter les types de paramètres

Nous avons déjà vu comment les structures de données génériques définissent une forme de données qui ne dépend pas d'un paramètre de type particulier T.Nous avons également examiné un ensemble d'algorithmes utilisant des itérateurs pour traiter des séquences de valeurs de type T, quel que soit le type c'est. Maintenant, dans le Listing 10.13, considérons un scénario où un type de données particulier est important: une fonction générique renderAll () qui prend un Iterable <T> comme argument et appelle render () sur chaque élément renvoyé par l'itérateur.





Tenter de compiler cette fonction se termine par le message d'erreur suivant: La propriété «render» n'existe pas sur le type «T» (il manque la propriété «render» de type «T»).



Nous essayons d'appeler la méthode render () d'un type générique T, qui peut ne pas avoir une telle méthode. Dans un tel scénario, vous devrez limiter le type T aux seules incarnations spécifiques qui contiennent la méthode render ().

Limitations des types de paramètres

Les contraintes indiquent au compilateur les capacités qu'un type d'argument doit avoir. Sans restrictions, le type d'argument peut être n'importe quoi. Lorsqu'il est requis qu'un type de données générique ait certains membres de classe, c'est à l'aide de contraintes que nous réduisons l'ensemble des types autorisés à ceux qui ont ces membres obligatoires.



Dans notre cas, nous pouvons définir l'interface IRenderable, qui déclare la méthode render (), comme indiqué dans l'extrait 10.14. Vous pouvez ensuite ajouter une contrainte sur le type de T à l'aide du mot clé extend pour indiquer au compilateur que seuls les types d'argument qui incarnent IRenderable sont autorisés.

10.3.1. Structures de données génériques restreintes

La plupart des structures de données génériques ne nécessitent pas de contraintes de type de paramètre. Tout type de valeur peut être stocké dans une liste liée, une arborescence et un tableau. Cependant, il existe quelques exceptions, en particulier l'ensemble haché.



La structure de données d'ensemble modélise l'ensemble dans un sens mathématique, de sorte que des valeurs uniques y sont stockées et les doublons sont ignorés. Les structures de données d'ensemble incluent généralement des méthodes de jonction, d'intersection et de soustraction d'autres ensembles, et vous permettent également de vérifier si une valeur donnée est incluse dans un ensemble. Pour effectuer cette vérification, vous pouvez comparer cette valeur avec chacun des éléments de l'ensemble, bien que ce ne soit pas une approche très efficace. Dans le pire des cas, la comparaison avec chacun des éléments de l'ensemble nécessite de parcourir l'ensemble de l'ensemble. Un tel parcours est effectué en temps linéaire, O (n). Vous pouvez revoir ces notations dans la barre latérale «Big O Notation» ci-dessous.



L'implémentation la plus efficace consiste à hacher toutes les valeurs et à les stocker dans une structure de données clé-valeur telle qu'une carte de hachage ou un dictionnaire. Les structures comme celles-ci sont plus efficaces, elles peuvent récupérer des valeurs en temps constant , O (1). L'ensemble haché enveloppe la carte de hachage, fournissant une vérification efficace de l'inclusion d'un élément. Mais il a une limitation: le type T doit fournir une fonction de hachage qui prend une valeur de type T et renvoie sa valeur de hachage de type number.



Dans certains langages de programmation, le hachage de toutes les valeurs est possible en décrivant la méthode de hachage dans le type supérieur. Par exemple, le type d'objet Java supérieur inclut une méthode hashCode () et le type d'objet C # supérieur inclut la méthode GetHashCode (). Mais si le langage ne fournit pas une telle possibilité, alors une contrainte de type est nécessaire pour que seuls les types qui peuvent être hachés puissent être stockés dans nos structures de données. Par exemple, nous pouvons définir l'interface IHashable et l'utiliser comme contrainte de type sur le type de clé de notre hashmap ou dictionnaire générique.

A propos de l'auteur

Vlad Rishkutsia est un spécialiste du développement logiciel chez Microsoft avec plus de dix ans d'expérience. Pendant ce temps, il a géré plusieurs projets logiciels d'envergure et formé de nombreux jeunes professionnels.



Plus de détails sur le livre peuvent être trouvés sur le site de la maison d'édition

» Table des matières

» Extrait



Pour Habitants une remise de 25% sur le coupon - TypeScript



Lors du paiement de la version papier du livre, un e-book est envoyé par e- poster.