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

Question

我正在进行一个基本的Haskell练习,其设置如下:一个数据定义,Zero声明为a NaturalNumber,一系列数字(按名称打印,例如,four),直到ten构造有了这个.

我理解Eq实例声明的工作原理并没有太多麻烦(除了没有给出语法的确切解释),但是我在声明我需要的所有实例时遇到了麻烦Ord- 我需要成为能够在整个数字集上构建一个排序,这样True如果我输入"ten> nine"或者其他东西我就会得到.

现在,我有这段代码.前两行应该是正确的,因为我从练习本身复制它们(就像我应该的那样).

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,我得到一个"模式匹配(es)重叠"警告,但它的工作原理.但是,GT当我输入compare one two实际的Haskell平台时,我也得到了结果,所以显然有些东西不起作用.即使我compare one two = LT在该行下方添加,也会发生这种情况.

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

任何人都可以告诉我如何解决这个问题并完成订购机制的构建？

Answer 1

此任务的重点是查找基本案例和递归规则.你得到的前两行是

instance Ord NaturalNumber where
    compare Zero Zero   = EQ

这是第一个基本案例,用文字表示:

零等于零

另外两个基本案例是:

零小于任何一个的继承者 NaturalNumber

any的继承者NaturalNumber大于零

请注意,您的第三行和第四行仅表示0 < 1和1 > 0,但没有任何其他非零数字.

那么,递归规则是,如果你比较两个非零数字,或者它们是后继数字,它就没有区别:

比较1 + x和1 + y比较x和y.

将其编码到Haskell应该可以为您提供此练习的解决方案.

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之间进行比较.您应该更改它们以涵盖零和任何正数之间的比较:

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