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

Question

Я читаю книгу на Haskell (стр. 412). В этой книге есть объяснение нормальной формы для суммы произведений:

Все существующие алгебраические правила для произведений и сумм применяются в системах типов, включая свойство распределения. Давайте посмотрим, как это работает в арифметике:

2 * (3 + 4)
2 * (7)
14

Мы можем переписать это с умножением, распределенным по сложению, и получить тот же результат:

2 * 3 + 2 * 4
(6) + (8)
14

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

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

Количество типов означает, сколько разных значений может быть включено в этот тип (например, набор). Например, тип Bool в haskell имеет кардинальное число 2, то есть сложение 1 для False и 1 для True каждый.

Является ли сумма продуктов (2 * 3 + 2 * 4) нормальнойформе? Это выражение может быть уменьшено еще больше, потому что полностью уменьшенное выражение будет 14. Я не понимаю, почему сумма продуктов и их количество связаны с нормальной формой.

Answer 1

Давайте объявим несколько типов для представления чисел:

data Two = OneOfTwo | TwoOfTwo
data Three = OneOfThree | TwoOfThree | ThreeOfThree
data Four = ... (similar)

Теперь мы можем видеть, что число возможных значений типа Two фактически равно 2. То же самое для Three, Four и Seven.

Теперь, если мы создадим тип суммы:

data A = A Two

Этот тип просто прямо обернет значение Twoпоэтому число возможных значений A также равно 2. Пока все хорошо?

Теперь давайте построим более сложный:

data B = B1 Three | B2 Four

Теперь этот тип переносит либо значение типа Three или значение типа Four (но не оба одновременно!) Это означает, что число возможных значений будет 3 + 4. Следуйте до сих пор?

Теперь, идем дальше:

data C = C Two B

Этот тип переносит два значения одновременно - одно значение типа Two и одно значениетипа B. Это означает, что число возможных значений C - это число возможных комбинаций Two и B, которое, как мы знаем из математики средней школы, будет их произведением, или 2 * (3 + 4) = 2 * (7) = 14.

Но вот хитрость: мы можем записать эквивалентный тип по-другому:

data CNew = C1 Two Three | C2 Two Four

Видите, что я там делал? Для CNew набор всех возможных комбинаций между значениями Two, Three и Four такой же, как для C. Посмотрите: в обоих случаях это либо значение Two в сочетании со значением Three, либо значение Two в сочетании со значением Four. За исключением CNew они объединяются напрямую, но в C они объединяются через B.

Но формула для CNew будет иной: 2 * 3 + 2 * 4 = (6) + (8) = 14. Вот что означает книга.

Теперь, чтобы ответить на этот вопрос более прямо:

Является ли сумма произведений (2 * 3 + 2 * 4) нормальной формой? Это выражение может быть еще больше уменьшено, потому что полностью сокращенное выражение будет 14

Это было бы верно, если бы мы имели дело с целыми числами, но это не так. Мы можем переписать C в виде CNew, потому что это дает нам все те же возможные комбинации значений. Но мы не можем переписать их как тип, который имеет до 14 возможных значений без объединения 2, 3 и 4. Это был бы совершенно новый, не связанный тип, в отличие от комбинации Two, Three и Four.

и возможного недопонимания терминологии:

Является ли сумма продуктов (2 * 3 + 2 * 4) нормальной формой?

Термин «нормальная форма» не означает «самая короткая». Этот термин обычно используется для обозначения формы, которая является очень регулярной, и поэтому с ней легче работать, и, что особенно важно, которая может представлять все возможные случаи в домене. В этом случае нормальная форма определяется как «сумма произведений».

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

Может ли это быть «просто числом возможных значений», например 14? Опять нет, потому что преобразование в такую ​​форму теряет некоторую информацию (см. Выше).