理解Haskell的Bool类型如何派生一个Ord类型

Question

Learn You a Haskell介绍了Bool类型：

data Bool = False | True deriving (Ord)

我不明白为什么要比较Bool。

> False `compare` True
LT
> True `compare` False
GT

如果Bool没有从Ord继承会失去什么？

- Kevin Meredith

---

好的，我会尽力进行翻译。以下是需要翻译的内容：Well, you couldn't have a Map of bools. What is there to gain by not having an Ord instance? Also, notice you couldn't trivially derive Ord for ANY type that includes Bool without a pre-existing instance Ord Bool。你不能拥有一个包含布尔值的Map。不具备Ord实例有什么好处呢？另外，请注意，如果没有预先存在的instance Ord Bool，任何包含Bool类型的类型都无法轻松地派生Ord。 - Thomas M. DuBuisson

指示函数如何？例如，fromEnum . (elem [1,2,3])，如果应用于集合的元素，则为1，否则为0？ - idontgetoutmuch

我认为应该称其为“派生一个Ord实例”，而不是“从Ord派生”。 - felix-eku

感谢 @chaosmasttter。我刚刚用你的更正进行了更新。 - Kevin Meredith

Answer 1

Bool 构成一个有界格*，其中 False 是 bottom，True 是 top。这个有界格定义了一个（全）排序，其中 False 严格小于 True。它们也是这个格的唯一元素。

布尔运算 and 和 or 也可以分别看作是该格中的 meet 和 join。Meet 找到了最大下界，Join 找到了最小上界。这意味着 a && False = False 相当于说 bottom 和任何其他值的最大下界都是 bottom，a || True = True 相当于说 top 和任何其他值的最小上界都是 top。因此，Meet 和 Join 利用了布尔值的排序特性，与您熟悉的布尔运算是等价的。

您可以使用 min 和 max 在 Haskell 中展示这个结果：

False `min` True = False -- this is the greatest lower bound
False  &&   True = False -- so is this

False `max` True = True  -- this is the least upper bound
False  ||   True = True  -- so is this

这表明您可以仅从衍生的Ord实例中定义&&和||：

(&&) = min
(||) = max

注意，由于存在不同类型底部的存在，这些定义并不等价，因为(&&)和(||)是短路运算符（当第一个参数为False或True时，第二个参数非严格化），而min和max则不是。

另外，有一个小修正： deriving子句并不表示Bool“源自”Ord。它指示GHC为类型Bool派生一个Ord类型类实例。

* 更具体地说，它是一个补合分配格。更具体地说，它是一个布尔代数。

- Rein Henrichs

---

(&&) = min; (||) = max与典型定义有所不同：它们具有不同的严格性属性，因此，例如，在底部（"bottom"是指未定义等）方面，它们的行为不同。 (&&)和(||)是短路运算。 - David Young

好的，如果你认为有帮助的话，我可以加上通常的“从上到下”的警告。 - Rein Henrichs

请问一下，meet和join的意义是什么？我已经读了你关于它们的段落两遍，但我还是不理解。具体来说，Bool的least upper bound和greatest lower bound的含义是什么？ - Kevin Meredith

@newacct (&&) 和 (||) 是通过短路模式匹配来定义的。对于 compare 来说，为了得到一个结果（至少在 Bool 类型上），它必须评估两个参数，因为存在它们相等的可能性。考虑 True || undefined 和 True \max` undefined` 之间的区别。 - David Young

@ReinHenrichs 听起来对我来说是个好主意。不过，最好将其与“Bool”有界格子中的“bottom”区分开来。 - David Young

Answer 2

当您需要比较包含 Bool 的值时，Bool类型的Ord实例变得更加重要。例如，如果没有它，我们将无法编写以下表达式:

[False,True] `compare` [False,True,False]

(3, False) < (3, True)

data Person = Person { name :: String, member :: Bool } deriving (Eq, Ord)

等等。

- Petr

Answer 3

这是因为 Haskell 的设计者犯了一个错误！我从来没有看过一本数学教科书提到布尔值的排序。仅仅因为它们可以排序并不意味着我们应该这样做。我们中的一些人使用 Haskell 正是因为它在许多情况下禁止/保护我们免受混淆/荒谬的事情，但这种情况除外。

instance Ord Bool 导致 a => b 意味着你期望的 a <= b 的含义！

早先支持 instance Ord Bool 的论点是，您可以使更多类型隐式可比较。继续这条线的论证，有些人可能希望使每种类型都隐式可比较，甚至省略类型类并具有弱动态类型。但我们想要强类型，正是为了禁止那些不明显正确的事情，而 instance Ord Bool 打败了这个目的。

至于 Bool 是有界格。与 boolean:={True,False} 不同，我们在 Haskell 中拥有的是 Bool:={True,False,bottom}，不再是有界格，因为在 bottom 的存在下，True 和 False 都不是恒等元素。这与那些讨论 && vs min 等的评论有关。

- ropmlcpm

---

我不太理解你的论点。许多Monad实例在存在bottom情况下也是不正确的，然而我们仍然在使用它们。 - Lambda Fairy

在 Haskell 中，以“底部为上限”进行推理是非常常见的，我已经包含了一个关于这个方面的警告。我们之所以能够这样做，是因为在 快速松散推理在道德上是正确的 (PDF) 中探讨的意义上，“道德上是正确的”：如果两个术语在总体语言中具有等效的语义，则它们在部分语言中具有相关的语义，因此尽管 Haskell 是部分的，我们仍然可以有效地推理出其语义。 - Rein Henrichs