Привет, Хаброжители! Причиной многих программных ошибок становится несоответствие типов данных. Сильная система типов позволяет избежать целого класса ошибок и обеспечить целостность данных в рамках всего приложения. Разработчик, научившись мастерски использовать типы в повседневной практике, будет создавать более качественный код, а также сэкономит время, которое потребовалось бы для выискивания каверзных ошибок, связанных с данными.В книге рассказывается, как с помощью типизации создавать программное обеспечение, которое не только было бы безопасным и работало без сбоев, но также обеспечивало простоту в сопровождении.
Примеры решения задач, написанные на 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).
Этот пример — живое подтверждение эффективности обобщенных типов. Вместо того чтобы реализовывать новую функцию для обхода бинарного дерева и суммирования четных чисел, мы просто формируем конвейер обработки специально для нужного сценария.
10.1.5. Упражнения
- Создайте конвейер для обработки итерируемого объекта типа string: конкатенации всех непустых строк.
- Создайте конвейер для обработки итерируемого объекта типа number: выбора всех нечетных чисел и возведения их в квадрат.
10.2. Распространенные алгоритмы
Мы обсудили алгоритмы map(), filter() и reduce(), а также был упомянут take() в главе 9. В конвейерах часто используются и многие другие алгоритмы. Перечислю некоторые из них. Мы не станем изучать реализации — я просто опишу, какие аргументы (помимо Iterable) они получают и как обрабатывают данные. Вдобавок я перечислю различные названия, под которыми эти алгоритмы могут встречаться:
- map() принимает на входе последовательность значений типа T и функцию (value: T) => U, а возвращает последовательность значений типа U после применения ко всем значениям входной последовательности этой функции. Она также встречается под названиями 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, по сути, склеивая две входные последовательности.
Существует множество других алгоритмов для сортировки, обращения, разбиения и конкатенации последовательностей. К счастью, эти алгоритмы настолько полезны и применимы в таком количестве областей, что реализовывать их самостоятельно не требуется. Для большинства языков программирования существуют библиотеки с готовыми реализациями. В JavaScript есть пакеты underscore.js и lodash, в каждом из которых множество подобных алгоритмов. (На момент написания данной книги эти библиотеки не поддерживали итераторы — только встроенные типы массивов и объектов JavaScript.) В Java их можно найти в пакете java.util.stream. В C# они располагаются в пространстве имен System.Linq. В C++ — в заголовочном файле стандартной библиотеки <algоrithm>.
10.2.1. Алгоритмы вместо циклов
Возможно, вы удивитесь, но есть хорошее эмпирическое правило: всякий раз, когда пишете алгоритм, проверьте, не существует ли библиотечного алгоритма или конвейера для этой задачи. Обычно циклы пишутся для обработки последовательностей — именно для того, для чего служат обсуждавшиеся выше алгоритмы.
Библиотечные алгоритмы предпочтительнее пользовательских циклов потому, что вероятность ошибки меньше. Библиотечные алгоритмы — проверенные и реализованы эффективным образом, и их применение позволяет получить более понятный код благодаря явному указанию операций.
В этой книге мы рассмотрели несколько реализаций, чтобы лучше понять внутренние механизмы, но реализовывать алгоритмы самостоятельно приходится редко. Если вам встретится задача, которая не под силу существующим алгоритмам, то лучше создать обобщенную, повторно используемую реализацию, чем одноразовую специализированную.
10.2.2. Реализация текучего конвейера
Большинство библиотек предоставляют текучий API для объединения алгоритмов в конвейер. Текучие API — это API, в основе которых лежит сцепление, значительно упрощающее чтение кода. Посмотрим на разницу между текучим и нетекучим API на примере конвейера фильтрации/свертки из раздела 10.1.4 (листинг 10.8).
И хоть мы сначала применяем операцию filter() и затем передаем результат в операцию reduce(), при чтении кода слева направо увидим reduce() перед filter(). Кроме того, довольно непросто разобраться, какие аргументы относятся к той или иной функции в конвейере. Текучий API намного облегчает чтение кода.
В настоящее время все наши алгоритмы принимают как первый аргумент объект итерируемого типа и возвращают итератор. Объектно-ориентированное программирование позволит усовершенствовать наш API. Можно собрать все наши алгоритмы в класс-обертку для итерируемого объекта. А затем вызывать любой из итерируемых объектов без явного указания его в качестве первого аргумента, ведь теперь итерируемый объект является членом класса. Проделаем это для map(), filter() и reduce(), сгруппировав их в новый класс FluentIterable<Т>, служащий оберткой для объекта Iterable, как показано в листинге 10.9.
На основе Iterable<Т> можно создать FluentIterable<Т>, поэтому мы можем переписать наш конвейер filter/reduce в более текучем виде. Создадим объект FluentIterable<Т>, вызовем для него filter(), создадим на основе результатов его работы новый объект FluentIterable<Т> и вызовем для него reduce(), как показано в листинге 10.10.
Теперь filter() встречается перед reduce(), и совершенно ясно, что аргументы относятся к этой функции. Единственная проблема состоит в необходимости создавать новый объект FluentIterable<Т> после каждого вызова функции. Можно усовершенствовать данный API, если переписать функции map() и filter() так, чтобы они возвращали FluentIterable<Т> вместо IterableIterator<Т>. Обратите внимание: менять метод reduce() не требуется, поскольку reduce() возвращает единственное значение типа T, а не итерируемый объект.
Но поскольку мы используем генераторы, то просто поменять возвращаемый тип нельзя. Смысл существования генераторов состоит в том, чтобы обеспечивать удобный синтаксис для функций, но они всегда возвращают IterableIterator<Т>. Вместо этого мы можем перенести реализации в два приватных метода: mapImpl() и filterImpl() — и производить преобразование из IterableIterator<Т> в FluentIterable<Т> в публичных методах map() и filter(), как показано в листинге 10.11.
Благодаря этой усовершенствованной реализации становится удобнее сцеплять алгоритмы, поскольку они все теперь возвращают FluentIterable, в котором все алгоритмы описаны в виде методов, как показано в листинге 10.12.
Теперь в этом по-настоящему текучем варианте код легко читается слева направо, и синтаксис сцепления произвольного количества составляющих конвейер алгоритмов выглядит вполне естественно. Подобный подход применяется в большинстве библиотек алгоритмов, максимально упрощая сцепление нескольких алгоритмов.
В зависимости от языка программирования один из недостатков текучих API — загромождение класса FluentIterable методами для всех алгоритмов, что усложняет его расширение. Если он включен в библиотеку, то у вызывающего кода нет возможности добавить новый алгоритм без модификации класса. В C# существуют так называемые методы расширения (extension methods), которые позволяют добавлять в класс или интерфейс методы, не прибегая к модификации его кода. Впрочем, не во всех языках присутствуют подобные возможности. Тем не менее в большинстве случаев лучше использовать уже существующую библиотеку алгоритмов, а не реализовывать новую с нуля.
10.2.3. Упражнения
- Расширьте класс FluentIterable, добавив в него алгоритм take(), возвращающий первые n элементов из итератора.
- Расширьте класс FluentIterable, добавив в него алгоритм drop(), пропускающий первые n элементов из итератора и возвращающий все остальные.
10.3. Ограничение типов-параметров
Мы уже видели, как обобщенные структуры данных задают форму данных, не зависящую от конкретного типа-параметра T. Мы также рассмотрели набор алгоритмов, использующих итераторы для обработки последовательностей значений типа T, вне зависимости от того, какой конкретно это тип. Теперь в листинге 10.13 рассмотрим сценарий, при котором конкретный тип данных важен: обобщенную функцию renderAll(), принимающую в качестве аргумента Iterable<Т> и вызывающую метод render() для каждого возвращаемого итератором элемента.
Попытка компиляции этой функции завершается следующим сообщением об ошибке: Property 'render' does not exist on type 'T' (в типе 'T' отсутствует свойство 'render').
Мы пытаемся вызвать метод render() обобщенного типа T, в котором такого метода может и не быть. При подобном сценарии необходимо ограничить тип T исключительно конкретными воплощениями, содержащими метод render().
Ограничения типов-параметров
Ограничения сообщают компилятору о возможностях, которые обязательно должны быть у типа-аргумента. Без ограничений тип-аргумент может быть любым. Когда требуется наличие у обобщенного типа данных определенных членов класса, именно с помощью ограничений мы сокращаем множество допустимых типов до тех, в которых есть эти требуемые члены.
В нашем случае можно описать интерфейс IRenderable, в котором объявлен метод render(), как показано в листинге 10.14. Далее можно добавить ограничение на тип T с помощью ключевого слова extends, указав тем самым компилятору, что допустимы только типы-аргументы, воплощающие IRenderable.
10.3.1. Обобщенные структуры данных с ограничениями типа
Для большинства обобщенных структур данных не требуется ограничение типов-параметров. В связном списке, дереве и массиве можно хранить значения любого типа. Однако существует несколько исключений, в частности хешированное множество.
Структура данных множества моделирует множество в математическом смысле, поэтому в нем хранятся уникальные значения, а дубликаты отбрасываются. Структуры данных множества обычно включают методы для объединения, пересечения и вычитания из других множеств, а также позволяют проверять, включено ли заданное значение в множество. Чтобы выполнить подобную проверку, можно сравнить это значение с каждым из элементов множества, хоть это не слишком эффективный подход. В худшем случае сравнение с каждым из элементов множества требует обхода всего множества. Подобный обход выполняется за линейное время, O(n). Освежить знания об этих обозначениях вы можете во врезке «Нотация O большое» далее.
Наиболее эффективная реализация — хеширование всех значений и хранение их в структуре данных «ключ — значение», например в хеш-карте или словаре. Подобные структуры более эффективны, они могут извлекать значения за константное время, O(1). Хешированное множество служит оберткой для хеш-карты, обеспечивая эффективную проверку на включение элемента. Но у него есть ограничение: тип T должен предоставлять хеш-функцию, принимающую значение типа T и возвращающую его хеш-значение типа number.
В некоторых языках программирования хеширование всех значений осуществимо за счет описания метода хеширования в высшем типе. Например, высший тип Java Object включает метод hashCode(), а высший тип C# Object включает метод GetHashCode(). Но если язык не предоставляет подобной возможности, то необходимо ограничение типа, чтобы в наших структурах данных могли храниться только типы, допускающие хеширование. Например, можно описать интерфейс IHashable и воспользоваться им в качестве ограничения типа для типа ключей наших обобщенных хеш-карты или словаря.
Об авторе
Влад Ришкуция — специалист по разработке ПО в Microsoft, имеет более чем десятилетний опыт. За это время он руководил несколькими крупными программными проектами и обучил множество молодых специалистов.
Более подробно с книгой можно ознакомиться на сайте издательства
» Оглавление
» Отрывок
Для Хаброжителей скидка 25% по купону — TypeScript
По факту оплаты бумажной версии книги на e-mail высылается электронная книга.
