在Haskell中实现冯·诺依曼序数时遇到类型匹配错误如何解决

Haskell是强静态类型语言，同一个函数的所有返回值必须是相同类型。列表要求所有元素类型一致（即你提到的齐次类型），你的实现存在天然的类型冲突：

• ordinal 0返回[]，类型为[a]
• ordinal 1返回[ordinal 0]即[[]]，类型为[[a]]
• ordinal 2返回[ordinal 0, ordinal 1]即[[], [[]]]，类型为[[[a]]]

每次调用返回的列表嵌套层数不同，对应类型完全不同，因此编译器抛出Couldn't match type 'a' with '[a]'的类型不匹配错误。

• 不需要改用元组：元组虽然支持存储不同类型的元素，但元组的长度是其类型的一部分，ordinal n返回的集合长度等于n，不同n对应的返回值类型仍然不统一，依旧无法通过类型校验。
• Haskell不存在原生的元组推导式语法：元组的长度和元素类型都是静态确定的，无法像列表一样实现通用的推导式构造逻辑。

自定义递归代数数据类型统一所有序数的类型即可，冯诺依曼序数的本质是每个序数都是所有更小序数的集合，递归类型正好匹配这个结构：

-- 定义冯诺依曼序数类型，每个序数是一个存储同类型元素的列表
data VonNeumannOrd = Ord [VonNeumannOrd] deriving (Show, Eq)

ordinal :: Int -> VonNeumannOrd
ordinal 0 = Ord []
-- 注：原代码中列表生成范围有误，冯诺依曼序数n包含0到n-1的所有序数
ordinal x = Ord [ ordinal n | n <- [0..x-1] ]

测试效果符合预期：

> ordinal 0
Ord []
> ordinal 1
Ord [Ord []]
> ordinal 2
Ord [Ord [],Ord [Ord []]]

内容的提问来源于stack exchange，提问作者AlgebraicsAnonymous