Новости

Разработчик, научившись мастерски использовать типы в повседневной практике, будет создавать более качественный код, а также сэкономит время, которое потребовалось бы для выискивания каверзных ошибок, связанных с данными.

В книге рассказывается, как с помощью типизации создавать программное обеспечение, которое не только было бы безопасным и работало без сбоев, но также обеспечивало простоту в сопровождении.

Примеры решения задач, написанные на TypeScript, помогут развить ваши навыки работы с типами, начиная от простых типов данных и заканчивая более сложными понятиями, такими как функторы и монады.

В этой книге:

• Создание структур данных на основе простых типов, массивов и ссылок.
• Объектно-ориентированное программирование и типы.
• Использование дженериков и типов высшего порядка.

Для работы с книгой требуется опыт работы с одним из мейнстримовых языков программирования, например TypeScript, Java, JavaScript, C# или C++.

Для кого эта книга

Книга предназначена для программистов-практиков. Читатель должен хорошо уметь писать код на одном из таких языков программирования, как Java, C#, C++ или JavaScript/TypeScript. Примеры кода приведены на языке TypeScript, но большая часть излагаемого материала применима к любому языку программирования. На самом деле в примерах далеко не всегда используется характерный TypeScript. По возможности они адаптировались так, чтобы их понимали программисты на других языках программирования. Сборка примеров кода описана в приложении A, а краткая «шпаргалка» по языку TypeScript — в приложении Б.

Если вы по работе занимаетесь разработкой объектно-ориентированного кода, то, возможно, слышали об алгебраических типах данных (algebraic data type, ADT), лямбда-выражениях, обобщенных типах данных (generics), функторах, монадах и хотите лучше разобраться, что это такое и как их использовать в своей работе.

Эта книга расскажет, как использовать систему типов языка программирования для проектирования менее подверженного ошибкам, более модульного и понятного кода. Вы увидите, как превратить ошибки времени выполнения, которые могут привести к отказу всей системы, в ошибки компиляции и перехватить их, пока они еще не натворили бед.

Основная часть литературы по системам типов сильно формализована. Книга же сосредотачивает внимание на практических приложениях систем типов; поэтому математики в ней очень мало. Тем не менее желательно, чтобы вы имели представление об основных понятиях алгебры, таких как функции и множества. Это понадобится для пояснения некоторых из нужных нам понятий.

Обобщенные алгоритмы и интераторы

В этой главе

• Использование операций map(), filter() и reduce() не только для массивов.

• Решение широкого спектра задач с помощью набора распространенных алгоритмов.

• Обеспечение поддержки обобщенным типом данных нужного контракта.

• Реализация разнообразных алгоритмов с помощью различных категорий итераторов.

• Реализация адаптивных алгоритмов.

Эта глава всецело посвящена обобщенным алгоритмам, пригодным для повторного использования, подходящим для разнообразных типов и структур данных.

Мы рассмотрели по одной версии каждой из операций map(), filter() и reduce() в главе 5, когда обсуждали функции высшего порядка. Эти функции работают с массивами, но, как мы видели в предыдущих главах, итераторы — прекрасная абстракция для работы с любой структурой данных. Мы начнем с реализации обобщенных версий трех вышеупомянутых алгоритмов, работающих с итераторами, а значит, применимых для обработки бинарных деревьев, списков, массивов и любых других итерируемых структур данных.

Операции map(), filter() и reduce() не единственные в своем роде. Мы поговорим и о других обобщенных алгоритмах и библиотеках алгоритмов, доступных в большинстве современных языков программирования. Мы увидим, почему лучше заменить большинство циклов вызовами библиотечных алгоритмов. Мы также немного поговорим о текучих API и удобных для пользователя интерфейсах алгоритмов.

Далее мы пройдемся по ограничениям типов-параметров; обобщенные структуры данных и алгоритмы могут задавать возможности, которые должны присутствовать в их типах-параметрах. Подобная специализация приводит к несколько менее универсальным структурам данных и алгоритмам, пригодным к использованию уже не везде.

