sorting - 编写排序实例的有效方法？

Question

我正在做一个基本的 Haskell 练习，设置如下:进行数据定义，其中 Zero被声明为 NaturalNumber , 和一系列数字(按名称打印，例如 four )直到 ten是用这个构造的。

我在理解 Eq 的声明方面没有太多麻烦实例有效(除了没有给出语法的确切解释)，但我在声明 Ord 所需的所有实例时遇到了麻烦。 -- 我需要能够对整个数字集进行排序，这样我会得到 True如果我输入“十>九”之类的。

现在，我有这段代码。前两行应该是正确的，因为我从练习本身中复制了它们(正如我应该做的那样)。

instance Ord NaturalNumber where
    compare Zero Zero   = EQ
    compare Zero (S Zero)  = LT
    compare (S Zero) Zero  = GT
    compare x    (S x)  = LT

前四行工作正常，但它们无法处理“比较四五”之类的情况，即使我输入类似 compare four four = EQ 的内容，与我最后输入的内容类似的任何内容也不起作用: 我得到一个“冲突定义”的错误，大概是因为 x出现两次。如果我写类似 compare two one = GT相反，我收到“模式匹配重叠”警告，但它有效。但是，我也得到了结果 GT当我输入 compare one two进入实际的 Haskell 平台，很明显有些东西不起作用。即使我添加 compare one two = LT 也会发生这种情况低于该线。

很明显，我无法完成对 Ord 的描述。通过编写我可能需要的每个实例来编写实例，即使我可以，手动写出所有 100 个实例也是非常低效的。

谁能给我一个提示，告诉我如何解决这个问题并完成排序机制的构建？

Answer 1

这项任务的重点是找到基本案例和递归规则。你得到的前两行是

instance Ord NaturalNumber where
    compare Zero Zero   = EQ

这是第一个基本情况，换句话说:

zero is equal to zero

另外两个基本情况是:

zero is less than the successor of any NaturalNumber

the successor of any NaturalNumber is greater than zero

请注意，您的第三行和第四行只说 0 < 1和 1 > 0 ，但与任何其他非零数无关。
因此，递归规则是，如果比较两个非零数或它们的后继数，则没有区别:

comparing 1 + x and 1 + y is the same as comparing x and y.

将其编码到 Haskell 中应该会给你这个练习的解决方案。