遞迴型別

清單

列表可以定義為：

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 個節點的可能二進位制樹的數量。