Why does all() return True if the iterable is empty?(blog.carlmjohnson.net)

134 pointsby vikrum3 yıl önce194 comments

blog.carlmjohnson.net

Why does all() return True if the iterable is empty?

https://blog.carlmjohnson.net/post/2020/python-square-of-opposition/

202 comments

The sum of no numbers is 0.

The product of no numbers is 1.

The union of no areas (sets, …) is the empty area.

The intersection of no areas (sets, …) is the universal area.

The commonality here, is what element z can you add or remove from a list which won’t change the result?

We call the element that makes no change to the result, the “identity element”.

For y = sum of {x1,x2, … Xn, z},

We know z must be 0, if it has no impact on y. So the identity element for sum is 0.

So if y = sum of {}, we know we can insert the identity element without changing the result, and we know the sum of {0} is 0. The identity element itself.

So operations applied across lists return that operation’s identity element for an empty list.

—-

Ergo:

the identity element of “all” is “true”.

The identity element of “any” is “false”.

——

More fun:

The identity element for the resistance sum across parallel resistors, is the infinite ohm resister.

The identity element for the vector distance sum of a child making a sequence of jumps is the in-place jump.

—-

Getting meta with, oh hell, monads:

The identity element for C, the concatenation operator over lists, is the empty list {}.

Since all lists are concatenations of lists (down to empty & unitary lists), we can view any operation Q over lists also as an operation over the concatenation of lists.

So any Q acts like a monad over list concatenation operations.

If Q = sum, then it is the monad that transforms concatenations of lists of numbers into the sum of those numbers.

If Q = all, then it is the monad that transforms concatenations of lists of truth values to the conjunction of the truth values in those lists.

With that view in place, we can see another reason why the identity of any operation Q is Q on an empty list Q{}

Because as a monad, Q applies over C, the concatenation of lists. The identity of C is {}, so the identity of Q must be Q{}.

Voila!

So we really shouldn’t define sum{} as 0, but define 0 as sum{}.

“0” is just a symbol. Sum{} is what it is.

0 is the sum of nothing.

So “True” IS the conjunction of nothing. It’s meaning IS all{}. It is the truth of “no requirements”.

feoren3 yıl önce

To be pedantic:

TRUE is the identity element of "and", not "all". "All" is not a binary operator, it is the (unary) aggregation of "and". That is, S.all() == S.aggregate((prev, next) => prev && next, TRUE).

FALSE is the identity element of "or". "any"/"some" is the aggregation of "or". S.any() == S.aggregate((prev, next) => prev || next, FALSE).

0 is the identity element of addition, and "sum" is the aggregation of addition. S.sum() == S.aggregate((prev, next) => prev + next, 0).

1 is the identity element of multiplication, with "product" the aggregation.

Given a monoid M<T> { combine(a: T, b: T) => T, identity: T }, you can define an aggregation operation the same way:

    S.aggregate((prev, next) => M.combine(prev, next), M.identity)

Nevermark3 yıl önce

TRUE can be the identity element both for the conjunction of 2 Boolean values, and of an operator that extends 2-value Boolean operations to lists of N-elements.

Being an identity is a property. A given mathematical object can be an identity for more than one relation.

It can also be the identity element for general logical propositions or relations.

The reason being, the former is just a special case of the Boolean relations of AND and ALL.

So TRUE can consistently be the identity for many classes of logical operations of varying generality or complexity.

The raw identity relation and concept of identity element form the “tops” of ladders, whose specializations can hold over large classes of relations.

feoren3 yıl önce

My goal was to add more context to your (excellent and upvoted) original post, which in my opinion is basically the fundamental "proof" of why All([]) must be TRUE, and I find beauty in this two-dimensional analogy:

    add      | sum
    multiply | product
    and      | all
    or       | any
    concat   | "flatten" (arguable name here)

I also find beauty in the fact that the existence of a monoid on the left is sufficient for producing the aggregation on the right that behaves in the way we want. I see the monoid as the simple building block from which we produce more interesting and complicated structures. I enjoy the continued, unbroken thread of rigorous logic that connects everything.

When you say that TRUE can be the identity of "an operator that extends 2-value Boolean operations to lists of N-elements", I just don't see the unbroken thread of rigorous logic behind that statement. Maybe it's there! But I don't see it. I can write down exactly what it means for some element i to be an identity of a binary operation @. It means i@x == x == x@i for all x in the set over which @ is defined. Whatever the rules of "identity" are that you're talking about, they're not this, so I'm just kinda struggling to accept it. I wonder whether maybe what you're thinking of deserves a different name than "identity".

Does any of this matter? It does to me, because I actually use Monoids all the time in programming, where you can't afford any ambiguity at all. So again: maybe you see that unbroken chain of rigorous logic and know exactly what you mean when you say TRUE is the identity of "an operator that extends 2-value Boolean operations to lists of N-elements", but I'd need to see the exact laws that an element must follow to be such an operator or such an identity of that operator. I gave an example of how to turn associative binary operations with identity into a unary operator on lists of elements, but unary operators don't really have identity elements. Some unary operators have fixed points and eigenvalues, which are similar to identity, but such operators must have the same domain and codomain, and aggregate operators like SUM and ALL do not. So there's not really anything you define to be SUM's identity, since it does not accept 0 as an input.

Nevermark3 yıl önce

Ha! I agree, you are right.

TRUE for a monoid can exist independently from any aggregator defined over that monoid.

My bad :)

The fractal lines between what is mathematically true, vs. what is practical or useful to be true, in coding are worth paying attention to!

Thank you!

And perhaps these relations can always hold, “without loss of generality”.

In which case we need to formally define these monoid-aggregator relations so we all know when they are assumed to be in effect.

—

On the beauty side, I love how 0 = sum{} captures the semantic difference between zero and other numbers, with the syntax of nothing between two braces.

feoren3 yıl önce

I do think there was something interesting about the idea that adding the element to the input array doesn't change the result. It's a little tricky to formalize though.

If we define an "aggregation" agg over some set S as a function from S* (the "Kleene star", AKA the free monoid over S, AKA really just simple arrays of S) to S, and we identify some element i such that

   agg([i] concat X) == agg(X) == agg(X concat [i])

for all X in S*, that does feel very "identity-ish". It's a little bit like saying [i] is an identity of concat under the equivalence relation on S* that X~Y iff agg(X) == agg(Y)? In the same way that 7 is an identity of + under the equivalence relation "mod 7" (paraphrasing).

But note that:

   sum([-2, 2] concat X) == sum(X) == sum(X concat [-2, 2])

for all X as well. You could say "well obviously, because sum([-2, 2]) == sum([0]) and [0] is our identity element" but then we're implicitly assuming that agg(X concat Y) = agg(X) @ agg(Y) for some operator @. Which in turn is basically assuming we've built agg up from a monoid to begin with, and the novelty here would be what happens when we don't do that. There may be some interesting (if not useful) stuff here.

if there exists some operator @: (S, S) -> S such that:

    agg(X concat Y) == agg(X) @ agg(Y)

For all X, Y in S*, and if :

    agg([i] concat X) == agg(X) == agg(X concat [i])

for all X in S*, then must agg([i]) be an identity element of @? Certainly that's true if agg is onto (i.e. we can find every element of S via agg of some S*). But it can't really be true in general, because we could make degenerate agg functions like

    ignore(X) := 0

Now every element of S meets this condition:

    ignore([s] concat X) == ignore(X) == ignore(X concat [s])

So we have every element of S as this weird kind of "identity" of the "ignore" function. And we can find functions on S* with no "identity" of this kind: "count", for instance. Although that's cheating because it only works when S happens to be the natural numbers (otherwise agg is not a function from S* -> S).

Nevermark3 yıl önce

Yes I think you hit it on the nail.

My logic depended on the aggregator being a recursive monoid, with:

1) Special handling for a unit list, where the unitary element is returned, and

2) Special handling for an empty list, where the identity element of the monoid is returned OR we get explicit that the case of the empty list is simply already it’s simplest form, and we choose to define that equivalent to the monoid’s identity

So i skipped a step by “finding” the identity from the aggregator’s behavior, instead of directly from the monoid it is based on.

——

Alternatively, I am liking the idea of defining this list vs pair, aggregator vs monoid relations more tightly.

Empty braces unify the syntax for “zero” with the semantics “nothing” between the braces.

How else can you join those semantics and syntax?

Likewise, starting with unary natural numbers, syntactically and semantically, a list of 1’s is the number.

So which comes first? A unary monoid addition of 2 lists of ones (n-way concatenations of unitary 1), or an n-way sum-concatenation that each unary number actually consists of?

I think they are more tightly bound definitions than our typical syntax suggests, when we get down to the semantics = syntax level.

black_knight3 yıl önce

To be even more pedantic! Unit elements are not limited to binary operators. In fact, in a monoid (or group) there is naturally an n-ary operation for each n. Or if you want a single operation from lists of elements to a single element. It is just that we usually present it using a unit and a binary operation + associativity. But one can split that cake in other ways. Thus, in some sense any and all are even more natural or "objective" (as Lawvere would put it) than and and or.

feoren3 yıl önce

