在 Haskell 中实现序数

Question

我已经开始学习 Haskell，我想我会使用常见的（“冯·诺依曼”）定义来实现序数。所以我写道：

ordinal 0 = []
ordinal x = [ ordinal n | n<-[1..(x-1)] ]

但翻译并不满意，它反而告诉我，据说

    * Couldn't match type `a' with `[a]'
Expected: t -> a
Actual: t -> [a]
* Relevant bindings include
ordinal :: t -> a (bound at fist.hs:7:1)
|
1 | ordinal 0 = []
| ^^^^^^^^^^^^^^^...

现在我想这里可能出错的是该列表不是同类类型的。但是我该如何切换到元组呢？是否有“元组理解”之类的东西？

Answer 1

该函数的结果是单个空值、此类值的列表、列表的列表、列表的列表的列表等，具体取决于输入数字。没有一个列表类型可以代表所有这些值。

...或者有吗？该类型不是[]仅表示单个扁平值序列的列表（即 ），但有这样一种类型：

data Ordinal = Zero | Ordinal [Ordinal] deriving Show

并且您的函数应该修改为将每个此类级别的列表嵌套包装在Ordinal构造函数中：

ordinal 0 = Zero
ordinal x = Ordinal [ ordinal n | n<-[1..(x-1)] ]

例子：

*Main> ordinal 3
Ordinal [Ordinal [],Ordinal [Ordinal []],Ordinal [Ordinal []]

Answer 2

首先，列表不是集合。

\n

其次，列表要求所有元素具有相同的类型，因此一个列表中不能包含不同嵌套深度的列表。

\n

但是从 \xe2\x80\x9c 来看，一切都是一个集合 \xe2\x80\x9d 的角度，冯诺依曼序数等结构是基于这样的，你可以定义一个 \xe2\x80\x9cuniversal type\xe2\x80\x9d based在集合上：

\n

import qualified Data.Set as Set\n\nnewtype UntypedSet = UntypedSet { getUntypedSet :: Set.Set UntypedSet }\n deriving (Eq, Ord, Show)\n\nordinal :: Int -> UntypedSet\nordinal 0 = UntypedSet $ Set.empty\nordinal x = UntypedSet $ Set.fromList [ ordinal n | n <- [0..x-1] ]\n

\n

请注意，您的实现中的定义[1..x-1]实际上是错误的，它应该是[0..x-1].

\n

如果你想变得古怪（不一定推荐），你实际上仍然可以使用 \xe2\x80\x9clist\xe2\x80\x9d 表示法：

\n

{-# LANGUAGE OverloadedLists #-}\n{-# LANGUAGE TypeFamilies    #-}\n\nimport qualified Data.Set as Set\nimport GHC.Exts (IsList(..))\n\nnewtype UntypedSet = UntypedSet { getUntypedSet :: Set.Set UntypedSet }\n deriving (Eq, Ord)\n\ninstance IsList UntypedSet where\n  type Item UntypedSet = UntypedSet\n  fromList = UntypedSet . Set.fromList\n  toList (UntypedSet s) = Set.toList s\n\ninstance Show UntypedSet where\n  show = show . toList\n\n\nordinal :: Int -> UntypedSet\nordinal 0 = []\nordinal x = fromList [ ordinal n | n <- [0..x-1] ]\n

\n

然后，

\n

*Main> ordinal 4\n[[],[[]],[[],[[]]],[[],[[]],[[],[[]]]]]\n

\n