Комментарии 14
Зачем выделять дополнительные условия 4 и 5 в определении полукольца? Они же следуют из свойств моноидов и дистрибутивности.
В eitherCardinality не забыли вычесть мощность пересечения множеств значений типов?
Говоря о сумме типов вообще, можно провести аналогию, что сумма типов — это контейнер с ячейками, каждую из которых может занимать какой-либо тип, но всего может быть занята ровно одна ячейка. Соответственно, значения суммы типов — это «контейнер с заполненной ячейкой 1», «контейнер с заполненной ячейкой 2» и т.д. Таким образом, опять получаем строгую сумму, даже если типы в ячейках совпадают.
Т.е. нет "наследования" типов? (Integer)2 и (Number)2 обязательно разные вещи?
Какое-нибудь включение множеств значений типов друг в друга. Пусть E = Either[N, Z], где Either — сумма типов N и Z, как оно применяется в статье, N — тип, элементами которого являются только все натуральные числа меньше 3 (пусть с нулём), Z — тип, элементами которого являются только все целые числа меньше 3 по модулю. Я интуитивно ожидаю кардинальное число |E| = 5.
Я так понимаю, что вы пытаетесь рассматривать сумму типов как объединение множеств значений этих типов, но эти операции не совпадают.
В данном случае речь не идёт о каком-либо наследовании или включении одного типа в другой. Каждому из суммируемых типов можно сопоставить индекс, а значение суммы типов — это по сути "индекс" + "значение типа с соответствующим индексом в сумме". То есть для значения суммы типов важно, какой именно по порядку тип выбран.
Пример с Either[A, B] наиболее иллюстративен, так как Left[Int, Int](1) != Right[Int, Int](1), потому что различаются "обёртки"
И в первом примере дополнения откуда степень? "A => B" — тип функции? Тогда достаточно перемножить мощности множеств значений A и B, нет?
Да, A => B — тип функции. Интуитивно понятно, что, если бы мы просто перемножили кардинальные числа, то получили бы результат, аналогичный произведению типов. Но количество функций из A в B в общем случае с количеством пар (A, B) не совпадает.
Откуда же берётся формула B^A? Рассмотрим произвольный элемент типа A. Функция A => B может переводить его в любой элемент типа B, значит, всего |B| вариантов. Рассмотрим следующий элемент типа A. Для него ситуация аналогичная — |B| вариантов. Это будет выполняться для любого представителя A. Соответственно, чтобы получить общее количество вариантов по превращению A в B, перемножим количество вариантов для отдельных представителей: |B| * |B| * |B| * |B| ... (всего |A| раз). Отсюда и следует |B => A| = |B|^|A|.
Аналогичным образом мы можем подумать о функции B => A как о представителе произведения типов (B, B, B, ..., B) (всего |A| раз). Элементами этого произведения можно однозначно задать любую функцию, а как вычислять кардинальное число такого типа уже известно.
А что насчет строк? String — формально неограниченный тип и теоретически обладает бесконечным числом значений (на практике, естественно, мы не обладаем бесконечной памятью, поэтому конкретное число будет зависеть от конфигурации компьютера).
String в текущих реалиях совсем не бесконечный. В JVM он точно не будет длиннее Integer.MAX_VALUE байт (так как содержит byte[] адресуемый целым числом). Причем не удивлюсь, если из-за деталей реализации окажется еще более ограниченным. Это не так много — 2 ГиБ памяти, а это уже не ограничение даже для современных телефонов. Да, конечно, кардинальное число exp(2,(8*(exp(2,31)-1)) изрядно большое (и даже в BigInteger в Java не влезет), но всё-таки эти пределы уже вполне можно "пощупать".
Еще мне из дополнения 2 момента непонятны
Первое:
Cardinality.of[Option[A]] === Cardinality.of[A] + 1А что будет для Option[Option[Option[A]]]? Насколько я понимаю, новых значений там не появится — всё также будет Cardinality.of[A] + 1.
Второе — про Cardinality.of[A => B].
Я правильно понимаю, что это всё только про чистые детерминированные функции (иначе Unit=>Unit не счесть).
Для Option не происходит удаление вложенных None, поэтому формула всё-таки остаётся верной. Вот все значения, которые может принимать такой тип:
Option[Option[A]] = None, Some(None), Some(Some(A)). Кардинальное число: |A| + 1 + 1.
По поводу функций — дельное замечание, мне, наверное, стоило об этом упомянуть. Речь, естественно, идёт не о функциях Scala как таковых, а о морфизмах. Потому что даже чистых детерминированных функций Boolean => Boolean можно набрать бесконечное число, так как True можно представить как True && True, True && True && True и т.д. Cardinality.of[A => B] — это количество возможных вариантов перевести элементы A в элементы B простым сопоставлением/таблицей.
Сказ о полукольцах