Краткое содержание

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

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

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

Алгебраические типы данных

АТД получили свое название от двух фактов.

  1. В отличие от функтора (типа «обертки») или типа «интерфейса» (трейты, интерфейсы, абстрактные базовые классы — есть много названий для одного и того же)… По сути, тип данных — это любой тип, который просто данные! Он настолько прост, что трудно признать необходимость дать ему имя. Но это красивое имя, поэтому, пожалуйста, примите его.
  2. Алгебраический — потому что количество значений, которое может принимать АТД, представляет собой алгебраическое выражение, основанное на составляющих его типах.

Структура — это «тип продукта», потому что количество значений, которые может принимать структура, является произведением значений ее составляющих. Логическое значение может быть 2 значения. Структура с 10 логическими значениями может содержать 2¹⁰ значений.

std::variant (или объединение) (или перечисление в rust) — это «суммарный тип», потому что количество значений, которые он может принимать, равно, как вы уже догадались, сумме значений его составляющих. std::variant с 10 логическими значениями может быть 20 значений. Первое логическое значение может быть активным и может быть включено или выключено. Второе логическое значение может быть активным значением, оно может быть включено или выключено и т. д. Конечно, представление объединения в стиле C в терминах битов может быть таким же маленьким, как и самая большая составляющая. Но размеченный союз, который сохраняет тракт, какая составляющая активна (как это делает std::variant или rust enum), не поддается такого рода путанице.

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

Доказательство функций в виде экспоненциального АТД

Предполагая 2 возможных входа и 3 возможных выхода, вы можете разделять и властвовать. Дважды решите следующую задачу: у вас есть 1 возможный вход и 3 возможных выхода.

Давайте решим это: учитывая, что есть только один возможный аргумент (скажем, значение «истина»), то явно есть 3 уникальных способа написать эту функцию:

{правда: 0}, {правда: 1}, {правда: 2}

Давайте решим задачу и для другого значения аргумента:

{ложь: 0}, {ложь: 1}, {ложь: 2}

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

Уникальная функция, которая может иметь либо true, либо false в качестве аргумента, фактически будет любым из возможных декартовых произведений этих двух наборов:

{правда: 0, ложь: 0}, {правда: 0, ложь: 1}, …, {правда: 2, ложь: 1}, {правда: 2, ложь: 2}.

Написанное таким образом, становится ясно, что существует 3² возможных типов. Другими словами, вы получаете «одну цифру на |тип ввода|». и «каждая цифра может быть |типом вывода| разные ценности».

Еще один пример

Допустим, есть функция «enum_to_bool», где на входе может быть 3 значения, а на выходе может быть 2 значения. Сколько типов мы получаем тогда? 2³=8. Я напишу 8 функций, которые учитывают эту сигнатуру, затем карту, которой они соответствуют.

just_true = {0: правда, 1: правда, 2: правда},

made_the_finals = {0: правда, 1: правда, 2: ложь},

is_not_middle_child = {0: правда, 1: ложь, 2: правда},

if_your_not_first_your_last = {0: правда, 1: ложь, 2: ложь},

successful_in_horseshoes_and_hand_grenades = {0: ложь, 1: правда, 2: правда},

is_middle_child = {0: ложь, 1: правда, 2: ложь},

slept_in_today = {0: ложь, 1: ложь, 2: истина},

always_false = {0: ложь, 1: ложь, 2: ложь},

Переговоры

CppCon 2016: Бен Дин «Эффективное использование типов»

"связь"

Это 55-минутное видео, подробно описывающее то, о чем говорится в заголовке. К преимуществам типов относятся компиляторы, проверяющие корректность нашего кода, и система типов, делающая недопустимое состояние непредставимым.

Эффективный ОД

"связь"

69-минутная лекция инженера с Джейн Стрит, прочитанная для введения в курс компьютерных наук в Гарварде в 2010 году. К ней прилагается сообщение в блоге, и именно здесь я действительно укрепил свое понимание алгебраической части алгебраических типов данных https://blog.janestreet.com/efficient-ml-revisited/

История

Низкий ключ, это просто моя болтовня. В любом случае.

Типы — очень полезная вещь в программировании. Сначала они использовались, чтобы различать, какие инструкции по сборке следует создавать. Мы можем сделать «add», чтобы добавить целые числа, или «fadd», чтобы добавить числа с плавающей запятой. Что ж, программирование развивалось со времен раннего C, и теперь типы могут делать больше. Тем не менее, многие языки и программисты до сих пор рассматривают типы через призму старой школы. Это естественно, это то, с чем мы выросли. Но это не то, на что мы должны соглашаться. Концепция «типов» может сделать для нас больше.

Мы начали получать эту мощь с помощью классики C, такой как «size_t» или «addr_t». Но эти специальные типы и структуры — это только начало. Объектно-ориентированные классы, определяющие типы, являются логическим следующим шагом — ЭТИ типы не просто имеют значения, но и имеют функции, позволяющие легко выполнять с ними полезную работу. На самом деле функции-члены — это просто синтаксический сахар: myObj.myFxn(myArg) эквивалентно myFxn(myObj, myArg). Но, эй, ООП легко мыслить в терминах, и я большой поклонник «нотаций как инструмента мышления», так что если синтаксис помогает, то он помогает.

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

Но нас беспокоит не аппаратное обеспечение, а программное обеспечение. Чисто математическое представление «какой сегодня день недели» в диапазоне от 1 до ²³² просто не имеет никакого смысла. Вместо этого вы должны использовать тип, содержащий ровно 7 типов. Вы знаете, как это сделать на C++?

Перечисление, конечно! Просто создайте перечисление с 7 значениями, и все готово. Преимущество перечислимого типа перед целочисленным: если вы хотите написать ветку кода для каждого дня недели, компилятор узнает, если вы этого не сделали. Принимая во внимание, что компилятор не имеет представления о числе 7 как о магическом числе случаев, когда вы используете целое число. Попробуйте объяснить, что, КОНЕЧНО, нет смысла иметь 8 wochentags тому, кто не знает, что «wochentag» — это немецкое слово, означающее «день недели» (я использовал гугл-переводчик, поэтому не знаю, насколько это точно, лол). ).

В любом случае. Вы можете использовать перечисление в C++, чтобы получить тип с правильным количеством значений. Но что, если у вас есть число больше 7? Как бы вы создали тип, который имеет ²³²*²¹⁶ значений. Или тип со значениями ²⁶⁴+1. В первом случае это будет тип с именем ip_and_port, а во втором случае — pointer_but_maybe_fail или std::optional<int*>. Здесь мы вступаем в мир алгебраических типов данных.