What is your definition of an identity of a ternary function? Say i is the identity of f. Must it hold that

    f(i, a, b) == f(a, i, b) == f(a, b, i)?

For all a, b in f's domain? The seems like the obvious choice, and certainly holds for ternary functions "built up" from associative binary ones, but I've just never seen such a thing. Is there a case where it's useful to talk about the identity of a 3-valued function?

I think the thing I find weird about this is that a binary operator op2 over some set S is defined as S^2 -> S. So we can sensibly say:

    op2(a, i) == a == op2(i, a)

But the extension of this to a 3-valued function from S^3 -> S cannot have that middle condition, because it has too many "free variables". We can't say:

    op3(a, b, i) == op2(a, b)

Without establishing a relationship between op3 and op2, but must there be a sensible "decomposition" of op3 into some op2? Surely not. I guess I just don't know what it means to be an identity of a 3-valued function.

As an example, consider mult3(a, b, c) := a * b * c. Then,

    mult3(0, a, b) == mult3(a, 0, b) == mult3(a, b, 0)

for all a and b. We intuitively know that 0 is not behaving like an identity. Can we write down an identity rule that must hold for a generic op3 that excludes 0 as the identity of that function? Without relying on some oracle to provide us an appropriate decomposed op2?

Edit: I would also like to point out this function over R^3:

    f(a, b, c) := a*b + a*c + b*c

Note that every value in R meets the condition:

    f(a, x, y) == f(x, a, y) == f(x, y, a) == ax + ay + xy

For all x and y. Is every number an identity of this function? In fact, this is trivially true for any completely associative function. I guess I just need to see the definition of an identity of a ternary operator.

evertedsphere3 yıl önce

monoid, not monad

---

a monoid is a set A with an associative binary operator @ on it: that is, for any a, b, c

a @ (b @ c) = (a @ b) @ c

and it also has an "identity" element I, that is, for any a:

a @ I = I @ a = a

