Если вы пришли с мира ООП, то одной наиболее сложной вещью в функциональном программировании для вас может быть отсутствие явных шаблонов программирования. Здесь множество идиом типа частичного применения и техник обработки ошибок, но нет очевидных шаблонов как в "Банде четырёх".
В этом посте мы рассмотрим довольно распространенный "шаблон" известный как моноид. Строго говоря, моноид это не шаблон проектирования, а скорее подход, одинаково работающий с разными типами данных. Фактически, если вы разберетесь с моноидом, вы будете видеть его везде!
К сожалению, термин "моноид" сам по себе немного отталкивающий. Он изначально пришел с математики, но концепция применима к программированию, даже без знания математики, и я вам это продемонстрирую.
Честно говоря, если бы мы давали имя концепту сегодня, мы бы его назвали что-то типа ICombinable, а не такого пугающего как моноид.
И на конец, вы можете подумать что "моноид" как нибудь связан с "монадами". Да, у них есть математическая связь, но в программировании это очень разные вещи, несмотря на похожие имена.
Ох... уравнения.
В основном на этом сайте я не использую математику, но в этом случае я должен нарушить свое правило и показать несколько уравнений.
Готовы? Держите первое:
1 + 2 = 3
Смогли разобраться? А еще с одним?
1 + (2 + 3) = (1 + 2) + 3
и на конец...
1 + 0 = 1 и 0 + 1 = 1
Все. Готово. Если вы можете понять эти уравнения, тогда у вас есть все знания для того чтоб понять моноид.
Мышление как в математика
"Творчество математика в такой же степени есть создание прекрасного, как творчество живописца или поэта, – совокупность идей, подобно совокупности красок или слов, должна обладать внутренней гармонией.."
Большая часть людей представляют себе, что математики работают с числами, делая сложную арифметику или расчеты.
Это заблуждение. Например, если вы посмотрите на обычный высший уровень разговоров математиков, вы увидите множество странных слов, букв и символов, но не увидите арифметики.
Одна вещь, которую делают математики - попытки найти шаблоны в сущностях. "Что общее имеют эти сущности?" или "Как обобщить этот концепт?" - обычные вопросы математиков.
Поэтому давайте рассмотрим эти три уравнения глазами математика
Обобщение первого уравнения
Математик, посмотрев на 1 + 2 = 3, мог бы подумать:
- У нас есть набор чего-то (целое число в данном случае)
- И мы можем как нибудь комбинировать два из них (суммирование)
- И результатом будет третья штука (мы получили еще одно число)
Потом математик может попробовать понять, возможно ли обобщить его к другим вещам или операциям.
Давайте будем считать числа "сущностями". Как по другому можно комбинировать числа? И подходить им какой нибудь шаблон?
Давайте попробуем умножение, подходит ли?
Ответ: да, умножение подходит под этот шаблон потому что любые два числа производят третье число.
Как на счет деления? Подходит ли оно под шаблон? Ответ: нет, потому что в большинстве случаев деление двоих целых чисел производить дробь, что явно не целое число. (Я игнорирую целочисленное деление).
Как на счет функции max? Она подходит? Она комбинирует два целых числа и возвращает одно из них, поэтому ответ: да.
Как на счет функции equals? Она комбинирует два числа, но возвращает логическое значение, не число. Поэтому ответ - нет.
Хватит целых чисел. Как на счет других типов сущностей?
Вещественные числа близкие к целым, но использование деления с вещественными возвращает вещественное, поэтому операция деления подходит шаблону.
Что на счет логических? Они могут быть комбинированы операторами на подобие AND, OR и тд. Результат aBool AND aBool логический? Да! Также OR подходит к шаблону
Далее строковые значения. Как мы их можем комбинировать? Единственный путь это конкатенация (обеднение), которая возвращает другое строковое значение, собственно то, что нам и нужно. Но в то же время сравнение не подходит, потому что оно возвращает логическое значение.
Ну и наконец, рассмотрим списки. Как и для строк, обычный способ их комбинировать это конкатенация, которая возвращает новый список, который подходит к нашему шаблону.
Мы можем продолжить с подобные способы комбинаций, но вы уже должны были понять как это работает.
Вы можете спросить: почему так важно, чтоб операция над чем-то возвращала результат того самого типа? Ответ в том, что вы можете строить цепочки из множества объектов используя эту операцию.
Например, так как 1 + 2 это другое число, вы можете добавить к нему 3. А так как 1 + 2 + 3 так же число, вы можете продолжить добавлять скажем 4 к результату. Другими словами только потому, что суммирование целых чисел подходит к нашему шаблону, мы можем писать последовательности суммирования, подобные: 1 + 2 + 3 + 4. Вы не можете написать 1 = 2 = 3 = 4, потому что сравнение числовых значений не соответствует шаблону.
И, конечно, же цепочка комбинаций из чисел может быть длинной насколько мы захотим. Другими словами, этот шаблон позволяет нам расширить попарную операцию в операцию которая работает с списками.
Математики называют это требование (когда "результат имеет тот же тип что и операнды) - замкнутостью.
Обобщение второго уравнения
Хорошо, что например о следующем уравнении: 1 + (2 + 3) = (1 + 2) + 3? Почему оно так важно?
Ну, если вы вспомните первый шаблон, то он говорит, что мы можем объединять в цепочки операции, подобные 1 + 2 + 3. Но на самом деле мы получили только попарную операцию. Тогда в каком порядке мы должны их комбинировать? Должны скомбинировать сначала 1 и 2, а потом результат с 3. Или сначала 2 с 3, а потом с 1? И вообще есть ли разница?
Вот почему полезное второе уравнение. Оно говорит, что порядок суммирования не имеет значения. Вы получите тот самый результат в любом случае.
Поэтому, в цепочке с четырех чисел 1 + 2 + 3 + 4, мы можем начать работать с лева: ((1+2) + 3) + 4 или с права: 1 + (2 + (3+4)), или даже сделать это парами и потом комбинировать: (1+2) + (3+4).
Рассмотрим, подходит ли шаблон к примерам, которые мы уже рассматривали.
На этот раз начнем с умножения. Результат 1 * (2 * 3) будет тот же, что и (1 * 2) * 3? Да. То же самое с суммированием, порядок не имеет значения.
Теперь попробуем вычитание. Будет ли иметь 1 - (2 - 3) тот же результат, что и (1 - 2) - 3? Нет. Для вычитания порядок имеет значение.
Как насчет деления? Будет ли 12 / (2 / 3) иметь тот же результат, что и (12 / 2) / 3? Нет, для деления также порядок имеет значение.
В то же время функция max будет работать. max( max(12,2), 3) даст тот же результат, что и max(12, max(2,3).
Как на счет строк и списков? Конкатенация подходит ли к требованиям? Как вы думаете?
Еще вопрос... Можем ли мы найти операцию для строк, которая зависит от порядка?
Хорошо, как на счет функции типа subtractChars, которая удаляет все буквы в строке справа из строки слева. Резульат subtractChars("abc","ab"). subtractChars еще как порядко-зависима, как вы видите в простом примере subtractChars("abc", subtractChars("abc","abc")) не то же самое что и subtractChars(subtractChars("abc","abc"),"abc").
Математики называют требование (порядок имеет значение) - ассоциативностью.
Важное замечание: Когда я говорю "порядок комбинации", я имею ввиду порядок, комбинируя попарно - одну пару, и потом комбинируя результат со следующим значением.
Очень важно то, что в общем последовательности чисел остаются неизменными. Это потому, что для определенных операций если вы измените последовательности чисел, то получите совсем другой результат! 1 - 2 не то же самое, что и 2 - 1 и 2 / 3 не то же самое, что и 3 / 2.
Конечно, во многих случаях порядок последовательностей не имеет значение. В конце концов, 1 + 2 это то же самое что и 2 + 1. В этом случае операции называются коммутативными.
Третье уравнение
Давайте взглянем на третье уравнение: 1 + 0 = 1.
Математик мог бы сказать: это интересно -- есть специальный вид сущности ("нуль"), который при комбинации с чем то возвращает оригинальную сущность, как-будто ничего не произошло.
Давайте еще один раз пройдемся по нашим примерам, и посмотрим, как мы можем расширить концепт "нуля" с другими операциями.
Пожалуй, начнем с умножения. Существует ли некоторое значение, на которое мы можем умножать число и получить оригинальное назад?
Конечно же да! Это число один. Для умножения число 1 это "нуль".
Как на счет max? Существует ли для не него "нуль"? Для 32 битных целых чисел, да. Комбинируя System.Int32.MinValue с любым другим 32 битным числом max, вернет другое число. Это идеально подходит под определение "нуля".
Как на счет логических значений комбинированных оператором AND? Существует ли нуль для него? Да, это значение True. Почему? Потому что True AND False = False и True AND True = True. В обоих случаях переданное значение возвращается нетронутым.
Логические значение комбинированные OR? Если ли для него нуль? Я дам возможность вам подумать.
Идем дальше, как на счет конкатенации строк? Есть ли "нуль" здесь? Да, однозначно -- это просто пустая строка
"" + "hello" = "hello"
"hello" + "" = "hello"
Ну и на конец конкатенация списков, "нуль" здесь это просто пустой список:
[] @ [1;2;3] = [1;2;3]
[1;2;3] @ [] = [1;2;3]
Вы можете заметить что значение "нуля" сильно зависит от операции, а не просто от набора сущностей. Нуль для суммирования чисел отличается от "нуля" для умножения, а также он отличный для функции max.
Математики называть этот "нуль" идентичность.
Повторение уравнений
Давайте повторим уравнения и новые обобщения в уме.
Сначала у нас было:
1 + 2 = 3
1 + (2 + 3) = (1 + 2) + 3
1 + 0 = 1 и 0 + 1 = 1
Но сейчас у нас что-то более абстрактное, набор обобщенных требований которые, могут быть применимы к разным сущностям:
- Мы начинаем с набора сущностей и возможности комбинирования двух с них одновременно.
- Правило 1 (Замкнутость): Результат комбинирования двоих сущностей всегда одна сущность.
- Правило 2 (Ассоциативность): При комбинировании более двух сущностей попарно, порядок не имеет значение.
- Правило 3 (Нейтральный элемент или идентичность): Существует специальная сущность, названая "нулем", и если "что-нибудь" с ней комбинировать, то получим это "что-нибудь" обратно.
Имея эти правила в одном месте, мы можем определить моноид. Моноид - просто система которая подчиняется всем трем правилам. Все просто!
Как я и говорил с самого начала, не дайте математике отпугнуть вас. Если бы программисты давали имя этому шаблону, то скорее бы назвали его "шаблон комбинирования", нежели "моноид". Но такова жизнь. Терминология уже широко распространенная, и мы должны ее использовать.
Обратите внимание на две части определения моноида - сущность плюс связанная операция. Моноид это не просто "набор сущностей", а "набор сущностей" и "способ их комбинирования". Например: "целые числа" не моноид, но "целые числа с суммированием" это моноид.
Полугруппы
В некоторых случаях у вас может быть система которая следует первым двум правилам, и не имеет кандидата на звание "нуля".
Например, если в вашей области существуют только положительные числа, тогда при суммировании они замкнуты и ассоциативны, но в таком случае нет положительного числа которое может быть "нулем".
Другим примером может быть скрещивание конечных списков. Они замкнуты и ассоциативны, но не существует (конечного) списка, который при скрещивании возвращает исходный не тронутым.
Этот вид систем все еще может быть полезным, и математиками он назван "полугруппой". К счастью, существует фокус который позволит конвертировать любую полугруппу в моноид (который я опишу позже).
Таблица классификации
Давайте запишем все наши примеры в одной таблице чтоб вы могли увидеть их все сразу.
| Сущности | Операции | Замкнутая? | Ассоциативная? | Идентичная? | Классификация |
|---|---|---|---|---|---|
| Int32 | Суммирование | Да | Да | 0 | Моноид |
| Int32 | Умножение | Да | Да | 1 | Моноид |
| Int32 | Вычитание | Да | Нет | 0 | Другое |
| Int32 | Max | Да | Да | Int32.MinValue | Моноид |
| Int32 | Ровность | Нет | Другое | ||
| Int32 | Меньше чем | Нет | Другое | ||
| Float | Умножение | Да | Нет | 1 | Другое |
| Float | Деление | Да (1) | Нет | 1 | Другое |
| Positive Numbers | Суммирование | Да | Да | нет идентичности | Полугруппа |
| Positive Numbers | Умножение | Да | Да | 1 | Моноид |
| Boolean | AND | Да | Да | true | Моноид |
| Boolean | OR | Да | Да | false | Моноид |
| String | Конкатенация | Да | Да | Пустая строка "" | Моноид |
| String | Равность | Нет | Другое | ||
| String | "subtractChars" | Да | Нет | Пустая строка "" | Другое |
| List | Конкатенация | Да | Да | Пустой список [] | Моноид |
| List | Пересечение | Да | Да | Нет идентичности | Полугруппа |
Существует много видов сущностей, которые можно добавить в этот список: полиномы, матрицы, распределение вероятностей и тд. Но этот пост не о них, но так как однажды поймете идею моноидов, вы увидите, что этот концепт может быть применим к множеству сущностей.
[1] В математике реальные числа не замкнуты при делении, потому что вы не можете поделить число на нуль и получить другое реальное число. Но все же с плавающими числами IEEE вы можете делить на нуль и получить корректное значение. Поэтому, числа с плавающей точкой являются замкнуты. Вот пример:
let x = 1.0/0.0 // бесконечность
let y = x * 2.0 // два раза бесконечность
let z = 2.0 / x // два поделено на бесконечность
Какая польза программисту от моноида?
Мы описали некоторые абстрактные концепты, но что хорошего может принести моноид в реальное програмирование?
Польза от замкнутости
Мы видели как правило замкнутости приносит пользу при конвертировании попарных операций в те, которые могут работать со списками или последовательностями.
Другими словами, если мы определим попарную операцию, то мы сможем ее расширить для списка "бесплатно"
Функции которые это делают обычно называются "reduce" (сокращение). Вот примеры:
| Подробно | Используя reduce | Пример на JavaScript (ES6) |
|---|---|---|
1 + 2 + 3 + 4 |
[ 1; 2; 3; 4 ] |> List.reduce (+) |
[1, 2, 3, 4].reduce((a, b) => a + b) |
1 * 2 * 3 * 4 |
[ 1; 2; 3; 4 ] |> List.reduce (*) |
[1, 2, 3, 4].reduce((a, b) => a * b) |
"a" + "b" + "c" + "d" |
[ "a"; "b"; "c"; "d" ] |> List.reduce (+) |
["a", "b", "c", "d"].reduce((a, b) => a + b) |
[1] @ [2] @ [3] @ [4] |
[ [1]; [2]; [3]; [4] ] |> List.reduce (@) |
[[1], [2], [3], [4]].reduce((a, b) => a.concat(b)) |
Вы можете видеть, что reduce можно рассматривать как операцию, вставленную между каждым элементом в списке.
Примечание: в последнем примере на вход reduce передается список списков, но на выходе получаем линейный список. Убедитесь, что вы понимаете, почему так.
Польза от ассоциативности
Если попарные комбинации можно делать в любом порядке, это открывает нам некоторые интересные возможности:
- Алгоритмы разделяй и властвуй
- Паралелизацию
- Инкремнеталзим
Это очень глубокие темы, но все же давайте бегло осмотрим их.
Алгоритмы разделяй и властвуй
Рассмотрим задачу суммирование первых 8 чисел. Как вы б ее реализовали?
Один с вариантов может быть пошаговая сума, как здесь:
let sumUpTo2 = 1 + 2
let sumUpTo3 = sumUpTo2 + 3
let sumUpTo4 = sumUpTo3 + 4
// etc
let result = sumUpTo7 + 8
Но так как суммирование можно сделать в любом порядке, мы можем реализовать требование разделяя сумы на два, как здесь:
let sum1To4 = 1 + 2 + 3 + 4
let sum5To8 = 5 + 6 + 7 + 8
let result = sum1To4 + sum5To8
далее мы можем рекурсивно разделить суммы в под-суммы. Продолжая таким образом, мы дойдем до базовых попарных операций:
let sum1To2 = 1 + 2
let sum3To4 = 3 + 4
let sum1To4 = sum1To2 + sum3To4
Подход "разделяй и властвуй" выглядит немного избыточным для простого суммирования, но вы еще увидите в будущих постах, что в паре с map, это база для некоторых хорошо известных алгоритмов агрегации.
Паралелизация
Как только мы имеем стратегию "разделяй и властвуй", она может быть легко конвертирована в параллельный алгоритм.
Например, для суммирования первых 8 числе на четырех ядерном процессоре, это может быть так:
| Ядро 1 | Ядро 2 | Ядро 3 | Ядро 4 | |
|---|---|---|---|---|
| Шаг 1 | sum12 = 1 + 2 |
sum34 = 3 + 4 |
sum56 = 5 + 6 |
sum78 = 7 + 8 |
| Шаг 2 | sum1234 = sum12 + sum34 |
sum5678 = sum56 + sum78 |
(простой) | (простой) |
| Шаг 3 | sum1234 + sum5678 |
(простой) | (простой) | (простой) |
Здесь все еще семь вычислений которые нужно сделать, но так как они делаются параллельно, мы можем их решить за три шага.
И снова, это выглядит как тривиальный пример, но большие системы как "Hadoop" состоят полностью из агрегации больших объемов данных. И если операция агрегации моноид, тогда вы, теоретически, можете масштабировать эти операции на множество машин*.
* На практике, как известно, дьявол кроется в деталях, и реальные системы работают немного по другому.
Инкрементализм
Даже если вам не нужен параллелизм, хороше дополнение моноида - инкрементальные расчеты.
Для примера: допустим вы попросили меня вычислить суму от одного до пяти. Тогда я, конечно же, дам вам ответ - пятнадцать.
Но вы можете сказать, что вы передумали, и сейчас хотите суму от одного до шести. Должен ли я суммирование начинать с начала? Нет, я могу использовать предыдущий результат и просто добавить до него шестерку. Это возможно потому что целочисленное суммирование - моноид.
Поэтому, если мне дадут выражение 1 + 2 + 3 + 4 + 5 + 6, то я могу группировать числа так, как мне нравиться. Практически, я могу суммировать инкрементально, на подобие: (1 + 2 + 3 + 4 + 5) + 6, которое сокращается к 15 + 6.
В этом примере перерасчет всей суммы с нуля не очень то и проблема. Если рассматривать примеры из жизни, например, веб-аналитику и вычисление количества посетителей за последние 30 дней. Простая реализация может вычислять числа, анализируя журнал(лог) за последние 30 дней. Более эффективный подход будет, если мы вспомним что предыдущие 29 дней не изменились, и можно обработать только один день. В результате, мы здорово с экономим на вычислениях.
Аналогично, если у вас есть 100 страничная книжка, и вы добавили одну страницу, вам не обязательно опять анализировать всю 101 страницу. Достаточно вычислить количество слов в последней странице и просуммировать с предыдущим результатом.*
- Технически это масштабирование называется моноидный гомоморфизм. Я объясню более подробно в следующем посте.
Польза от идентичности
Требование идентичности не всегда необходимо. Иметь замкнутую и ассоциативную операцию (полугруппу) достаточно для многих вещей.
Но все же, в некоторых случаях этого не достаточно. Вот некоторые из них:
- Как можно использовать
reduceна пустом списке? - Если я планирую использовать алгоритм "разделяй и властвуй", что я могу сделать, если нет ничего для "разделения"?
- Когда используя инкрементальный алгоритм, с какого значения должен начать если данных нет совсем?
У всех этих случаях нам нужно "нулевое" значение. Это позволит нам, например, сказать что пустой список это 0.
Относительно первого пункта: если нам нужно, чтоб список мог быть пустым, то мы должны заменить reduce на fold, который позволяет определить начальное значение (Конечно, fold возможно использовать не только для операций над моноидами).
reduce и fold в действии:
// хорошо
[1..10] |> List.reduce (+)
// ошибка
[] |> List.reduce (+)
// хорошо, с явным нулем
[1..10] |> List.fold (+) 0
// хорошо, с явным нулем
[] |> List.fold (+) 0
Использование "нуля" приводит к нелогичным последствиям. Например, что будет результатом пустого списка целых чисел?
Ответ - 1, а не 0 как вы могли ожидать. Вот код, который доказывает это:
[1..4] |> List.fold (*) 1 // результат 24
[] |> List.fold (*) 1 // результат 1
Заключение
Моноид это фактически способ описать шаблон агрегации - у нас есть список сущностей, и нам нужно их как нибудь комбинировать, для того что бы получить один агрегирований объект в конце.
Или в терминах F#:
Monoid Aggregation : 'T list -> 'T
Когда вы проектируете код, и начинаете оперировать терминами на подобие "сумма", "результат", "композиция" или "конкатенация", это тонкий намек на то, что вы имеете дело с моноидом.
—