Мы подробнее обсудим итераторы и поговорим об их различных категориях. Чем уже специализирован итератор, тем более эффективные алгоритмы возможны с его участием. Впрочем, не все структуры данных способны поддерживать специализированные итераторы.

Наконец, мы коротко пробежимся по адаптивным алгоритмам. Они позволяют создавать более универсальные, но менее эффективные реализации для итераторов, обладающих меньшим количеством возможностей, и более эффективные, но менее универсальные реализации для итераторов с большим количеством возможностей.

10.1. Улучшенные операции map(), filter() и reduce()

В главе 5 мы говорили об операциях map(), filter() и reduce() и рассмотрели одну из возможных реализаций каждой из них. Эти алгоритмы представляют собой функции высшего порядка, поскольку принимают в качестве аргумента другую функцию, применяя ее к последовательности данных.

Операция map() применяет функцию к каждому элементу последовательности и возвращает результаты. Операция filter() применяет функцию фильтрации к каждому элементу и возвращает только те из них, для которых эта функция вернула true. Операция reduce() группирует все значения в последовательности с помощью функции и возвращает в виде результата одно значение.

В нашей реализации из главы 5 использовался обобщенный тип-параметр T, а последовательности были представлены в виде массивов элементов типа T.

10.1.1. Операция map()

Вспомним, как мы реализовали операцию map(). У нас было два типа-параметра: T и U. Функция принимает как аргумент массив значений типа T и функцию, переводящую из T в U в качестве второго аргумента. Она возвращает массив значений типа U, как показано в листинге 10.1.

Теперь, воспользовавшись нашими знаниями об итераторах и генераторах, посмотрим в листинге 10.2, как реализовать map() так, чтобы она могла работать с любым Iterable<Т>, а не только c массивами.

В то время как область действия первоначальной реализации ограничивалась массивами, эта может работать с любой структурой данных, предоставляющей итератор. Кроме того, код стал намного компактнее.

10.1.2. Операция filter()

Проделаем то же самое с filter() (листинг 10.3). Наша исходная реализация ожидала на входе массив элементов типа T и предикат. Напомню, что предикат — это функция, принимающая один элемент какого-то типа и возвращающая boolean. Если данная функция возвращает true для переданного ей значения, то говорят, что значение удовлетворяет предикату.

Как и в случае с операцией map(), мы воспользуемся Iterable<Т> вместо массива и реализуем этот Iterable в виде генератора, выдающего значения, удовлетворяющие предикату, как показано в листинге 10.4.

Опять получилась более лаконичная реализация, способная работать не только с массивами. И наконец, модифицируем функцию reduce().

10.1.3. Операция reduce()

Наша первоначальная реализация reduce() ожидала на входе массив элементов типа T, начальное значение типа T (на случай, если массив окажется пуст) и операцию op(). Эта операция представляет собой функцию, которая принимает в качестве аргументов два значения типа T и возвращает одно значение типа T. Операция reduce() применяет операцию к начальному значению и первому элементу массива, сохраняет результат, применяет ту же операцию к результату и следующему элементу массива и т. д. (листинг 10.5)

Эту функцию можно переписать так, чтобы вместо массива использовался Iterable<Т> и она могла работать с любой последовательностью, как показано в листинге 10.6. В данном случае генератор нам не нужен. В отличие от двух предыдущих функций, reduce() возвращает не последовательность элементов, а одно значение.

Остальная часть реализации не поменялась.

10.1.4. Конвейер filter()/reduce()

Посмотрим, как объединить эти алгоритмы в конвейер, выбирающий из бинарного дерева только четные числа и суммирующий их. Воспользуемся классом BinaryTreeNode<Т> из главы 9 с его центрированным обходом дерева и сцепим его с фильтром четных чисел и функцией reduce(), в которой в качестве операции применяется сложение (листинг 10.7).

Этот пример — живое подтверждение эффективности обобщенных типов. Вместо того чтобы реализовывать новую функцию для обхода бинарного дерева и суммирования четных чисел, мы просто формируем конвейер обработки специально для нужного сценария.

С полным содержанием статьи можно ознакомиться на сайте "Хабрахабр":

https://habr.com/ru/company/piter/blog/554652/