common monoids: integers under addition (i.e. @ is addition, the identity is 0), nonzero real numbers under multiplication, lists under concatenation, booleans under AND (identity is True), booleans under OR (what's the identity?), ...

now, when you have a mathematical structure, you often want to study functions between two of them. so you might ask what a reasonable notion of functions between monoids is

one nice way is if, given two monoids, M with operation @ and unit I, and N with operation ^ and unit J, we had a function f for which:

f(I) = J

f(a @ b) = f(a) ^ f(b)

this is loosely described as the function "respecting the structure" of the monoids, and such functions are called monoid homomorphisms or just homomorphisms if the context is clear

--

with that background, we see that `all` should really be be a homomorphism from the monoid of lists (under concatenation, with the empty list as the identity element) to the monoid of booleans under AND (with True as the identity)

this means that

all(concat(list1, list2)) = and(all(list1), all(list2))

or, in python,

all(a + b) = all(a) and all(b)

and, of course, all([]) = True!

the value here is that now you can reason about the all() of two lists by thinking about the all() of sublists, and the conditions required for a homomorphism guarantee that the empty list is not an edge case:

all([T, F]) = all([]) and all([T, F]) = all([T]) and all([F]) = ...

and that it doesn't matter how you cut up a list into sublists and what order you apply the concatenations in to reconstruct it

Nevermark3 yıl önce

I was referring to monad, as used in programming, as a transform that can be applied to the elements of a structure.

For instance, a transform that wraps each joining operator, in an expression tree, with a new operator that applies the original operator if all its inputs are defined, but returns a null if any input is null.

The expression tree structure hasn’t changed, but it now consistently (anvoiding error) responds to null values by propagating them.

In my example, a monad converts the list combining operation of concatenation into other list combining operations.

The result was that the identity of concatenation (the empty list) formed the basis for the new list operator’s identity.

—

Both concepts are indeed relevant.

A “monoid-to-aggregator” monad could convert 2-element operations into recursively applied list operations (which also return the single element for unitary lists, and the identity element for empty lists).

Then a structure of monoids processing pairs of values could be transformed into a structure that processes lists.

layer83 yıl önce

One corollary is that a zero-dimensional array has exactly one element, whereas a 1-dimensional array can have zero elements (can have length zero). It took me a while to wrap my head around this.

Nevermark3 yıl önce

Yes! Dimensions are multipliers on each other.

The cross points, over multiple points on segments in different dimensions is a product.

And the product across an empty list is 1.

The number of ways you can roll a dice “no” times is also 1.

Cross combinations of all kinds are products.

itishappy3 yıl önce

Whoah...

Does this imply there's a sixth of a way to unroll a dice?

rain13 yıl önce

I don't understand this. Please can you point me to information about it?

layer83 yıl önce

I haven’t seen this discussed anywhere else in terms of arrays, so I’ll elaborate here:

The number of elements in an n-dimensional array is the product of its n dimension sizes. For example, the number of elements in a two-dimensional 2x3 array is 6, because 2 x 3 = 6.

Consequently, the number of elements in a zero-dimensional array would be the empty product, which is 1 (as the root comment mentions).

Naively, one might think that removing a dimension from an array cannot increase the number of elements. For example, dropping a dimension from a 2x3 array reduces the number of elements from 6 to 2 (or 3, depending in which dimension you drop). But in the case of a zero-length 1-dimensional array (i.e. an empty list or empty vector), dropping the one dimension causes an element to be added, because a zero-dimensional array always has 1 element.

(This effect is not restricted to 1- and 0- dimensional arrays, by the way. If you admit zero-length dimensions, then you can also think of a 2x0 two-dimensional array, which would have zero elements, but dropping the zero-length dimension would result in a 1-dimensional array of length 2, increasing the element count by 2.)

The other maybe surprising part is that for all n > 0, you can have an n-dimensional array with zero elements by having at least one of the dimensions have length zero. But for a zero-dimensional array, it’s not possible for it to be empty, because it has no dimension whose length could be zero. This is somewhat counterintuitive at first, because one might have thought that a zero-dimensional array would be the canonical empty array, like how a point in space (whis is a zero-dimensional object) has no length/area/volume.

By the way, one could think of non-array values in a programming language to really be zero-dimensional array values, with their value being the singular element of the zero-dimensional array.

klysm3 yıl önce

> The identity element for the resistance sum across parallel resistors, is the infinite ohm resister.

I really like this example, because it has an intuitive physical analog and is more tangible than than the example I typically reach for: lists.

bjourne3 yıl önce

Continuing the same line or reasoning, for integers, max([]) should be -inf and min([]) should be +inf. For positive numbers max([]) should be 0 and min([]) should be +inf. But that's not how these operations are defined in most languages.

edflsafoiewq3 yıl önce

It's certainly how they're defined in math. In fact all is just min and any is just max over the poset {True, False} with True > False.

I think the reason we don't usually use those definitions is we like to maintain the fiction we're working with actual integers or reals, which don't have a min/max.

xigoi3 yıl önce

min and max are in fact defined this way in JavaScript.

slaymaker19073 yıl önce

You could also argue that any({}) is really not defined because first order logic generally excludes empty sets. The reason for said exclusion is because weird stuff starts to happen when you allow an empty domain when talking about if a formula is true in all domains. For example, "exists x, P(x) or !P(x)" is true for every domain unless you allow an empty domain since "exists x ..." is always false. The same is true of all({}) because you have an equivalent weirdness in the form of "!(forall x, P(x) and !P(x))". These seem innocuous, but there are many rules of inference that are excluded once you allow the empty domain.

schoen3 yıl önce

Maybe I'm too used to Coq's higher-order theory now, but I think it's not really that bad to say that we have to be careful about whether statements have existential import.

https://en.wikipedia.org/wiki/Syllogism#Existential_import

[deleted]3 yıl önce

Nevermark3 yıl önce

If we are defining ANY as an n-element LIST operator, in a programming language, which recursively applies the 2-operand AND taking literal Boolean values, there are no ambiguities.

Note that this is inherently a constructible relation, which avoids many pratfalls of more general mathematics.

But if ANY & ALL are being defined as general mathematical relations over all EXISTING members of a class (whose members’ construction, consistency or completeness, may be unknown or even unattainable), then there are other issues.

[deleted]3 yıl önce

manlobster3 yıl önce

Given:

    all(xs + ys) == (all(xs) and all(ys))

And:

    xs == xs + []

We have:

    all(xs) == all(xs + []) == all(xs) and all([])

Which implies:

    all([]) == True.

toxik3 yıl önce

I like this variant, it also works to show why any([]) is False.

Smaug1233 yıl önce

Although it's presumably much less controversional that `any([])` is false. After all, most people presumably think of an existential statement as being satisfied precisely when there's a witness to that statement, and of course an empty list contains no witnesses to any statement.

kccqzy3 yıl önce

"Any" is an existential quantification (what you mean by existential statement). "All" is a universal quantification. It can be vacuously true.

If this is controversial to any one at all, refer them to an introduction to logic course.

Smaug1233 yıl önce

There are logics in which vacuous truth is just not a thing (e.g. relevance logics). Your casual dismissal of the less common logics does not cause them not to exist.

tromp3 yıl önce

If all marbles in a bag are black, and you take one marble out, are all marbles in the bag still black?

The only logical answer is yes. It would be rather absurd to make an exception for the case where you start with one marble in the bag. That would make logical reasoning extremely cumbersome, for no benefit whatsoever.

dkarl3 yıl önce

Translating it to idiomatic natural language makes it less clear, because the natural language statement "all marbles in the bag are black" implies that there are marbles in the bag. The question is, why do we interpret it differently in a logical/mathematical context?

As with anything mathematical, we picked the way that yields useful and elegant mathematics. The notion of "all" would be awkward to work with if it did not apply to the empty set (bags without marbles) so we extended it in a way that is consistent with what it means over non-empty sets (bags with marbles.)

One very nice thing about this definition of "all" is that it gives this simple relationship between logical "all" and logical "none":

"for all x, P(x) is true" is equivalent to "there is no x for which P(x) is false"

I.e., if there is no marble in the bag that is not black, then all marbles in the bag are black... so to speak.

This yields elegant and useful mathematics, and (as you would expect) that tends to mean elegant and useful code as well.

For example, suppose you had an enormous dataset of records that included zip codes and wanted to know: "Are all the zip codes in this dataset in the continental United States?" One approach would be to split the data into smaller shards, answer the question for each shard, and "and" all the answers together. What if you chose a bad way of sharding the data and one of the shards was empty? What result would you want returned for that shard?

Someone3 yıl önce

An alternative way to see why that’s the most logical viewpoint is, that, if you assume not all marbles in an empty bag are black, you can have the following:

- Take a bag for which “all marbles in this bag are black” is false

- Add a black marble to that bag

- After that, “all marbles in the bag are black” becomes true

As is often the case in mathematics/logic [1] with these kind of things, you can hold an alternative view where “are all marbles in this bag black” doesn’t make sense for an empty bag or one where it has the answer “yo”, but if you do that, you’ll find that many proofs get more cumbersome because you have to handle that case differently from all other cases.

[1] other examples are the convention that 0⁰ = 1 and the convention that 1 isn’t a prime number (that’s an example where mathematicians (eventually) decided that having 3 kinds of positive integers (prime numbers, composite numbers, and 1) is the better choice)

marktani3 yıl önce

edit: totally misunderstood parent, my bad. disregard the following.

> - Take a bag for which “all marbles in this bag are black” is false

> - Add a black marble to that bag

> - After that, “all marbles in the bag are black” becomes true

This reasoning is not correct. If the bag contains exactly a red marble at the start, "all marbles in this bag are black" is false as you required, but it breaks the claim at the end that "all marbles in the bag are black".

There is in fact no bag that fulfills your reasoning, even the empty bag wouldn't (when starting to write my reply I had erroneously assumed so)

saurik3 yıl önce

If a bag contains exactly one red marble at the start then all marbles in this bag are black is in fact false, but when you throw in a black marble the value does NOT suddenly become true, as the red marble still exists, which is exactly the point of the scenario: adding a black marble to a bag where that claim is false shouldn't make the bag suddenly become true, and it still didn't in your example... it would, though, if the empty bag were defined to be false (which it should not be based on this argument).

marktani3 yıl önce

thanks, I see my misunderstanding now

dragonwriter3 yıl önce

If all marbles in a bag are black, and you take one marble out, are all marbles in the bag white?

The only logical answer is no. It would be rather absurd to make an exception for the case where you start with one marble in the bag... and yet:

  marbles = ["black"]
  marbles.pop()
  all(m=="white" for m in marbles) # => True

chongli3 yıl önce

The mistake you’re making here is by treating the statement “all marbles are white” as the negation of “all marbles are black” and claiming that this violates the law of the excluded middle.

But we are operating under predicate logic. The negation of “all marbles in the bag are black” is “there is a marble in the bag which is not black”. Then, clearly the latter statement is false in the case of an empty bag.

In fact, we can confidently claim falsity for any given statement of the form “there is a marble in the bag such that…” when the bag is empty. Therefore, by the law of the excluded middle, its negation is true, so statements of the form “all marbles in the bag are…” are vacuously true when the bag is empty.

VonGallifrey3 yıl önce

I don't think he was treating "all marbles are white" as the negation of "all marbles are black".

The comment he replied to was claiming that any question that is true for n = 1 should also be true for n = 0, but this comment shows that it is obvious nonsense.

The comment above basically claimed:

  marbles = ["black"]
  all(m=="black" for m in marbles) # => True
  marbles.pop()
  all(m=="black" for m in marbles) # => True

If that is the case then the following would also need to be true:

  all(m=="white" for m in marbles) # => True
  all(m=="green" for m in marbles) # => True

What color is the marble?

Just because the question “there is a marble in the bag such that…” is false does not mean you can just negate it and say “all marbles in the bag are…” if the actual answer is that the question is not applicable.

jayd163 yıl önce

Its interesting that "for all <is true?>" seems to imply a non-empty set, whereas "for any <is false?>" seems to not make the same implication.

It's certainly misleading in every day speech. On the bright side, all my papers have been published and all of my research funding has been granted.

Dylan168073 yıl önce

> "for any <is false?>"

What do you mean here?

"some element doesn't have the attribute" requires a non-empty set.

If you mean "it is false that some element has the attribute", then you need to write that very differently, which makes it much less of a surprise that it has different implications from the "all" statement.

bandyaboot3 yıl önce

Though it feels strange to write this, the fact that all the marbles are white doesn't change the fact that they're all black...and transparent, and not marbles at all, etc...

dragonwriter3 yıl önce

Right, my point was pointing out a weakness in the style of explanation—that the same structure can be applied with similar intuitive appeal to reject the behavior of all()—not to actually disagree with the correctness of all() in implementing universal quantification, or the correctness of the design that it should implement universal quantification.

p1mrx3 yıl önce

> If all marbles in a bag are black, and you take one marble out, are all marbles in the bag white?

The logical answer is "maybe."

Thiez3 yıl önce

Yes, you took out the last marble that wasn't white, and now all marbles that remain are white.

neves3 yıl önce

my pragmatic view is that it should be false.

A common error would be a programming mistake in the selection of the list element return an empty list. The returned list would, unexpectedly, comes empty. Trying to check if everything is black would return True and the code would follow on. It would be very hard to debug

Akronymus3 yıl önce

For the any predicate, you want to know if any element satisfies it, which of course, without any elements it can't be satisfied.

If you want the inverse behaviour, you have to verify that all elements do not satisfy it. And that necessarily results in the empty set being falsy on any, but truthy on all.

Also, its just easier to use .any to check if the set is empty or not, in many cases.

fasterik3 yıl önce

Your proposal would break all of logic and mathematics.

"All marbles in the bag are white" is equivalent to "For all x, if x is a marble and x is in the bag, then x is white". Since the antecedent is false if the bag is empty, the statement is true by material implication.

VonGallifrey3 yıl önce

Are those statements really the same?

"For all x, if x is a marble and x is in the bag, then x is white"

I would question if nothingness is a marble. Or would you say that the following statement is also true? I would say that x is a marble and therefore can be neither even or odd because it is not a number?

"For all x, if x is a marble and x is in the bag, then x is even"

That is just a nonsense question same as asking if all the non-existing marbles are of a particular color.

fasterik3 yıl önce

According to the rules of logic, we can always replace (P -> Q) with (~P v Q). In other words, if P is false then (P -> Q) is always true. This is known as a vacuous truth.

https://en.wikipedia.org/wiki/Vacuous_truth

Agreed, sometimes this leads to true statements that sound like nonsense. One example from the article is "if Tokyo is in France, then the Eiffel Tower is in Bolivia". This is a true statement because Tokyo is not in France.

>"For all x, if x is a marble and x is in the bag, then x is even"

We can rewrite this as "For all x, x is not a marble or x is not in the bag or x is even". We can see that this is true if "x is not in the bag" is true for all x. It's not really nonsense because we can quantify over all objects, so some of them will be marbles, some of them will be even, etc.

Going back to the more general question we can look at the statement "For all x, F(x)" where F is any predicate. Call this statement P. The negation ~P is equivalent to "There exists some x such that ~F(x)". But if we are quantifying over the empty set, ~P is false, so P must be true in that case.

VonGallifrey3 yıl önce

I think my problem here is that everyone just assumes an extra condition. The question "if Tokyo is in France, then the Eiffel Tower is in Bolivia" is not the same as "is the Eiffel Tower in Bolivia" and the statement of

  all(m=="white" for m in marbles)

is not the same as "For all x, if x is a marble and x is in the bag, then x is white". The statement is more "For all x in the bag, is x white?" and the answer to that is either "No, nothing is not white" or "Question is not applicable".

fasterik3 yıl önce

>"For all x, if x is a marble and x is in the bag, then x is white". The statement is more "For all x in the bag, is x white?"

They're the same, just quantifying over different sets. I can quantify over objects in the universe, in which case I need the clause about being in the bag. Or I can quantify over objects in the bag, in which case I'm quantifying over the empty set.

all(m=="white" for m in marbles)

By De Morgan's laws, this is equivalent to

not any(m != "white" for m in marbles)

If you want all(m=="white" for m in marbles) to evaluate to False for the empty set, then any(m != "white" for m in marbles) has to evaluate to True for the empty set, or you have to give up on De Morgan's laws.

This is how standard first-order logic works. Again, you're welcome to try to make your own system of logic that works differently, but good luck doing that while preserving all of our theorems in set theory and mathematics.

[deleted]3 yıl önce

hoosieree3 yıl önce

A man walks into a shop and asks, "You wouldn't happen to have any fish, would you?" The shop assistant replies, "You've got it wrong – ours is a butcher's shop. We don't have any meat. You're looking for the fish shop across the road. There they don't have any fish!"

schubart3 yıl önce

“I’d like a coffee, please. Without milk.”

“Apologies, we’re out of milk. Could I offer you a coffee without sugar instead?”

NoThisIsMe3 yıl önce

That's not the question. The question is: If there are no marbles in a bag, are all marbles in the bag black?

twiceaday3 yıl önce

Sounds weird when you ask the question that way, but if you ask "is there a non-black marble in the bag?" the answer is clearly no. So the question is more like: Should "all marbles in the bag are black" be exactly equal to "not(is there a non-black marble in the bag)".

Smaug1233 yıl önce

I think you've misunderstood. The question you posed has an answer implied by the parent's question with n=1.

SkyPuncher3 yıl önce

The answer should be no. Though, it’s understandably ambiguous.

Black is a property of a marble. Without a marble, black cannot evaluate to true. Therefore zero marbles equals “no”

feoren3 yıl önce

All cell phones must be turned off before the movie will begin.

Oh wait, nobody in the audience has a cell phone. Can the movie begin?

> Without a marble, black cannot evaluate to true. Therefore zero marbles equals “no”

"Is_Black" cannot evaluate to false either, therefore zero marbles equals "yes". But that's wrong too, because it is never evaluated, because there are no marbles to evaluate it on. TRUE is the identity of AND, and ALL is the aggregation of AND, so ALL([]) == TRUE. Put another way:

If you start from a bag with N black marbles and split it up between M bags, can you say that for each new bag, all the marbles in it must be black? Yes, you can. That is, if you find a marble in the bag, it will be black. This still holds even if one bag doesn't happen to get any marbles.

kaashif3 yıl önce

> All cell phones must be turned off before the movie will begin.

> Oh wait, nobody in the audience has a cell phone. Can the movie begin?

That's a really good one. Admittedly, I've never had to actually explain why statements can be vacuously true to anyone. But I'll keep this in mind if I ever have to.

pharrington3 yıl önce

There are zero marbles. All zero of the marbles are black. All zero of the marbles are white. There are zero marbles.

kstrauser3 yıl önce

Alternatively, there are no marbles that are not black.

fasterik3 yıl önce

Your proposal would break all of logic and mathematics.

"All marbles in the bag are black" is equivalent to "For all x, if x is a marble and x is in the bag, then x is black". Since the antecedent is false if the bag is empty, the statement is true by material implication.

jayd163 yıl önce

Isn't this like complaining about division by zero? Why make an exception? Well...because its exceptional.

So it's consistent to say that a bag can contain all red and all black marbles at the same time?

Eldt3 yıl önce

That's not an exception, that's a different situation...

cedilla3 yıl önce

Is it?

If that case is so different, than the case with two marbles is also different - because removing the second-to-last marble will change will change the bag to be in that situation. But then, the case with three marbles is also different, and by induction you are left with only special cases.

On the other hand, see the related statement "If all marbles in a bag are black, adding a red marble will result in a mixed bag" clearly fails for the empty bag.

This isn't really a question of logic or mathematics. Mathematicians just use systems which are useful. And predicate logic, which has proven invaluable, would allow OP's claim.

pixl973 yıl önce

Eh, wouldn't the induction reduce to 0, 1, infinity?

jackbrookes3 yıl önce

not really

    marbles = (BlackMarble() for _ in range(random.randint(0, 10)))
    all(isinstance(m, BlackMarble) for m in marbles)

Surely should always be true

Salgat3 yıl önce

"all" and "none" are simultaneously true, which makes this a tricky edge case that needs to be explicitly accounted for.

dragonwriter3 yıl önce

Its necessary that all and none are both true of empty lists, if they are both defined for empty lists, because otherwise the invariant that all(xs) == none(not x for x in xs) [0] would not hold.

[0] yes, “none()” doesn’t actually exist in Python, but we can imagine that it did, and see that if it did, it should have this relationship.)

