递归类型

清单

列表可以定义为：

data List a = Nil | Cons a (List a) 

如果我们将其转换为我们的类型代数，我们得到

清单（a）= 1 + a *清单（a）

但是我们现在可以多次在这个表达式中替换 List(a) ，以获得：

列表（a）= 1 + a + a * a + a * a * a + a * a * a * a + …

如果我们将列表视为只能包含一个值的类型，这是有意义的，如 []; 或 a 类型的每个值，如 [x]; 或两个 a 类型的值，如 [x,y]; 等等。List 的理论定义应该是：

-- Not working Haskell code!
data List a = Nil
            | One a
            | Two a a
            | Three a a a 
            ...

树

例如，我们可以用二叉树做同样的事情。如果我们将它们定义为：

data Tree a = Empty | Node a (Tree a) (Tree a)

我们得到了表达式：

树（a）= 1 + a *树（a）*树（a）

如果我们一次又一次地进行相同的替换，我们将获得以下序列：

树（a）= 1 + a + 2（a * a）+ 5（a * a * a）+ 14（a * a * a * a）+ …

我们在这里得到的系数对应于加泰罗尼亚数字序列，第 n 个加泰罗尼亚数字恰好是具有 n 个节点的可能二进制树的数量。