代数数据类型的“代数”表达式对于具有数学背景的人来说非常具有启发性。让我试着解释一下我的意思。

已经定义了基本类型

产品• 联盟+ 单例X 1号机组

用简写X²表示X•X，用简写2X表示X+X，以此类推，我们可以为链表定义代数表达式

数据列表a =无|缺点a(列表a)↔L = 1 + X•L

二叉树:

数据树a =无|分支a(树a)(树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•X)) / (2)

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

再次，使用幂级数展开(用Wolfram Alpha完成)。这表达了一个(对我来说)不明显的事实，即只有一个有1个元素的二叉树，2个有2个元素的二叉树(第二个元素可以在左边或右边分支)，5个有3个元素的二叉树等等。

我的问题是，我在这里做什么?这些操作似乎不合理(代数数据类型的平方根到底是什么?)，但它们会导致合理的结果。两种代数数据类型的商在计算机科学中有什么意义吗，还是只是符号技巧?

也许更有趣的是，是否有可能扩展这些想法?是否存在一种类型代数理论允许，例如，类型上的任意函数，或者类型需要幂级数表示?如果你可以定义一类函数，那么函数的组合有什么意义吗?