bandyaboot3 yıl önce

Ultimately I agree with the conclusion, but the logic of how you're getting there seems flawed in that the question you're asking doesn't add any value. The fundamental question is whether all marbles in a bag of n black marbles are black for all values of n including 0. If the answer to that question is yes, then the answer to your question is yes. If the answer is no, then the answer to your question is "yes except if it results in n=0".

saurik3 yıl önce

The point was (explicitly) that it would be awkward to add the n=1->0 corner case.

bowsamic3 yıl önce

> If all marbles in a bag are black, and you take one marble out, are all marbles in the bag still black?

> The only logical answer is yes.

The only "logical answer" is "there are no marbles in the bag". If this must be cast to a boolean somehow, the only "logical answer" is no. There should be a discontinuity as the last black marble is removed. That isn't absurd at all

jimmaswell3 yıl önce

Look into formal boolean logic, specifically the "therefore" operator. (T->T)=T,(T->F)=F, but starting with a false premise always results in true. There's good reason for it and it makes other things work out how you'd expect.

A marble is in the bag -> the marble is black = True, even if there are no marbles in the bag. You can consider the "all" method as asking for the truth value of "A marble is in the bag -> the marble is black"

bowsamic3 yıl önce

Why should I consider the all function to be like that, rather than actually answering the question “are all the marbles black”?

Also, why am I getting downvoted? I’m starting to realise that HN is not the place to come for intellectual discussion anymore if you have anything to say that isn’t immediate agreement. I guess dang has set a flag on my account that encourages others to downvote me, because I’m not sure what other explanation there is for how my comments have been treated recently

shadowgovt3 yıl önce

With deepest respect: I can't speak to any other comments you've made, but on this thread the downvotes are almost certainly because you've stepped into a philosophical debate that has gone on for over 2,000 years in Western philosophy and more-or-less asserted "If this must be cast to a boolean somehow, the only 'logical answer' is no." I believe the community is interpreting that as a bit dismissive both of the contents of the post and philosophy in general; one of the field's goals is to get past what we feel ought to be the answer to establish some kind of framework where that must be the answer, and your assertion is a bit dismissive of the other viewpoint (which, FWIW, happens to be the modern orthodoxy; IIUC your preferred answer is the old orthodoxy that leads to logical paradoxes and has therefore been put on the shelf as less useful).

8note3 yıl önce

You could define an alternative All where where it means (at least one is true) && (for each n, n is true)

But is it useful?

Suppose I'm a bus driver and I ask "all aboard?"

I'd expect that if the answer is false, I'm missing somebody, and not that the bus is empty

stOneskull3 yıl önce

i think it's a 'black marble bag'. you want to make sure it only ever has black marbles in it. so you do checks on it.. does the bag only contain black marbles? you want to check there's no non-black marbles.

wan233 yıl önce

Without knowing how many marbles are in the bag, if you say that not all the marbles in the bag are black, then I'm going to ask you to show me a non-black marble to prove it. Alternatively, I can prove that all the marbles are black by showing you n marbles that are black where n is the number of marbles in the bag. Here you go, zero black marbles!

whoopdedo3 yıl önce

    def all(L):
        for i in L:
            if not L:
                return False
        return True

Seems quite clear when presented that way. Same with `any`.

> In logic, this is called the principle of bivalence: there are only two values that a proposition can have, true or false. But Python has None, many other programming languages have null or nil, and Zen has mu. Maybe adding another value would help?

If `all` were in Python v1 it would have thrown an exception when called with an empty list. (Said jokingly, or is it?)

dragonwriter3 yıl önce

Yes, that's an implementation of all() that produces the current result.

What the article explains is why the thing that produces the current result has the name “all()”.

While both can be answers to different senses of “Why does all() behave the way it does?”, they are fundamentally answers to very different questions that English, being ambiguous in the way natural language tends to be, allows to be expressed in the same words, the implementation explanation is not a clearer answer to the same question answered by the examination of the history of philosophy and predicate logic, and presenting it as if it were is fundamentally misunderstanding the question being answered by the longer piece.

ajross3 yıl önce

This is the essence of the issue. All the pontification about (sigh) periods of western logic is missing the point.

The object isn't question isn't a statement of philosophical logic[1]. It's a computer program. And, yeah, it's implemented by iterating over the list and returning false if it finds anything false. If it gets to the end, it returns true. And that is all that needs to be said, because it is an algorithm and not a statement about the world. Maybe it's wrong. In which case, file a bug. But the bug isn't about philosophy either, it's about "I want to solve a problem and all() is giving me the wrong answer".

[1] Not to be confused with actual mathematics, of course. Math doesn't have semantic arguments like this because it starts from a stance of defining terms and axioms such that no one gets confused over words. Sigh, again.

cpgxiii3 yıl önce

