为什么"和[]"为真,"或[]"为假

Question

为什么空列表中的"和"返回true,是否表示空列表为True？对不起,但我无法正确阅读和理解,所以请纠正我.谢谢.

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

Answer 1

在数学上,它往往是有用谈论二元运算,例如&&,||,+,*,等为具有身份.标识是一个值e,使得以下属性适用于某些通用二进制操作<>

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

对于我上面列出的运营商,他们是可交换的,这意味着x <> y = y <> x所有的x和y,所以我们只需要检查上面的属性之一.因为and,有问题的二元运算符是&&,对于or二元运算符是||.如果我们为这些操作制作Cayley表,它看起来就像

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


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

因此,大家可以看到,对于&&如果您有True && False和True && True,答案永远是第二个参数&&.对于||,如果您有False || False和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是<>易于使用的别名(我在上面为一般二元运算符选择它并不是偶然的).我鼓励您查看该模块并使用其定义.源代码非常易于阅读并具有启发性.

Answer 2

and并且or只是折叠,并且在空列表上调用的折叠将产生其起始参数,分别是True或False.

它们只有在Prelude加载时才使用折叠实现,否则它们是使用显式递归实现的,尽管实际上没有使用foldr或者仍然是折叠foldl.通过检查来源,它们的行为仍然与我们看到的相同:

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

这是实现的链接.

清除注释中的混淆:fold是一个函数,它接受二进制函数和起始值(通常称为累加器)并遍历列表直到它为空.当在空列表上调用时,折叠将返回累加器,如果列表已经遍历则无关紧要.这是一个示例实现foldr:

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

and 很简单

and = foldr (&&) True

这使得and []评估True.

Answer 3

优秀的答案,但我认为值得提供更直观的治疗.相反的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

Answer 4

除了@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)

一些幺半群之间存在幺半群同态.有一个自由的幺半群 - 与其他任何一个同态的幺半群.这样的免费monoid是一个列表:([a], [], ++)可以映射到任何其他monoid.例如:

([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, &&).