10

为什么空列表上的“and”返回true，是否意味着空列表为True？抱歉，我无法正确阅读和理解这一点，所以请纠正我。谢谢。

Prelude> and []
True
Prelude> or []
False
4

7 回答 7

38

在数学中，将二元运算（例如&&, ||, +,*等）称为具有恒等式通常很有用。标识是一个值e，使得以下属性适用于某些通用二元运算<>

e <> x = x
x <> e = x

对于我上面列出的运算符，它们是可交换的，这意味着x <> y = y <> x对于所有xand y，我们只需要检查上述属性之一。对于and，有问题的二元运算符是&&，对于or二元运算符是||。如果我们为这些操作制作一个凯莱表，它看起来像

&&    | False | True
------+-------+------
False | False | False
True  | False | True


||    | False | True
------+-------+------
False | False | True
True  | True  | True

如您所见，&&如果您有True && False和True && True，答案始终是 的第二个参数&&。对于||，如果你有False || Falseand False || True，答案总是第二个参数，所以每个参数的第一个参数必须是这些运算符下的标识元素。简单地说：

True && x = x
x && True = x

False || x = x
x || False = x

因此，当没有要对其执行操作的元素时，首选答案是每个操作的标识元素。

考虑 和 的标识元素可能会有所帮助+，*它们分别是0和1：

x + 0 = x = 0 + x
x * 1 = x = 1 * x

您还可以将其扩展到列表连接（++with []）、类型函数的函数组合a -> a（(.)with id）等操作，以及许多其他操作。由于这开始看起来像一个模式，你可能会问这是否已经是 Haskell 中的一个东西，并且确实是。该模块Data.Monoid定义了Monoid抽象此模式的类型类，它的最小定义是

class Monoid a where
    mempty :: a                   -- The identity
    mappend :: a -> a -> a        -- The binary operator

mappend它甚至为易于使用而使用别名<>（我在上面选择它作为通用二元运算符并非偶然）。我鼓励您查看该模块并尝试使用它的定义。源代码很容易阅读并且很有启发性。

于 2014-08-21T13:44:24.550 回答
12

and和or只是折叠，在空列表上调用的折叠将产生它的起始参数，分别是Trueor False。

它们仅在加载时才使用折叠来实现，否则它们是使用显式递归实现的，尽管实际上没有使用or Prelude，但它本身仍然是折叠。通过检查源代码，它们的行为仍然与我们看到的相同：foldrfoldl

and [] = True
and (x:xs) = x && and xs
or [] = False
or (x:xs) = x || or xs

这是实现的链接。

为了消除注释中的混淆：折叠是一个函数，它接受一个二进制函数和一个起始值（通常称为累加器）并遍历一个列表直到它为空。当在空列表上调用时，折叠将返回累加器，不管列表是否已经被遍历。这是一个示例实现foldr：

foldr _ acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)

and简直就是

and = foldr (&&) True

这使得and []评估为True。

于 2014-08-21T13:38:42.077 回答
7

很好的答案，但我认为值得提供更直观的处理。and :: [Bool] -> Bool然而，让我们看一下 ，而不是all :: (a -> Bool) -> [Bool] -> Bool。你可以这样想all。将谓词（a -> Bool参数）想象成关于列表元素的假设。当且仅当列表包含至少一个假设的反例时，然后all返回。如果列表为空，则没有反例，因此可以轻松确认。False

要将其带回and，请注意and和all是可相互定义的。如果你有and，你可以all这样定义：

all :: (a -> Bool) -> [a] -> Bool
all pred = and . map pred

反之亦然，如果您已经拥有，则可以从中all定义：and

and :: [Bool] -> Bool
and = all id
于 2014-08-21T17:41:09.813 回答
5

除了@bheklilr 的回答，让我们回想一下 Monoid 是一个元组(M,e,<>)，其中M是一个对象（您可以将其视为一种类型），e是对象的一个​​点M（e : M - 类型的元素）并且<>是一个二元运算，其中是关联的并且具有e身份：

<> : M -> M -> M
e <> x = x
x <> e = x
(x <> y) <> z = x <> (y <> z)

一些幺半群之间存在幺半群同态。有一个自由幺半群——从其同态到任何其他幺半群的幺半群。这样的自由幺半群是一个列表：([a], [], ++)可以映射到任何其他幺半群。例如：

([Int], [], ++) => (Int, 0, +)
([Int], [], ++) => (Int, 1, *)
([Bool], [], ++) => (Bool, True, &&)
([Bool], [], ++) => (Bool, False, ||)

然后sum, product, and,or是各自的幺半群同态，映射类型[Int]和的元素[Bool]。根据幺半群同态的定义，幺半群的映射h是以任何列表x++y映射到点的方式执行的h(x ++ y) == (h x) <> (h y)- 例如，and (x++[]) == (and x) && (and [])。从后一个示例中可以清楚地看出，因为x++[] == x，所以(and x) && (and []) == and x，因此，and []映射到 的单位元素(Bool, True, &&)。

于 2014-08-21T14:49:52.257 回答
4

考虑True和的一种方法是作为由 排序的晶格False元素。并且可以被视为此格的二元“满足”（最大下限）和“连接”（最小上限）操作。同样，和是一般的有限满足和有限连接操作。是什么？是 的最大下界。但是（无意识地）小于或等于 的每个元素，所以它是 的下界，并且（当然）它大于任何其他下界（另一个存在），所以False < True&&||andorand [][]True[][]Falseand [] = True. 代数观点（考虑幺半群等）结果完全等同于序论观点，但我认为序论观点提供了更多的视觉直觉。

于 2014-08-22T01:32:37.700 回答
2

的逻辑and是找到列表中的第一个条目False。如果未找到该条目，则结果为True。例如：

and $ map even [2..]

不会遍历整个无限列表，但会停止3并返回False。空列表中没有False元素，所以我们默认为True.

因为or它是类似的：它试图找到第一个True然后停止，否则它是False.

于 2014-08-21T13:43:34.150 回答
1

and意思是：“一切都在那里True吗？”。当它为空时，里面的所有东西（不多）都是真的，所以这是一个是（True）。

or意思是：“有什么True吗？”。当那里什么都没有时，那里就没有真实的东西。( False)

于 2018-12-23T14:55:49.200 回答