This and the parent are mistaking the "how" all([]) is True for the why. The code is the "how", but it doesn't just exist. It could just as easily end in

  return len(L) > 0

instead, which would obviously have different behavior. The code is the embodiment of a particular design, the "why", which has a more complex history.

ajross3 yıl önce

There's no treatment about any "complex history of the design of all()" though. The article is a bunch of nattering about philosophical semantics.

And I'm saying that's just plain dumb. This is an engineering discipline. If there's a "why", then the author of the code is the resource, not (sigh) philosophers. Go ask Guido, or check the commit messages. Don't ask Aristotle, he can't hack.

And the proof (that's right, proof) that I'm right is this: imagine Guido (or whoever) had indeed chosen the opposite convention for all(). It's easy to imagine. And it's equally easy to imagine people getting confused about it and asking about it. And you could reply with exactly this same article trying to explain the "why" behind it as part of two traditions of philosophy.

That's right: the same words explain the opposite convention too. That's not an explanation for "why", is it? This whole discussion is QUITE LITERALLY providing zero insight into the question you're imagining it's answering! It's like asking someone "Why did you paint your house blue?", and them answering "Well, you see, I could have painted it blue, or red."

empath753 yıl önce

"All" as the way it is _because_ it's an implementation of the following logical statement:

For all x in X, P(x)

It's not arbitrary, and understanding formal logic and the history of formal logic is a good basis for understanding a great many things in computer science.

ajross3 yıl önce

And I sigh for a third time. This is emphatically not about "formal logic", it's philosophy. If you want to argue from programming language type theory about the best/right/proper/whatever way to implement set theoretic predicates in python, I'm here for it. If you want to do it by citing Aristotle, my eyes start rolling.

Buttons8403 yıl önce

We could have just used: all(L) if L else True

kubb3 yıl önce

Every one (all) of the set of zero elements is true. It's not counterintuitive or inconsistent, this is the only way that makes sense.

The complement is also consistent. None of the set of zero elements are true. So there aren't any true's.

They're symmetrical cases, and negation turns them into each other. Not-any-true is equivalent to all-false, and not-all-true is equivalent to any-false.

neuromanser3 yıl önce

> In logic, this is called the principle of bivalence: there are only two values that a proposition can have, true or false. But Python has None, many other programming languages have null or nil, and Zen has mu. Maybe adding another value would help?

Hoare labeled his invention of null a "billion dollar mistake". SQL NULL can't be far behind. Boolean logic has 4 unary and 16 binary operators, ternary logic has 27 and 19683, respectively. That's not helpful, that's intractable!

I cannot recommend C. J. Date's books enough.

jewel3 yıl önce

> SQL NULL can't be far behind.

SQL's NULL is far more useful though, since NULL != NULL. That lets you do things like join two tables with a column and not have the NULLs match.

Consider, for example:

    select * from users where id = null;

That will give 0 results, even if somehow you have a user with a null id.

It's also really nice for non-ID, non-reference fields to represent N/A. For example, user.birthdate can be NULL if the birthdate is not known.

SQL also lets you choose when you want NULL to be allowed for a column, so it's less likely to be a gotcha.

neuromanser3 yıl önce

> SQL's NULL is far more useful though, since NULL != NULL.

That's not true! (Nor is it false.) NULL = NULL IS NULL, NULL != NULL IS NULL. I can't overstate this: as soon as either (or both) operand of any binary relational operator is NULL, the whole expression is NULL!

I'm not being an asshole, this is the exact mistake that makes SQL NULL the other billion dollar sink!

This is really funny, because i wasn't aware of laying such a beatiful trap.

Karellen3 yıl önce

> as soon as either (or both) operand of any binary relational operator is NULL, the whole expression is NULL!

Isn't is a binary operator?

Because "NULL is NULL" is True (not NULL).

neuromanser3 yıl önce

No, IS NULL is an unfortunately named unary postfix operator.

jerf3 yıl önce

SQL NULL has to be the quintessential example of why programming can't just blindly follow math. The NULL truth table makes all the sense in the world in a mathematical context.. and it is a total pain to program with. Letting NULL == NULL be "true" and NULL == anything else be "false" might be slightly less principled, but it would be soooo much safer and have prevent so very many bugs.

(And it's not like that's some sort of mathematical nonsense either. It makes perfect sense to not create a special value that represent "outside my universe of values" and then refuse to equate any two of them. It makes perfect sense to declare a distinguished "outside my universe of values" and let it be equal to any other such value on the grounds that it is mathematically impossible to witness any differences between them anyhow so within the system they are indeed equal.)

maxbond3 yıl önce

Let's say we're in a situation like this:

    create table people (
        name text primary key,
        age integer
    );
    insert into people (name, age) values ('Bob', 50), ('Alice', null), ('Mallory', null);

We know Bob is 50, but we don't know the age of Alice or Mallory.

Are Bob and Alice the same age? We don't know.

Are Alice and Mallory the same age? We don't know.

If `null` were equal to `null,` we couldn't express missing information like this. Naive queries would still have bugs and conclude that Alice and Mallory were the same age.

Null is a property of living in an uncertain universe. When you start taking measurements of the real world (which every production business process is), you run into the many faces of null.

For example, I used to take data in a lab. Often we'd measure three replica samples. Sometimes I'd spill one of them. Scientific ethics demand I still write down the two measurements I did collect, even if I go get three more samples. For the third, I'd write the pen and paper equivalent of null (striking out that cell in the table).

Were any two of those missing measurements equal? Does a dog have Buddha nature?

vlovich1233 yıl önce

I think the mistake here was the name chosen. The NaN concept from floating point has an identical definition and behavior, so calling it something like NaV (not a value) or undefined (similar but not identical behavior in JS) instead might have caused less confusion vs NULL typically having a definition of an implicit Option<T>

jerf3 yıl önce

I addressed all of that in advance of your posting. We live with the equivalent `null == null` in plenty of other contexts, and not only does it not blow up, it in fact works better and has fewer bugs. It isn't even as if math demands this; it is merely one choice and one that is observably a mistake.

maxbond3 yıl önce

I disagree that it's an arbitrary choice, it's asserting statements as true which we don't know anything about. I also disagree that there is such a distinction between a "mathematical context" and a "programming context" here - what we're talking about is formal logic (rather than proper math), and programming is an application of formal logic. Indeed, that's why we're here in the first place, to discuss how any() and all() arise from set theory and predicate logic.

I don't know what systems you're referring to, but like I mentioned you will get bugs if you naively use either approach. Eg in Rust, Option<T>::None will compare equal, because Rust doesn't have a null concept and that's how Rust enums work. But if you were using None to represent missing information, you'd want to use pattern matching rather than the built in equality. (Missing information is a much less salient concept in Rust than SQL, and Rust very deliberately wanted to avoid having a language-level null concept, so I think both of them made the right choices for their problem domains. Though I agree with this comment[1].)

But I'm getting the vibe that we're not going to convince one another, which is fine, this is an area where reasonable people disagree.

[1] https://news.ycombinator.com/item?id=37271039

maxbond3 yıl önce

> and that's how Rust enums work

It shows that I haven't written Rust in a few months, that's not how Rust enums work, that's how the derive macro for PartialEq/Eq works. D'oh!

Too3 yıl önce

Similar to undefined in javascript. (undefined == anything) is always false, even if anything also happen to be undefined.

vlovich1233 yıl önce

undefined === undefined is true which is not true for SQL NULL.

Too3 yıl önce

Sorry I must have mixed up something. Even == returns true after quick test.

tomp3 yıl önce

For anyone wondering how to fix the above query so that it works for arbitrary X (which can be NULL or non-NULL):

    SELECT * FROM users WHERE status IS NOT DISTINCT FROM $x

neuromanser3 yıl önce

> Consider, for example: > select * from users where id = null; > That will give 0 results, even if somehow you have a user with a null id.

Why is it useful? Can you elaborate?

maxbond3 yıl önce

Not GP, but let's say that null in the query wasn't a literal but was the result of another query that returned null. Let's say that the query returned null because not user existed who met the criteria specified by the query, but because we were doing a complex join or aggregation or something, we didn't simply get back 0 rows.

In that case it would be a bug if we matched with this errant user who's id is null.

Smaug1233 yıl önce

The mistake of `null` is _not_ that it exists at all - it's often the case that you can't answer a question, and it's extremely useful to be able to model your inability to answer a question! The mistake of `null` is instead that it forces every reference type to be an optional. This is a mistake because some things can in fact be known. In practice, when everything is optional, it's so boilerplate-heavy to enforce the condition "this is known" at runtime for every property that everyone inevitably ends up not enforcing that condition most of the time; the bugs arise when one side of a boundary assumes for expediency that the other side has enforced it.

It is in general very reasonable for a function to return an optional bool; think of `List.tryHead [false, true, false]`. What is unreasonable is for all boolean functions to return optional bools.

edflsafoiewq3 yıl önce

  all = foldr and True
  any = foldr or False

hiAndrewQuinn3 yıl önce

So glad I know this language

xcdzvyn3 yıl önce

Man I love Haskell.

billpg3 yıl önce

I posted in a political thread once...

"Re-joining the EU would give the UK all the benefits of EU membership as well as all the benefits of Brexit too."

gizajob3 yıl önce

True

waffletower3 yıl önce

I miss using the Midje testing library for Clojure, as it has the 'truthy' and 'falsey' functions. It reduced these variously bivalent and trivalent conditions into binary in a way that would do Stephen Colbert proud (https://web.archive.org/web/20150121223555/http://www.merria...) Of course you or I can add such to what ever language we are using that supports actual functions -- or smash some abstraction of truthiness into those that don't.

feoren3 yıl önce

Humans have trouble with this because our brains cannot let go of the context surrounding a question. For example, a logician may find it funny to walk up to a police officer and say "all of the hookers in my trunk are dead." That is technically true, even though there are no bodies in his trunk. But the brain of the police officer is awash with why someone would be talking about dead hookers at all. Surely something is going on! I would not expect that logician to have a great day.

So we read things about bags with no marbles and bearded kings of France and pink goblins and we think someone is taking the piss out of us, because we can't let go of the context behind those statements. Why are we talking about goblins at all?

All models are wrong. Some models are useful. If you're getting hung up on how it just doesn't make sense that "A -> B" is always true when A is false (which is really the same issue), you have to realize that it's not meant to be intuitive, it's meant to be useful. And the theory of predicate logic where ALL([]) == TRUE is much more useful than the one where it's FALSE or even NULL. It's more useful because TRUE is the identity element of the monoid AND and ALL is the unary set-aggregation of AND. There really cannot be any other choice if you want your theory to fit in with the rest of mathematics and logic, which a useful theory must. It's internally consistent, useful, and really does make deep sense if you are able to let go of context-laden real-world examples.

You should not rely on English sentences making sense to be a good metric of whether a model is useful or not. Consider:

    Dogs must be carried on escalators.

You don't have a dog. Are you allowed on the escalator? Of course you are. This is, in fact, a perfect example of why Your_Dogs.All(is_carried) must be TRUE if Your_Dogs is empty.

    Hard hats must be worn in work areas.

You don't have a hard hat. Are you allowed in the work area? No! How can you tell the difference between these two situations? Only from context. Yet you can see how easy it would be to form the 2nd sentence as an (erroneous) example of "Enforce(HardHats.All(are_worn))", but it's not that. It's more like "Enforce(People.Where(in_work_areas).All(have_hard_hat_on))" -- if there is someone in a work area, then they must have a hard hat on. But if there's nobody in the work area, no rule is being broken! Again we actually see ANY([]) having to be true here.

When you come up with weird-sounding examples where you're sure All([]) must be False, you're just poisoning your intuition with unhelpful context.

msie3 yıl önce

I'm studying this comment many times. I do have a hang up with A->B being true when A is false.

Nevermark3 yıl önce

A->B, given A is False, simplifies to:

False->A

Since in this implication, we are starting from a false assumption, we have already left the guardrails of consistency. So we can say whatever we want.

False -> A

False -> not A, as well!

The simplest way to look at it is, having a false assumption is the same thing as saying:

Assume contradictions, then …

Or,

Assume (False = True), then …

Given a false assumption, anything can be implied.

Because if False equals True, then whether A is True or False, it is also the other.

—-

To take the antipode of feoren’s prosaic warnings against colorful context, let’s pile on context like it’s cake!

If we start in a false world, if the physics we live in are already a contradiction, then anything can happen!

Several impossible things before breakfast! Alice and wonderland!

You can have your cake (C) and eat it (not C) too!

msie3 yıl önce

Thanks

aportnoy3 yıl önce

1 is the multiplicative identity

0 is the additive identity

all([]) is True

any([]) is False

cheald3 yıl önce

It helps to think in terms of `any` first:

  any([], predicate) => false

This is plainly obvious, because it is illogical to say "the predicate is true for at least one member of the empty set".

If we can agree on that, then all([], predicate) must be true, because the complement of all(list, predicate) is any(list, predicate')

The naive assumption is that the complement of all(list, p) is all(list, p'), but this is demonstrably false, because in the case of an empty list: all([], e => e) and all([], e => !e) would both return the same value.

    > [[], [true], [false]].map(s => s.every(e => e) == !s.every(e => !e))
    [ false, true, true ]

Instead, its proper complement is any(list, p'), which means that all(list, p) = !any(list, p')

    > [[], [true], [false]].map(s => s.every(e => e) == !s.some(e => !e))
    [ true, true, true ]

So, for all([], p) to be false, any([], p') would have to be true, which makes even less sense than all([], p) => true.

kazinator3 yıl önce

If you have some set S and predicate P(x) is true for every x in S, ∀x∈S:P(x), then you can partition the set into pieces S₁ ∪ S₂ ∪ ... u Sₙ. such that ∀x∈S₁:P(x) ∧ ∀x∈S₂:P(x) ∧ ... ∧ ∀x∈Sₙ:P(x).

If the quantified predicate were to be false for an empty set, then the above breaks if any of the partitions are empty. A property can then be true when quantified over a set such that it's not true over subsets, which is inconsistent.

A similar problem occurs with products. We can use Lisp:

  (* 2 3 4) -> 24

We would like to be partition that into partial products. Here, we have a partition of length 1:

  (* (* 2 3) (* 4)) -> 24

So we want (* N) -> N. And empty partitions:

  (* (*) (* 2 3) (*) (* 4))  -> 24

For that to work we need:

  (*) -> 1

dylan6043 yıl önce

In any discussion on languages like this, I feel the Wat discussion is always appropriate: https://www.destroyallsoftware.com/talks/wat

H8crilA3 yıl önce

This video is over 10 years old. I felt very old all of a sudden. (BTW, it's hilarious, go watch it)

mabbo3 yıl önce

I think a key point is that (correct me if I'm wrong here) in predicate logic you can rewrite

   ∀x Fx

   Not ∃x (not Fx)

Ie: "for all x, f(x)" implies the opposite of "there exists an x where not F(x)".

People seem to have less of a problem with

   Not ∃x (not Fx)

when the universe is x is empty.

I usually explain it to junior developers by telling them to imagine it's a for loop over a list that returns true/false if it finds a value that doesn't match what's expected, and the opposite of it reaches the end of the list.

shadowgovt3 yıl önce

FTA:

> But it is interesting how even extremely practical twenty-first century programming can get drawn into millennia old philosophical controversies, intentionally or not.

This turns out to happen a lot. I can't find the source right now, but there was a good essay I read ages ago about how questions that are abstract and hand-waveable in day-to-day life become cornerstones of architecture rapidly in computer science and software engineering. The cow in the field epistemological puzzle [http://www.philosophical-investigations.org/2021/09/the-cow-...] maps directly to the nature of proving code is "correct" by testing (and any practicing coder has a story of false-positive or false-negative tests, as well as times they identified one of those by a "gut check" telling them "That result... doesn't feel right; I should investigate further"). Similarly, the philosophical question of "sameness" or "equality" ends up concretized over and over again in language design; there's a reason languages end up with so many ways to say 'equals', and it's because the underlying question of what it means for two things to be the same thing is legitimately philosophically complicated!

earthboundkid3 yıl önce

Here’s a real Gettier question from my actual life:

In college, my future ex-wife rented a video from the video store called “Kama Sutra” on my card and returned it late. The late fee was sent to my parents’ house. My dad discreetly told me later that it was not a problem that we got a late fee, which means he read the letter and thinks we had watched a porno together and was trying to let me know and be cool about it.

However, https://en.wikipedia.org/wiki/Kama_Sutra:_A_Tale_of_Love is a “historical erotic romance film” and not a porno. But my ex-wife and I did in fact see a different porno together.

So then, does my dad know that we saw a porno together?

adameasterling3 yıl önce

I had to deal with this problem in our product, which has a visual programming language. I opted to throw an exception if, for whatever reason, "all()" receives an empty list! I had forgotten I'd done that. There's no explanation for it in the code.

As I sit here justifying my own reasoning, though, it sort of makes sense. For ordinary people (for whom this product is supposed to be for), I figure if they put in nothing, that was probably just a mistake.

the-alchemist3 yıl önce

Clojure does the same thing:

  > clj                                                                                                                                                           
  Clojure 1.11.1
  user=> (every? true? [])
  true
  user=> (every? false? [])
  true
  user=> (every? true? nil)
  true
  user=>

Also:

  user=> (true? [])
  false

In English, an empty list is `false`, but any predicate on an empty list is `true`.

So I believe the logic is the same as Python.

Logic article on this in Wikipedia: https://en.wikipedia.org/wiki/Vacuous_truth

junon3 yıl önce

I remember explaining this rather simply, the same question actually. Look at the implementation.

    def all(it):
      for v in it:
        if not v:
          return False
      return True

If there are no items, it returns True.

    def any(it):
      for v in it:
        if v:
          return True
      return False

If there are no items, it returns False.

There's no need for fancy mathematical or "marbles in a bag" explanations here. Just look at the code.

ptx3 yıl önce

> in the new logic, you can’t soundly argue that “all dogs are mammals; all mammals have fur; therefore, all dogs have fur” because one person shaving their dog suddenly makes “all mammals have fur” untrue.

Isn't this just a problem with an unclear definition of "having fur"? Is the article saying that the old logic would hand-wave this problem away because it's about "universals and essences"?

earthboundkid3 yıl önce

Yes. “All dogs have fur” is untrue. “Dogs have fur” is true. The former is modern; the latter is classical.

gouggoug3 yıl önce

I'm a bit confused by this:

> “All stonemen are made of stone” is true by definition, but “no men are made of stone” is also true and seems to contradict it.

I don't see how “no men are made of stone” contradicts “All stonemen are made of stone”.

"stonemen" are not the same as "men".

English isn't my first language so maybe I don't know what a stoneman is (and google failed me), but I assumed it is a statue?

Smaug1233 yıl önce

The originator of that quote was writing in the 12th century. The quote is cited without a source at https://en.wikipedia.org/wiki/Square_of_opposition , where the phrase is "Omnis homo qui lapis est" ("every man who is a stone"). I haven't dug any further than that. But the phrase literally is intended to indicate a contradiction.

Jtsummers3 yıl önce

A stoneman would be a man made of stone, not a stone shaped like a man.

It comes down to a philosophy of logic issue. A universal quantifier ("for all x P(x)") is ambiguous when there are no x's. You can take it as false, true, or indeterminant, your system of logic will determine which interpretation should be used.

In modern predicate logic, that statement is true if there are no x's. In syllogistic logic it's considered false because there's a second presumption which must be satisfied: That there are any x's to talk about.

ptx3 yıl önce

Shouldn't this question fail at the parsing stage then, before it has even been asked?

  Q: All stonemen are ...

  A: ERROR: Undefined operation. Stonemen do not exist.

Jtsummers3 yıl önce

That's certainly one option. In a way, that's what the colloquial understanding of the expression would entail.

In colloquial use if you were to say, "All unicorns are blue" no one can meaningfully contradict nor confirm the statement, the statement is neither true nor false because there are no unicorns (this all assumes we're not discussing in a context where unicorns "exist", like about a particular fantasy setting or animated series). In syllogistic logic it becomes false because of the foundation of that logic (centered on reality, what exists and can be defined, not on fiction). Nothing true can be said about all of some non-existent thing because, well, it doesn't exist, so the statement must be false. In modern predicate logic it's considered true, because even though there are no unicorns we (someone) decided that it should be true by convention when the set is empty (turns out to have useful properties if we permit this).

These are just the rules that we've used for our logic, a choice we made. We're generally, in programming, operating under the modern logical rules, using neither colloquial rules nor syllogistic rules, so our programs are consistent with that last interpretation.

assbuttbuttass3 yıl önce

I'm guessing, a stoneman means a man made out of stone

nighthawk4543 yıl önce

claims on empty sets can be vacuously true.

"All elephants in my pocket are made of dark matter". Sure, all _zero_ of them, so it's 'technically correct'.

https://en.wikipedia.org/wiki/Vacuous_truth?useskin=vector

aftbit3 yıl önce

Sorry for the meta comment, but ?useskin=vector is game changing. I thought I had just lost the old readable Wikipedia.

nighthawk4543 yıl önce

There's actually 5 skins! If you sign in you can also set your preferred skin in preferences. Check them out below:

https://en.wikipedia.org/wiki/Wikipedia:Skin?useskin=vector

https://en.wikipedia.org/wiki/Wikipedia:Skin?useskin=vector-...

https://en.wikipedia.org/wiki/Wikipedia:Skin?useskin=monoboo...

https://en.wikipedia.org/wiki/Wikipedia:Skin?useskin=timeles...

https://en.wikipedia.org/wiki/Wikipedia:Skin?useskin=minerva

Akronymus3 yıl önce

Not the gp: I have redirector with a regex url rewriter that gets me the skin on all wiki pages. (it is somewhat complex, due to anchors and such) Writing this comment so that I can find it again later so I can post it here, if yoou want to have it.

devmunchies3 yıl önce

I actually used this in my F# code yesterday. The forall function does the same and it was exactly what I needed.

https://fsharp.github.io/fsharp-core-docs/reference/fsharp-c...

rickboyce3 yıl önce

I think the analysis is really interesting, but I suspect it’s quite possible that this behaviour is just a result of optimising the implementation than GVR taking sides in a 2,500 year old philosophical debate.

Both implementations of all() and any() short-circuit by returning as soon as a fasly element in all or a truthy element in any is iterated over.

The origin of these two functions seems to be this post: https://www.artima.com/forums/flat.jsp?forum=106&thread=9819...

Guido makes no comment on empty iterables, but does comment on the final implementation needing to be efficient. It’s possible this behaviour is just the engineering trade off made for a slightly more efficient implementation.

The initial commit of these two functions - https://github.com/python/cpython/commit/96229b191814556622b... - is exactly as Guido’s suggestion, but does include a test case for empty iterables for both functions so we know it wasn’t overlooked.

mrkeen3 yıl önce

I like `all = foldr and True` as others have pointed out.

But I think I have a more convincing example of why it can't be the other way around:

    all (>5) [6,7,8]
    all (>5) ([6,7,8] ++ [])
    (all (>5) [6,7,8]) && (all (>5) [])
    (True              && False)
    False

travisjungroth3 yıl önce

Think often when people want/expect this to be false, they’re combining two checks: that there’s an item and all items are true. This covers doing an operation on “ready” items. Instead:

    if items and all(items):

aib3 yıl önce

It's the identity element of the monoid, no?

Similarly, the product of an empty list should be 1.

justin_oaks3 yıl önce

Regardless of whether you thing the return value should be True or False, this behavior violates the Principle of Least Astonishment [0] for a significant number of people.

Such violations in software inevitably lead to bugs that could have been avoided. The real question in my mind isn't what the return value should be. The question is "How can this problem be wholly avoided?"

Some have suggested requiring a default return value when the iterator argument is empty. Others have suggested throwing an error. Perhaps others will suggest the all() function shouldn't exist, although that may be throwing the baby out with the bathwater.

[0] https://en.wikipedia.org/wiki/Principle_of_least_astonishmen...

kstrauser3 yıl önce

I disagree.

If

  lst = [True, True]; all(lst) is True

is True, and

  lst = [True]; all(lst) is True

is True, I'd be very surprised by

  lst = []; all(lst) is False

Basically, all(lst) is the same as `not any(not item for item in lst)`. If we inverted the value of `all([])`, I'd argue that we'd also have to invert the value of `any([])`, which today evaluates as False. `any([]) is True` would be beyond bizarre to me.

H8crilA3 yıl önce

What's an example realistic problem/piece of code that could be buggy because of this definition of all()?

rain13 yıl önce

The people that are astonished by this just need to learn why.

It's not the function that is wrong, it's those people.

justincredible3 yıl önce

michaelteter3 yıl önce

The problem isn't with all([]) -> True, the problem is the if [] -> False.

[] exists. It happens to be empty, but it is neither a False nor a None. Therefore it should be a True if applying truthiness to it. IMO, any expression which does not result in an actual False or None should be judged as True.

- edit -

On second thought, all([]) -> True is also a poor choice, same in Ruby. The idea of judging an empty collection as having all items being any value is flawed, since there are no items to measure. It is on par with 1 / 0.

This is fun: in both Ruby and Python...

[].all? -> true

all([]) -> True

[].any? -> false

any([]) -> False

So both languages agree that all elements of any empty collection are true, but if you ask them if any of the elements are true, they deny it. So they are all true while also not having any true elements.

Delk3 yıl önce

> The idea of judging an empty collection as having all items being any value is flawed, since there are no items to measure. It is on par with 1 / 0.

Not really. Those Python functions follow definitions from set theory and predicate logic, and in predicate logic e.g. "for all x, P(x)" is defined as being true if there are no x.

The reason for it being defined that way in mathematics is that it actually leads to consistent rules and definitions without the need to define lots of special cases, even if some of those definitions aren't how most people would use some of the same words in everyday language.

Similarly, the reason division by zero is considered undefined instead of e.g. equaling infinity is that if it were not considering undefined, that would lead to inconsistency. If we had 1 / 0 = a, with any valid result a, that would mean a * 0 would need to equal 1.

Programming languages could of course define their APIs to follow some other (hopefully internally consistent) logic, and I guess you could consider mathematical definitions based on predicate logic or set theory as being a somewhat arbitrary choice. But I disagree that the definition used in Python is on par with division by zero.

kstrauser3 yıl önce

I disagree. An empty string is False. Any empty set is False. An empty dict is False. Basically, in Python emptiness implies falseness. This has practical benefits:

  users = database.fetch_users()
  if not users:
      print("Didn't find anyone.")

and

  name = input()
  if not name:
      print("You didn't enter a name.")

Of course you could work around those like `if len(users) == 0` or `if not len(users)` or `if name != ""`, but each of those is uglier.

`if not users` translates very nicely to English: "if there are not any users...". I'm glad Python defined `bool(list)` that way.

robot_no_4213 yıl önce

I'm a Python dev who uses this feature frequently. But the more I use Python (and the more I use Rust in my spare time), the more I realize that I use it only because it's what Python expects me to do. If it was up to me I'd much rather use

  if my_container.empty():
      # do stuff

than

  if not my_container:
      # do stuff

The second implementation behaves the same if either my_container is None or if my_container is empty (or if my_container is 0 or ""...), whereas the first implementation allows me to handle those cases differently. The first implementation is also more explicit and easier to understand on a first read.

It's also easier to debug. Is users supposed to be None in your example? Possibly, but your code doesn't give me any hints. Is my_container supposed to be None in my example? Probably not based on the way I explicitly used the .empty() method.

kstrauser3 yıl önce

Python’s type annotations carry the same information, but explicitly. If fetch_users() returns a list of users, you know exactly what “users” is and whether it can be None.

Really, though, list.empty() is canonically spelled “not list” in Python. That’s the idiom to learn, read, and write.

x3n0ph3n33 yıl önce

That's exactly how Ruby behaves.

michaelteter3 yıl önce

Ruby and Python agree on the all/any functions, but they disagree on the if. And in the "if", I think the Ruby result is better.

earthboundkid3 yıl önce

JavaScript thinks empty arrays are true and it’s annoying because you have to write if (a.length) instead of if (a).

nurettin3 yıl önce

Because of this http://en.m.wikipedia.org/wiki/Vacuous_truth

Minor49er3 yıl önce

Why try to reduce assertions made against something that doesn't exist down to a boolean result? Clearly the answer is undefinable

rwmj3 yıl önce

It makes recursion easier. For example:

  ∀(head::tail) = head ∩ ∀(tail)

if ∀([]) is defined as true then this works for the single element list.

IshKebab3 yıl önce

It's easily definable. all(x) is true iff none of the elements in x are false. This is really the only sane option. To do anything else would be a weird special case for []. Like defining len([]) == None. There's no point; it just makes everything more complicated and worse.

neuromanser3 yıl önce

The assertion is against the set (list in the TFA).

Waterluvian3 yıl önce

I feel like I’d just make a poll and pick the least surprising option if there’s a clear winner.

But maybe that’s why I’m not a language developer.

pharmakom3 yıl önce

In logic class, these were axiomatically equivalent

    for all x. P(x)

    not (exists x. not P(x))

kaleidawave3 yıl önce

Case of the “Vacuous truth”

nobody03 yıl önce

The empty set is vacuously true for any properties with elements.

[deleted]3 yıl önce

rgovostes3 yıl önce

    all([x]+x)

earthboundkid3 yıl önce

(2020)

earthboundkid3 yıl önce

Incidentally I wrote the post. Please don’t AMA. It’s all in the post. No further questions.

gizajob3 yıl önce

The present king of France is bald.

ptx3 yıl önce

Does that work, though? If you're talking about a set of kings, then the set can be empty. But "the king" – isn't that more like Kotlin's single() method, which throws an exception if the number of elements is not 1?

gizajob3 yıl önce

It's a Bertrand Russel joke, and an issue that caused him to want to fix and rebuild formal logic from top to bottom, to differentiate statements like that which aren't really part of reality from functionally identical statements that are part of reality.

NoToP3 yıl önce

A man goes into court not sure how he got there or what he's accused of. The judge starts saying the opening formalities. "If and only if every member of the jury is convinced you are guilty then this court will convict you." The man looks around. "Your honor, there are no members of the jury." The judge slams the gavel hard. "Guilty". That's the trivial case.

nwah13 yıl önce

The codebase of Apache Kafka must be littered with this.

[deleted]3 yıl önce

rightbyte3 yıl önce

   > all([])
   True
   > any([])
   False

Not very consistent philosophy in that case. Surely if 'all' is True then 'any' got to be too?

CJefferson3 yıl önce

It is consistent, and in practice this is the only definition that ends up being sensible, if you play with lots of examples. I have done this as a, I believe, surprisingly fun thing with older school children, where we think about all the things we want to be true about all, and any, and then figure out what the answers are.

Some examples are "if something is true for 'all students', it should be true for any group of students", and if "all students have a hat" is true, then it should not be true that "any student had no hat", etc.

JadeNB3 yıl önce

> Surely if 'all' is True then 'any' got to be too?

No. `any([])` means "some element of [] is true", which is false because there aren't any elements. `all([])` means "all elements of [] are true", which is true because it's (classically, anyway) got to be true or false, and being false would require that there be some element of [] that isn't true, which there isn't.

More generally, `!all([!x for x in xs])` (or whatever the syntax is; I'm not a Python programmer)—meaning "it's not the case that the negation of every element of xs is true"—is `any(xs)`, so `!all([])` is `any([])`.

orf3 yıl önce

Going by the example in the post, "all unicorns are blue" seems truthy whereas "are any unicorns blue" seems falsey in a world with no unicorns?

thewakalix3 yıl önce

`any` corresponds to the existential quantifier, not the universal.

knappa3 yıl önce

I would read all more formally as: for each element in this list, the element is true. Then you get a vacuous truth. (Think about the negation: there is an element in the list which is false. That's obviously false.)

Any would be more formally: there is an element of the list which is true. But the list doesn't have any elements, so that's false.

Looks logical to me. Plus you get that `not any( map(lambda x: not x, l) )` is the same as `all(l)` for any list `l`.

rightbyte3 yıl önce

> Any would be more formally: there is an element of the list which is true. But the list doesn't have any elements, so that's false.

It is just a matter of convention and I see no logic behind why any convention would be worse or wrong. But I believe if 'any' implies 'at least one' so should 'all' otherwise they use different conventions.

In practice I get it was arbitrary choices and this is just how you end up when doing the obvious implementation.

   def all(l):
      for e in l:
         if not e:
            return False
      return True

   def any(l):
      for e in l:
         if e:
            return True
      return False

dragonwriter3 yıl önce

> But I believe if 'any' implies 'at least one' so should 'all' otherwise they use different conventions.

The conventions they use are not an arbitrary choice, and are those of predicate logic. any() is the “for any” (existential quantification) operator, while all() is the “for all” (universal quantification) operator.

They are deeply connected: “all items in xs are true” is “there are not any items in xs that are not true”, or, in code terms, all(xs) == not any(not x for x in xs).

And, vice versa, any(xs) == not all(not x for x in xs)

rightbyte3 yıl önce

Sure thinking about it the 'all ([]) => True', 'any ([]) => False' might be more intuitive.

Arnavion3 yıl önce

any(collection, predicate) == not(all(collection, not(predicate))). Or in English, "It is true that there is an even number in this list." is the same as "It is false that all the numbers in this list are odd."

shawnz3 yıl önce

How could they both have the same answer? They must have opposite answers because of De Morgan's law: asking "is any item true" is the same as asking "are NOT all items NOT true"

zem3 yıl önce

think of "any" as "we can find an element for which this is true", and "all" as "we cannot find an element for which this is false"

Sohcahtoa823 yıl önce

Think of it this way...

You're logging incoming web requests and then gathering statistics in 5 minute intervals.

During one interval, you get no requests.

You check to see...did "all" of the requests get processed without errors? The answer is Yes, because to say No would imply there were errors.

Did "any" of the requests cause an error? The answer is No, because to say Yes would imply at least one error.

mrkeen3 yıl önce

No need for philosophy.

    any (<5)  [6,7,8]
    any (<5) ([6,7,8]  ++           [])
   (any (<5)  [6,7,8]) || (any (<5) [])
    False              || True
    True

earthboundkid3 yıl önce

No need for philosophy, we can just use whatever assumptions underlie our technology without any reflection on what they are or how they got their.

petesergeant3 yıl önce

To prove “do all x satisfy y” you need to find an example that is not.

In order to satisfy “does any x satisfy y” you need find an example that does.

[deleted]3 yıl önce

dkersten3 yıl önce

“Are there any items in this list that are true? No? Ok, then False”

I don’t care about any fancy philosophy. What’s important is what kind of operation you want for when implementing algorithms, and False is what I always want in cases where I do “all”.

kadoban3 yıl önce

> “Are there any items in this list that are true? No? Ok, then False”

There's no particular reasoning that this is any more compelling than: “Are there any items in this list that are false? No? Ok, then True”

jamilton3 yıl önce

"is any item in this list true" is any(), which is different from all().

CJefferson3 yıl önce

Can you give a couple of examples where you want False for an empty all? I'd be interested to see them, as I've found I always want True.

robot_no_4213 yıl önce

> What’s important is what kind of operation you want for when implementing algorithms, and False is what I always want in cases where I do “all”.

Why would you want "all" to produce results that are inconsistent with logic and mathematics? Consider this tautology, which is a result of De Morgan's laws: for any list L, we have that

all(L) == ~any([~x for x in L]).

In other words, if all([]) == False, then you would also logically need to accept that:

False == all([]) == ~any([~x for x in []]) == ~any([])

which means that we'd require any([]) == True. And that's definitely an illogical result.

shawnz3 yıl önce

You're describing the "any" function, which actually does return false in that case already.

stop503 yıl önce

You can define all() as "is there any False item?" Which is False for an empty list, but true for any list with an false item. all(list) == anyfalse(list)