高效编写排序实例的方法？

Question

我正在做一个基本的Haskell练习，如下所示：定义了一个数据类型，其中声明Zero为NaturalNumber，并使用此构建了一系列数字（按名称打印，例如four），直到ten。

对于理解如何声明Eq实例，我没有太多困难（除了没有得到语法的确切解释），但是我在声明所有我需要的Ord实例方面遇到了麻烦 - 我需要能够构建整个数字集上的排序，以便如果我输入“ten > nine”或其他内容，我将获得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 five”这样的情况，以及我输入最后一行代码compare four four = EQ之类的任何类似情况：我会收到一个“conflicting definitions”的错误提示，可能是因为出现了两次x。如果我改为输入compare two one = GT，则会收到“pattern match(es) are overlapped”的警告，但它能正常工作。然而，如果我在实际的Haskell平台中输入compare one two，也会得到结果GT，因此显然有些问题。即使我添加了以下代码compare one two = LT，这个问题仍然存在。

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

是否有人能够给我提供一些提示，以解决这个问题并完成排序机制的构建？

- Maroon

---

注意：我对Haskell完全是个新手。可能是因为我不够熟悉语法，特别是因为我通常发现其他我使用过的语言的文档更容易阅读，但我感觉这不是唯一的问题。 - Maroon

看起来你想在最后一种情况下使用递归，并且有类似于compare (S x) (S y) = compare x y的东西。此外，您可以使用下划线_来描述您不关心详细情况，例如compare (S _) Zero = …表示您不关心第一个数字的大小，只要知道它大于等于1并且第二个数字为零即可。 - Jakob Runge

Answer 1

这个任务的重点是找到基本情况和递归规则。你得到的前两行是

instance Ord NaturalNumber where
    compare Zero Zero   = EQ

这是第一个基本情况，用语言表述如下:

零等于零

另外两个基本情况是：

零小于任何NaturalNumber的后继

任何NaturalNumber的后继都大于零

请注意，第三行和第四行仅说明0＜1和1＞0，而不涉及任何其他非零数字。

递归规则是，如果您比较两个非零数字或它们的继承者，则没有区别：

比较1 + x和1 + y与比较x和y是相同的。

将其编写成Haskell代码将为您提供此练习的解决方案。

- Silly Freak

---

这是有道理的。我觉得递归应该在其中某个地方出现，（现在想起来，我不知道为什么曾经把compare Zero (S _)替换成了compare Zero (S Zero)）但是出于某种原因，我无法完全弄清楚怎么做（尽管类似的东西在Eq实例中已经出现过了，真是奇怪）。 - Maroon

Answer 2

您需要按照一种方式组织您的实例，以覆盖所有可能的模式。为了使其更简单，请记住数字是如何定义的：

one = S Zero
two = S one  -- or S (S Zero)

要思考的是S和Zero，而不是one、two等（它们只是别名）。一旦你这样做了，就会清楚你缺少了这样一个情况：

compare (S x) (S y) = compare x y

编辑：

正如Jakob Runge所指出的那样，下列基本条款也应该得到改进：

compare Zero (S Zero)  = LT
compare (S Zero) Zero  = GT

按照现有写法，它们只允许比较0和1。您应该将其改为可以比较0和任何正数：

compare Zero (S _)  = LT
compare (S _) Zero  = GT

- rburny

Answer 3

您的compare函数需要使用递归。您需要让最后一个情况捕获两个参数都是某个后继的情况，然后对它们所继承的内容进行递归。此外，您的中间两个情况可能不是您想要的，因为它们只会捕获以下情况：

1. 1 > 0
2. 0 < 1

您希望这更加通用，以便可以处理如下情况：

1. S x > 0，对于所有的x
2. 0 < S x，对于所有的x

- Matt

---

еңЁж•°еӯ—д№Ӣй—ҙзҡ„и·қзҰ»>1зҡ„жғ…еҶөдёӢдҪҝз”Ё_д№ҹжҳҜжңүж„Ҹд№үзҡ„гҖӮ - Jakob Runge

在第二个和第三个分支中，您可能是想使用 S _ 而不是 S Zero。 - isekaijin

对于作业问题，我认为仅提供代码的答案是不合适的。 - Silly Freak