Hallo, Bewohner! Viele Programmierfehler werden durch Datentypinkongruenzen verursacht. Ein starkes Typsystem vermeidet eine ganze Klasse von Fehlern und stellt die Datenintegrität in der gesamten Anwendung sicher. Durch das Erlernen der Beherrschung von Typen in der täglichen Praxis erstellt ein Entwickler besseren Code und spart Zeit, um knifflige Datenfehler zu finden.
Das Buch zeigt Ihnen, wie Sie mithilfe der Eingabe Software erstellen, die nicht nur sicher ist, reibungslos funktioniert, sondern auch einfach zu warten ist.
In TypeScript geschriebene Beispiele für Problemlösungen helfen Ihnen dabei, Ihre Fähigkeiten im Umgang mit Typen zu entwickeln, von einfachen Datentypen bis hin zu komplexeren Konzepten wie Funktoren und Monaden.
In diesem Buch:
- Erstellung von Datenstrukturen basierend auf einfachen Typen, Arrays und Referenzen.
- Objektorientierte Programmierung und Typen.
- Verwendung von Generika und Typen höherer Ordnung.
Dieses Buch erfordert Erfahrung mit einer der gängigen Programmiersprachen wie TypeScript, Java, JavaScript, C # oder C ++.
Für wen ist dieses Buch?
Das Buch ist für praktizierende Programmierer gedacht. Der Leser sollte gut darin sein, Code in einer der Programmiersprachen wie Java, C #, C ++ oder JavaScript / TypeScript zu schreiben. Codebeispiele sind in TypeScript enthalten, aber der größte Teil des Materials ist auf jede Programmiersprache anwendbar. Tatsächlich verwenden die Beispiele nicht immer typisches TypeScript. Wann immer möglich, haben sie sich angepasst, damit Programmierer in anderen Programmiersprachen sie verstehen können. Die Zusammenstellung von Codebeispielen ist in Anhang A beschrieben, und ein kurzes TypeScript-Spickzettel ist in Anhang B beschrieben.
Wenn Sie an der objektorientierten Codeentwicklung für die Arbeit beteiligt sind, haben Sie möglicherweise von algebraischen Datentypen (ADTs), Lambda-Ausdrücken, Generika, Funktoren, Monaden gehört und möchten besser verstehen, was diese sind und wie Sie sie in Ihrer Arbeit verwenden .
Dieses Buch zeigt Ihnen, wie Sie das Typsystem einer Programmiersprache verwenden, um weniger fehleranfälligen, modulareren und verständlicheren Code zu entwerfen. Sie werden sehen, wie Sie Laufzeitfehler, die das gesamte System zum Absturz bringen können, in Kompilierungsfehler umwandeln und abfangen, bevor sie in Schwierigkeiten geraten.
Der Großteil der Literatur zu Typsystemen ist stark formalisiert. Das Buch konzentriert sich auf praktische Anwendungen von Typsystemen; deshalb ist sehr wenig Mathematik darin. Es ist jedoch ratsam, dass Sie grundlegende Algebra-Konzepte wie Funktionen und Mengen verstehen. Dies ist erforderlich, um einige der Konzepte zu klären, die wir benötigen.
Verallgemeinerte Algorithmen und Interatoren
In diesem Kapitel
- Die Verwendung von map () -, filter () - und redu () -Operationen gilt nicht nur für Arrays.
- Lösen einer Vielzahl von Problemen mithilfe einer Reihe gängiger Algorithmen.
- Bieten Sie generische Datentypunterstützung für den gewünschten Vertrag.
- Implementierung einer Vielzahl von Algorithmen unter Verwendung verschiedener Kategorien von Iteratoren.
- Implementierung adaptiver Algorithmen.
Dieses Kapitel konzentriert sich ausschließlich auf generische, wiederverwendbare Algorithmen, die für eine Vielzahl von Datentypen und -strukturen geeignet sind.
Wir haben uns in Kapitel 5 jeweils eine Version der Operationen map (), filter () und reduct () angesehen, als wir Funktionen höherer Ordnung besprochen haben. Diese Funktionen funktionieren mit Arrays, aber wie wir in den vorherigen Kapiteln gesehen haben, sind Iteratoren eine großartige Abstraktion für die Arbeit mit jeder Datenstruktur. Wir beginnen mit der Implementierung generischer Versionen der oben genannten drei Algorithmen, die mit Iteratoren arbeiten und daher auf die Verarbeitung von Binärbäumen, Listen, Arrays und anderen iterierbaren Datenstrukturen anwendbar sind.
Die Operationen map (), filter () und redu () sind nicht eindeutig. Wir werden über andere generische Algorithmen und Algorithmusbibliotheken sprechen, die in den meisten modernen Programmiersprachen verfügbar sind. Wir werden sehen, warum es besser ist, die meisten Schleifen durch Aufrufe von Bibliotheksalgorithmen zu ersetzen. Wir werden auch ein wenig über flüssige APIs und benutzerfreundliche Algorithmenschnittstellen sprechen.
Als nächstes gehen wir auf die Einschränkungen der Parametertypen ein. Generische Datenstrukturen und Algorithmen können die Funktionen angeben, die in ihren Parametertypen vorhanden sein müssen. Diese Spezialisierung führt zu etwas weniger universellen Datenstrukturen und Algorithmen, die nicht überall verwendbar sind.
Wir werden detaillierter auf Iteratoren eingehen und über ihre verschiedenen Kategorien sprechen. Je spezialisierter ein Iterator ist, desto effizientere Algorithmen sind mit seiner Teilnahme möglich. Allerdings können nicht alle Datenstrukturen spezialisierte Iteratoren unterstützen.
Abschließend werfen wir einen kurzen Blick auf adaptive Algorithmen. Sie ermöglichen vielseitigere, aber weniger effiziente Implementierungen für Iteratoren mit weniger Funktionen und effizientere, aber weniger vielseitige Implementierungen für Iteratoren mit mehr Funktionen.
10.1. Verbesserte Operationen für map (), filter () und redu ()
In Kapitel 5 haben wir über die Operationen map (), filter () und redu () gesprochen und uns jeweils eine der möglichen Implementierungen angesehen. Diese Algorithmen sind Funktionen höherer Ordnung, da sie eine andere Funktion als Argument verwenden und auf eine Datenfolge anwenden.
Die map () -Operation wendet eine Funktion auf jedes Element in der Sequenz an und gibt die Ergebnisse zurück. Die filter () -Operation wendet eine Filterfunktion auf jedes Element an und gibt nur diejenigen zurück, für die diese Funktion true zurückgibt. Die Operation redu () gruppiert alle Werte in einer Sequenz mithilfe einer Funktion und gibt als Ergebnis einen einzelnen Wert zurück.
Unsere Implementierung in Kapitel 5 verwendete den generischen Parametertyp T und stellte Sequenzen als Arrays von Elementen vom Typ T dar.
10.1.1. Map () -Operation
Erinnern wir uns, wie wir die map () - Operation implementiert haben. Wir hatten zwei Typparameter: T und U. Die Funktion verwendet als Argument ein Array von Werten vom Typ T und eine Funktion, die als zweites Argument von T nach U konvertiert. Es gibt ein Array von U-Werten zurück, wie in Listing 10.1 gezeigt.
Mit unserem Wissen über Iteratoren und Generatoren sehen wir uns in Listing 10.2 an, wie map () implementiert wird, damit es mit jedem Iterable <T> und nicht nur mit Arrays funktioniert.
Während die ursprüngliche Implementierung auf Arrays beschränkt war, kann diese mit jeder Datenstruktur arbeiten, die einen Iterator bereitstellt. Außerdem ist der Code viel kompakter geworden.
10.1.2. Filter () -Operation
Machen wir dasselbe mit filter () (Listing 10.3). Unsere ursprüngliche Implementierung erwartete ein Array von Elementen vom Typ T und ein Prädikat als Eingabe. Ich möchte Sie daran erinnern, dass ein Prädikat eine Funktion ist, die ein Element eines Typs verwendet und einen Booleschen Wert zurückgibt. Wenn eine bestimmte Funktion für einen an sie übergebenen Wert true zurückgibt, erfüllt der Wert das Prädikat.
Wie bei der map () -Operation verwenden wir eine Iterable <T> anstelle eines Arrays und implementieren diese Iterable als Generator, der Werte erzeugt, die dem Prädikat entsprechen, wie in Listing 10.4 gezeigt.
Wiederum hat sich eine lakonischere Implementierung herausgestellt, die nicht nur mit Arrays arbeiten kann. Schließlich ändern wir die Funktion redu ().
10.1.3. Reduzieren () Betrieb
Unsere ursprüngliche Implementierung von redu () erwartete ein Array von Elementen vom Typ T, einen Anfangswert vom Typ T (falls das Array leer war) und eine Operation op (). Diese Operation ist eine Funktion, die zwei Werte vom Typ T als Argumente verwendet und einen Wert vom Typ T zurückgibt. Die Operation redu () wendet die Operation auf den Anfangswert an, und das erste Element des Arrays speichert das Ergebnis und wendet das an gleiche Operation für das Ergebnis und das nächste Element des Arrays usw. (Listing 10.5)
Sie können diese Funktion neu schreiben, um Iterable <T> anstelle eines Arrays zu verwenden und mit einer beliebigen Sequenz zu arbeiten, wie in Listing 10.6 gezeigt. In diesem Fall benötigen wir keinen Generator. Im Gegensatz zu den beiden vorherigen Funktionen gibt redu () keine Folge von Elementen zurück, sondern einen einzelnen Wert.
Der Rest der Implementierung hat sich nicht geändert.
10.1.4. Filter () / redu () Pipeline
Lassen Sie uns sehen, wie diese Algorithmen zu einer Pipeline kombiniert werden, die nur gerade Zahlen aus einem Binärbaum auswählt und zusammenfasst. Verwenden wir die BinaryTreeNode <T> -Klasse aus Kapitel 9 mit ihrer zentrierten Baumdurchquerung und verketten sie mit einem Filter für gerade Zahlen und einer Funktion redu (), die Addition als Operation verwendet (Listing 10.7).
Dieses Beispiel ist ein lebender Beweis für die Wirksamkeit generischer Typen. Anstatt eine neue Funktion zum Durchlaufen eines Binärbaums und zum Summieren gerader Zahlen zu implementieren, bilden wir einfach eine Verarbeitungspipeline speziell für das gewünschte Szenario.
10.1.5. Übungen
- Erstellen Sie eine Pipeline für eine iterierbare Zeichenfolge: die Verkettung aller nicht leeren Zeichenfolgen.
- Erstellen Sie eine Pipeline, um eine iterierbare Typennummer zu verarbeiten: Wählen Sie alle ungeraden Zahlen aus und quadrieren Sie sie.
10.2. Gängige Algorithmen
Wir haben die Algorithmen map (), filter () und reduct () besprochen und auch take () in Kapitel 9 erwähnt. Viele andere Algorithmen werden häufig in Pipelines verwendet. Ich werde einige von ihnen auflisten. Wir werden uns nicht mit Implementierungen befassen - ich werde nur beschreiben, welche Argumente (außer Iterable) sie erhalten und wie sie die Daten verarbeiten. Außerdem werde ich die verschiedenen Namen auflisten, auf die sich diese Algorithmen beziehen können:
- map () verwendet als Eingabe eine Folge von Werten vom Typ T und eine Funktion (Wert: T) => U und gibt eine Folge von Werten vom Typ U zurück, nachdem diese Funktion auf alle Werte der Eingabe angewendet wurde Reihenfolge. Es erscheint auch unter den Namen fmap (), select ();
- 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, , .
Es gibt viele andere Algorithmen zum Sortieren, Umkehren, Teilen und Verketten von Sequenzen. Glücklicherweise sind diese Algorithmen in so vielen Bereichen so nützlich und anwendbar, dass Sie sie nicht selbst implementieren müssen. Für die meisten Programmiersprachen gibt es Bibliotheken mit vorgefertigten Implementierungen. JavaScript enthält die Pakete underscore.js und lodash mit jeweils vielen ähnlichen Algorithmen. (Zum Zeitpunkt dieses Schreibens unterstützen diese Bibliotheken keine Iteratoren - nur das integrierte JavaScript-Array und die Objekttypen.) In Java befinden sie sich im Paket java.util.stream. In C # befinden sie sich im System.Linq-Namespace. In C ++ in der Header-Datei der Standardbibliothek <algorithmus>.
10.2.1. Algorithmen statt Schleifen
Sie werden vielleicht überrascht sein, aber es gibt eine gute Faustregel: Wenn Sie einen Algorithmus schreiben, überprüfen Sie, ob es einen Bibliotheksalgorithmus oder eine Pipeline für die Aufgabe gibt. Schleifen werden normalerweise geschrieben, um Sequenzen zu verarbeiten - genau das, was die oben diskutierten Algorithmen tun.
Bibliotheksalgorithmen werden benutzerdefinierten Schleifen vorgezogen, da die Fehlerwahrscheinlichkeit geringer ist. Bibliotheksalgorithmen sind bewährt und effizient implementiert und können verwendet werden, um Code durch explizite Angabe von Operationen lesbarer zu machen.
Wir haben uns in diesem Buch mehrere Implementierungen angesehen, um die Interna besser zu verstehen, aber Sie müssen die Algorithmen selten selbst implementieren. Wenn Sie auf eine Aufgabe stoßen, die über die Möglichkeiten bestehender Algorithmen hinausgeht, ist es besser, eine generische, wiederverwendbare Implementierung zu erstellen als eine einmalige, spezialisierte.
10.2.2. Implementierung einer Fluidleitung
Die meisten Bibliotheken bieten eine flüssige API für Pipelining-Algorithmen. Fluid-APIs sind verkettete APIs, die das Lesen Ihres Codes erheblich erleichtern. Betrachten wir den Unterschied zwischen einer Fluid-API und einer Nicht-Fluid-API am Beispiel der Filter- / Faltungspipeline aus Abschnitt 10.1.4 (Listing 10.8).
Und obwohl wir zuerst die filter () - Operation anwenden und dann das Ergebnis an die redu () - Operation übergeben, sehen wir beim Lesen des Codes von links nach rechts redu () vor filter (). Es ist auch ziemlich schwierig herauszufinden, welche Argumente sich auf eine bestimmte Funktion in einer Pipeline beziehen. Die flüssige API erleichtert das Lesen Ihres Codes erheblich.
Derzeit verwenden alle unsere Algorithmen ein iterierbares Objekt als erstes Argument und geben einen Iterator zurück. Objektorientierte Programmierung wird unsere API verbessern. Es ist möglich, alle unsere Algorithmen in einer iterierbaren Wrapper-Klasse zu sammeln. Rufen Sie dann eine der Iterables auf, ohne sie explizit als erstes Argument anzugeben, da die Iterable nun Mitglied der Klasse ist. Wir tun dies für map (), filter () und redu () und gruppieren sie in eine neue FluentIterable <T> -Klasse, die ein Iterable-Objekt umschließt, wie in Listing 10.9 gezeigt.
Basierend auf dem Iterable <T> können wir ein FluentIterable <T> erstellen, sodass wir unsere Filter- / Reduktions-Pipeline neu schreiben können, um flüssiger zu werden. Lassen Sie uns ein FluentIterable <T> -Objekt erstellen, filter () darauf aufrufen, ein neues FluentIterable <T> -Objekt basierend auf seinen Ergebnissen erstellen und redu () darauf aufrufen, wie in Listing 10.10 gezeigt.
Jetzt kommt filter () vor reduct () und es ist ziemlich klar, dass sich die Argumente auf diese Funktion beziehen. Das einzige Problem ist die Notwendigkeit, nach jedem Funktionsaufruf ein neues FluentIterable <T> zu erstellen. Sie können diese API verbessern, indem Sie die Funktionen map () und filter () neu schreiben, um einen FluentIterable <T> anstelle eines IterableIterator <T> zurückzugeben. Beachten Sie, dass Sie die Methode redu () nicht ändern müssen, da redu () einen einzelnen Wert vom Typ T zurückgibt, keinen iterierbaren.
Da wir jedoch Generatoren verwenden, können wir den Rückgabetyp nicht einfach ändern. Das Ziel von Generatoren ist es, eine bequeme Syntax für Funktionen bereitzustellen, aber sie geben immer einen IterableIterator <T> zurück. Stattdessen können wir die Implementierungen in zwei private Methoden verschieben, mapImpl () und filterImpl (), und von IterableIterator <T> in FluentIterable <T> in den Methoden public map () und filter () konvertieren, wie in Listing 10.11 gezeigt.
Diese verbesserte Implementierung erleichtert das Verketten von Algorithmen, da alle jetzt ein FluentIterable zurückgeben, in dem alle Algorithmen als Methoden beschrieben werden, wie in Listing 10.12 gezeigt.
In dieser wirklich flüssigen Version ist der Code von links nach rechts leicht zu lesen, und die Syntax zum Verketten einer beliebigen Anzahl von Algorithmen, aus denen die Pipeline besteht, sieht ganz natürlich aus. Ein ähnlicher Ansatz wird in den meisten algorithmischen Bibliotheken verwendet, um die Verkettung mehrerer Algorithmen so einfach wie möglich zu gestalten.
Abhängig von der Programmiersprache besteht einer der Nachteile von Fluent-APIs darin, die FluentIterable-Klasse mit Methoden für alle Algorithmen zu überladen, was die Erweiterung erschwert. Wenn es in der Bibliothek enthalten ist, kann der aufrufende Code keinen neuen Algorithmus hinzufügen, ohne die Klasse zu ändern. C # verfügt über sogenannte Erweiterungsmethoden, mit denen Sie einer Klasse oder Schnittstelle Methoden hinzufügen können, ohne den Code ändern zu müssen. Allerdings verfügen nicht alle Sprachen über solche Funktionen. In den meisten Fällen ist es jedoch besser, eine vorhandene Bibliothek von Algorithmen zu verwenden, als eine neue von Grund auf neu zu implementieren.
10.2.3. Übungen
- Erweitern Sie die FluentIterable-Klasse um einen take () -Algorithmus, der die ersten n Elemente vom Iterator zurückgibt.
- Erweitern Sie die FluentIterable-Klasse um einen drop () -Algorithmus, der die ersten n Elemente aus dem Iterator überspringt und den Rest zurückgibt.
10.3. Begrenzung der Parametertypen
Wir haben bereits gesehen, wie generische Datenstrukturen eine Form von Daten definieren, die nicht von einem bestimmten Typparameter T abhängt. Wir haben uns auch eine Reihe von Algorithmen angesehen, die Iteratoren verwenden, um Folgen von Werten vom Typ T zu verarbeiten, unabhängig von welchem Typ es ist. Stellen Sie sich nun in Listing 10.13 ein Szenario vor, in dem ein bestimmter Datentyp wichtig ist: eine generische Funktion renderAll (), die eine Iterable <T> als Argument verwendet und render () für jedes vom Iterator zurückgegebene Element aufruft.
Der Versuch, diese Funktion zu kompilieren, führt zu der folgenden Fehlermeldung: Die Eigenschaft 'render' ist für den Typ 'T' nicht vorhanden (für den Typ 'T' fehlt die Eigenschaft 'render').
Wir versuchen, die render () -Methode eines generischen Typs T aufzurufen, der möglicherweise keine solche Methode hat. In einem solchen Szenario, müssten Sie beschränken Typ T nur die spezifischen Inkarnationen, die die render () Methode enthalten.
Einschränkungen der Parametertypen
Einschränkungen informieren den Compiler über die Funktionen, die ein Argumenttyp haben muss. Der Argumenttyp kann ohne Einschränkungen beliebig sein. Wenn es erforderlich ist, dass ein generischer Datentyp bestimmte Klassenmitglieder hat, reduzieren wir mithilfe von Einschränkungen die Menge der zulässigen Typen auf diejenigen, die diese erforderlichen Mitglieder haben.
In unserem Fall können wir die IRenderable-Schnittstelle definieren, die die render () -Methode deklariert, wie in Listing 10.14 gezeigt. Sie können dann eine Einschränkung für den Typ T hinzufügen, indem Sie das Schlüsselwort extended verwenden, um dem Compiler mitzuteilen, dass nur Argumenttypen zulässig sind, die IRenderable enthalten.
10.3.1. Eingeschränkte generische Datenstrukturen
Die meisten generischen Datenstrukturen erfordern keine Einschränkungen des Parametertyps. Jeder Werttyp kann in einer verknüpften Liste, einem Baum und einem Array gespeichert werden. Es gibt jedoch einige Ausnahmen, insbesondere die Hash-Menge.
Die Satzdatenstruktur modelliert den Satz im mathematischen Sinne, sodass eindeutige Werte darin gespeichert und Duplikate verworfen werden. Satzdatenstrukturen enthalten normalerweise Methoden zum Verbinden, Überschneiden und Subtrahieren von anderen Sätzen. Außerdem können Sie überprüfen, ob ein bestimmter Wert in einem Satz enthalten ist. Um diese Prüfung durchzuführen, können Sie diesen Wert mit jedem der Elemente des Satzes vergleichen, obwohl dies kein sehr effizienter Ansatz ist. Im schlimmsten Fall erfordert der Vergleich mit jedem der Elemente des Satzes das Durchlaufen des gesamten Satzes. Eine solche Durchquerung wird in der linearen Zeit O (n) durchgeführt. Sie können diese Notationen in der Seitenleiste „Big O Notation“ unten auffrischen.
Die effizienteste Implementierung besteht darin, alle Werte zu hashen und in einer Schlüsselwertdatenstruktur wie einer Hash-Map oder einem Wörterbuch zu speichern. Strukturen wie diese sind effizienter, sie können Werte in konstanter Zeit O (1) abrufen . Das Hash-Set umschließt die Hash-Map und bietet eine effiziente Überprüfung für die Aufnahme eines Elements. Es gibt jedoch eine Einschränkung: Typ T muss eine Hash-Funktion bereitstellen, die einen Wert vom Typ T annimmt und seinen Hash-Wert vom Typ Nummer zurückgibt.
In einigen Programmiersprachen ist das Hashing aller Werte möglich, indem die Hashing-Methode im höheren Typ beschrieben wird. Beispielsweise enthält der höhere Java-Objekttyp eine hashCode () -Methode und der höhere C # -Objekttyp die GetHashCode () -Methode. Wenn die Sprache jedoch keine solche Möglichkeit bietet, ist eine Typbeschränkung erforderlich, damit nur Typen, die gehasht werden können, in unseren Datenstrukturen gespeichert werden können. Beispielsweise können wir die IHashable-Schnittstelle definieren und als Typeinschränkung für den Schlüsseltyp unserer generischen Hashmap oder unseres Wörterbuchs verwenden.
Über den Autor
Vlad Rishkutsia ist ein Softwareentwicklungsspezialist bei Microsoft mit über zehn Jahren Erfahrung. Während dieser Zeit leitete er mehrere große Softwareprojekte und bildete viele junge Fachkräfte aus.
Weitere Details zum Buch finden Sie auf der Website des Verlags
» Inhaltsverzeichnis
» Auszug
für Einwohner 25% Rabatt auf den Gutschein - TypeScript
Nach Zahlungseingang für die Papierversion des Buches wird ein E-Book per E-Mail verschickt. Mail.