Злоупотребление алгеброй алгебраических типов данных - почему это работает?

«Алгебраическое» выражение для алгебраических типов данных выглядит очень многообещающим для кого-то с математическим образованием. Позвольте мне попытаться объяснить, что я имею в виду.

Определив основные типы

• Продукт •
• Объединение +
• Синглтон X
• Блок 1

и используя сокращение X² для X • X и 2X для X + X и так далее, мы можем затем определить алгебраические выражения для, например, связанные списки

data List a = Nil | Минусы a (Список a) ↔ L = 1 + X • L

и двоичные деревья:

Дерево данных a = Nil | Branch a (Tree a) (Tree a) ↔ T = 1 + X • T²

Итак, мой первый инстинкт как математика - сходить с ума с этими выражениями и попытаться найти для L и T . Я мог бы сделать это путем многократной подстановки, но мне кажется, что намного проще ужасно злоупотреблять обозначениями и делать вид, что я могу переставить их по своему желанию. Например, для связанного списка:

L = 1 + X • L

(1 - X) • L = 1

L = 1 / (1 - X) = 1 + X + X² + X³. + ...

, где я совершенно неоправданно использовал разложение в степенной ряд 1 / (1 - X) , чтобы получить интересный результат, а именно, что L тип либо Nil , либо он содержит 1 элемент, либо он содержит 2 элемента, или 3 и т. д.

Это станет более интересным, если мы сделаем это для двоичных деревьев:

T = 1 + X • T²

X • T² - T + 1 = 0

T = (1 - √ (1 - 4 • X)) / (2 • X)

T = 1 + X + 2 • X² + 5 • X³ + 14 • X⁴ + ...

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

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

И, что, возможно, более интересно, можно ли расширить эти идеи? Существует ли теория алгебры типов, которая допускает, например, произвольные функции от типов, или типы требуют представления степенного ряда? Если вы можете определить класс функций, то имеет ли смысл композиция функций?