Hello, Habitants! Many programming errors are caused by data type mismatches. A strong type system avoids an entire class of errors and ensures data integrity throughout the application. By learning to master types in everyday practice, a developer will create better code and save the time it would take to find tricky data errors.
The book shows you how to use typing to create software that not only is safe and runs smoothly, but is also easy to maintain.
Examples of problem solving, written in TypeScript, will help you develop your skills in working with types, from simple data types to more complex concepts such as functors and monads.
In this book:
- Creation of data structures based on simple types, arrays and references.
- Object oriented programming and types.
- Using generics and higher-order types.
This book requires experience with one of the mainstream programming languages such as TypeScript, Java, JavaScript, C #, or C ++.
Who is this book for
The book is intended for practicing programmers. The reader should be good at writing code in one of the programming languages such as Java, C #, C ++, or JavaScript / TypeScript. Code examples are in TypeScript, but most of the material is applicable to any programming language. In fact, the examples do not always use typical TypeScript. Whenever possible, they have adapted so that programmers in other programming languages can understand them. The assembly of code examples is described in Appendix A, and a short TypeScript cheat sheet is described in Appendix B.
If you are involved in object-oriented code development for work, you may have heard about algebraic data types (ADTs), lambda expressions, generics, functors, monads and want to better understand what these are. and how to use them in your work.
This book will show you how to use the type system of a programming language to design less error-prone, more modular, and understandable code. You will see how to turn runtime errors that can crash the entire system into compilation errors and catch them before they get in trouble.
The bulk of the literature on type systems is highly formalized. The book focuses on practical applications of type systems; therefore there is very little mathematics in it. However, it is advisable that you have an understanding of basic algebra concepts such as functions and sets. This is needed to clarify some of the concepts we need.
Generalized Algorithms and Interators
In this chapter
- Using map (), filter (), and reduce () operations isn't just for arrays.
- Solving a wide range of problems using a set of common algorithms.
- Provide generic datatype support for the desired contract.
- Implementation of a variety of algorithms using different categories of iterators.
- Implementation of adaptive algorithms.
This chapter focuses entirely on generic, reusable algorithms suitable for a wide variety of data types and structures.
We looked at one version of each of the map (), filter (), and reduce () operations in Chapter 5 when we discussed higher-order functions. These functions work with arrays, but as we've seen in previous chapters, iterators are a great abstraction for working with any data structure. We will start by implementing generic versions of the above three algorithms that work with iterators, and therefore are applicable to processing binary trees, lists, arrays, and any other iterable data structure.
The map (), filter () and reduce () operations are not unique. We'll talk about other generic algorithms and algorithm libraries available in most modern programming languages. We will see why it is better to replace most of the loops with calls to library algorithms. We'll also talk a little about fluid APIs and user-friendly algorithms interfaces.
Next, we'll go over the constraints of parameter types; generic data structures and algorithms can specify the capabilities that must be present in their parameter types. This specialization leads to somewhat less versatile data structures and algorithms that are no longer usable everywhere.
We'll go into more detail about iterators and talk about their different categories. The more specialized an iterator is, the more efficient algorithms are possible with its participation. However, not all data structures are capable of supporting specialized iterators.
Finally, we'll take a quick look at adaptive algorithms. They allow for more versatile but less efficient implementations for iterators with fewer features and more efficient but less versatile implementations for iterators with more features.
10.1. Improved map (), filter () and reduce () operations
In Chapter 5, we talked about the map (), filter (), and reduce () operations and looked at one of the possible implementations of each. These algorithms are higher-order functions because they take another function as an argument and apply it to a sequence of data.
The map () operation applies a function to each element in the sequence and returns the results. The filter () operation applies a filter function to each element and returns only those for which this function returns true. The reduce () operation groups all the values in a sequence using a function and returns a single value as a result.
Our Chapter 5 implementation used the generic parameter type T, and represented sequences as arrays of T type elements.
10.1.1. Map () operation
Let's remember how we implemented the map () operation. We had two types-parameters: T and U. The function takes as an argument an array of values of type T and a function that converts from T to U as the second argument. It returns an array of U values, as shown in Listing 10.1.
Now, with our knowledge of iterators and generators, let's see in Listing 10.2 how to implement map () so that it can work with any Iterable <T>, not just arrays.
While the original implementation was limited to arrays, this one can work with any data structure that provides an iterator. In addition, the code has become much more compact.
10.1.2. Filter () operation
Let's do the same with filter () (Listing 10.3). Our original implementation expected an array of elements of type T and a predicate as input. Let me remind you that a predicate is a function that takes one element of some type and returns a boolean. If a given function returns true for a value passed to it, then the value is said to satisfy the predicate.
As with the map () operation, we'll use an Iterable <T> instead of an array and implement this Iterable as a generator that produces values that satisfy the predicate, as shown in Listing 10.4.
Again, a more laconic implementation has turned out, capable of working not only with arrays. Finally, we modify the reduce () function.
10.1.3. Reduce () operation
Our original reduce () implementation expected an array of elements of type T, an initial value of type T (in case the array was empty), and an op () operation. This operation is a function that takes two values of type T as arguments and returns one value of type T. The reduce () operation applies the operation to the initial value and the first element of the array, stores the result, applies the same operation to the result and the next element of the array, and etc. (Listing 10.5)
You can rewrite this function to use Iterable <T> instead of an array and work with any sequence, as shown in Listing 10.6. In this case, we don't need a generator. Unlike the previous two functions, reduce () does not return a sequence of elements, but a single value.
The rest of the implementation has not changed.
10.1.4. Filter () / reduce () pipeline
Let's see how to combine these algorithms into a pipeline that selects only even numbers from a binary tree and sums them up. Let's use the BinaryTreeNode <T> class from Chapter 9 with its centered tree traversal and concatenate it with an even number filter and a reduce () function that uses addition as an operation (Listing 10.7).
This example is a living proof of the effectiveness of generic types. Instead of implementing a new function for traversing a binary tree and summing even numbers, we simply form a processing pipeline specifically for the desired scenario.
10.1.5. Exercises
- Create a pipeline to handle an iterable of type string: the concatenation of all non-empty strings.
- Create a pipeline to process an iterable of type number: picking all odd numbers and squaring them.
10.2. Common algorithms
We discussed the map (), filter (), and reduce () algorithms, and also mentioned take () in Chapter 9. Many other algorithms are often used in pipelines. I will list some of them. We're not going to look at implementations - I'll just describe what arguments (besides Iterable) they receive and how they process the data. In addition, I will list the various names these algorithms can be referred to:
- map () takes as input a sequence of values of type T and a function (value: T) => U, and returns a sequence of values of type U after applying this function to all values of the input sequence. It also appears under the names 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, , .
There are many other algorithms for sorting, reversing, splitting, and concatenating sequences. Fortunately, these algorithms are so useful and applicable in so many areas that you don't need to implement them yourself. For most programming languages, there are libraries with ready-made implementations. JavaScript has packages underscore.js and lodash, each with many similar algorithms. (At the time of this writing, these libraries do not support iterators — only the built-in JavaScript array and object types.) In Java, they can be found in the java.util.stream package. In C #, they are located in the System.Linq namespace. In C ++, in the header file of the standard library <algrithm>.
10.2.1. Algorithms instead of loops
You might be surprised, but there is a good rule of thumb: whenever you write an algorithm, check to see if there is a library algorithm or pipeline for the task. Loops are usually written to process sequences — exactly what the algorithms discussed above do.
Library algorithms are preferred over custom loops because there is less chance of error. Library algorithms are proven and efficiently implemented, and can be used to make code more readable by explicitly specifying operations.
We've looked at several implementations in this book to better understand the internals, but you rarely need to implement the algorithms yourself. If you come across a task that is beyond the power of existing algorithms, it is better to create a generic, reusable implementation than a one-off, specialized one.
10.2.2. Implementing a fluid pipeline
Most libraries provide a fluid API for pipelining algorithms. Fluid APIs are chained APIs that make your code much easier to read. Let's see the difference between a fluid API and a non-fluid API using the filter / convolution pipeline from Section 10.1.4 (Listing 10.8) as an example.
And although we first apply the filter () operation and then pass the result to the reduce () operation, when we read the code from left to right, we will see reduce () before filter (). It is also quite difficult to figure out which arguments refer to a particular function in a pipeline. The fluid API makes your code a lot easier to read.
Currently, all of our algorithms take an iterable object as the first argument and return an iterator. Object-oriented programming will improve our API. It is possible to collect all our algorithms into an iterable wrapper class. And then call any of the iterables without explicitly specifying it as the first argument, because now the iterable is a member of the class. We'll do this for map (), filter (), and reduce (), grouping them into a new FluentIterable <T> class that wraps an Iterable object, as shown in Listing 10.9.
Based on the Iterable <T>, we can create a FluentIterable <T>, so we can rewrite our filter / reduce pipeline to be more fluid. Let's create a FluentIterable <T> object, call filter () on it, create a new FluentIterable <T> object based on its results, and call reduce () on it, as shown in Listing 10.10.
Now filter () comes before reduce (), and it's pretty clear that the arguments refer to this function. The only problem is the need to create a new FluentIterable <T> after each function call. You can improve this API by rewriting the map () and filter () functions to return a FluentIterable <T> instead of an IterableIterator <T>. Note that you don't need to change the reduce () method because reduce () returns a single value of type T, not an iterable.
But since we are using generators, we cannot simply change the return type. The raison d'être of generators is to provide a convenient syntax for functions, but they always return an IterableIterator <T>. Instead, we can move the implementations into two private methods, mapImpl () and filterImpl (), and convert from IterableIterator <T> to FluentIterable <T> in the public map () and filter () methods, as shown in Listing 10.11.
This improved implementation makes it easier to chain algorithms because they all now return a FluentIterable in which all algorithms are described as methods, as shown in Listing 10.12.
Now, in this truly fluid version, the code is easy to read from left to right, and the syntax for concatenating an arbitrary number of algorithms that make up the pipeline looks quite natural. A similar approach is used in most algorithmic libraries, making it as easy as possible to chaining multiple algorithms.
Depending on the programming language, one of the drawbacks of Fluent APIs is cluttering the FluentIterable class with methods for all algorithms, making it harder to extend. If it is included in the library, then the calling code has no way to add a new algorithm without modifying the class. C # has so-called extension methods that allow you to add methods to a class or interface without having to modify its code. However, not all languages have such features. Nevertheless, in most cases it is better to use an existing library of algorithms rather than implement a new one from scratch.
10.2.3. Exercises
- Extend the FluentIterable class to include a take () algorithm that returns the first n elements from the iterator.
- Extend the FluentIterable class to include a drop () algorithm that skips the first n elements from the iterator and returns all the rest.
10.3. Limiting parameter types
We have already seen how generic data structures define a form of data that does not depend on a particular type parameter T. We also looked at a set of algorithms that use iterators to process sequences of values of type T, regardless of which type it is. Now, in Listing 10.13, consider a scenario where a particular data type is important: a generic function renderAll () that takes an Iterable <T> as an argument and calls render () on each element returned by the iterator.
Attempting to compile this function ends up with the following error message: Property 'render' does not exist on type 'T' (type 'T' is missing the 'render' property).
We are trying to call the render () method of a generic type T, which may not have such a method. In such a scenario, you would need to restrict type T to only the specific incarnations that contain the render () method.
Limitations of parameter types
Constraints tell the compiler about the capabilities that an argument type must have. Without restrictions, the argument type can be anything. When it is required that a generic data type has certain class members, it is with the help of constraints that we reduce the set of allowed types to those that have these required members.
In our case, we can define the IRenderable interface, which declares the render () method, as shown in Listing 10.14. You can then add a constraint on the type of T using the extends keyword to tell the compiler that only argument types that embody IRenderable are allowed.
10.3.1. Restricted Generic Data Structures
Most generic data structures do not require parameter type constraints. Any type of value can be stored in a linked list, tree, and array. However, there are a few exceptions, in particular the hashed set.
The set data structure models the set in a mathematical sense, so unique values are stored in it and duplicates are discarded. Set data structures typically include methods for joining, intersecting, and subtracting from other sets, and also allowing you to check if a given value is included in a set. To do this, you can compare this value with each of the elements in the set, although this is not a very efficient approach. In the worst case, comparison with each of the elements of the set requires traversing the entire set. Such a traversal is performed in linear time, O (n). You can brush up on these notations in the sidebar “Big O Notation,” below.
The most efficient implementation is to hash all values and store them in a key-value data structure such as a hash map or dictionary. Structures like these are more efficient, they can retrieve values in constant time , O (1). The hashed set wraps the hash map, providing an efficient check for the inclusion of an element. But it has a limitation: type T must provide a hash function that takes a value of type T and returns its hash value of type number.
In some programming languages, hashing of all values is possible by describing the hashing method in the higher type. For example, the higher Java Object type includes a hashCode () method, and the higher C # Object type includes the GetHashCode () method. But if the language does not provide such a possibility, then a type constraint is necessary so that only types that can be hashed can be stored in our data structures. For example, we can define the IHashable interface and use it as a type constraint on the key type of our generic hashmap or dictionary.
about the author
Vlad Rishkutsia is a software development specialist at Microsoft with over ten years of experience. During this time, he managed several major software projects and trained many young professionals.
More details about the book can be found on the website of the publishing house
» Table of Contents
» Excerpt
For Habitants a 25% discount on coupon - TypeScript
Upon payment for the paper version of the book, an e-book is sent by e-mail.