Forum: Ruby-core [CommonRuby - Feature #8723][Open] Array.any? predicate returns true for empty array.

65ed9a4414fcf018fd060b871177716c?d=identicon&s=25 nurettin (Nurettin Onur TUGCU) (Guest)
on 2013-08-02 13:38
(Received via mailing list)
Issue #8723 has been reported by nurettin (Nurettin Onur TUGCU).

----------------------------------------
Feature #8723: Array.any? predicate returns true for empty array.
https://bugs.ruby-lang.org/issues/8723

Author: nurettin (Nurettin Onur TUGCU)
Status: Open
Priority: Normal
Assignee:
Category:
Target version:


Are all your children redheaded?
Would this be true if you have no children?
I have no children, therefore none of my children are redheaded.
Therefore
[].any?{ true } == true makes no sense.
Expected behavior:
[].any?{ true } == false because the array is empty.
C4e88907313843cf07f6d85ba8162120?d=identicon&s=25 Eregon (Benoit Daloze) (Guest)
on 2013-08-02 14:36
(Received via mailing list)
Issue #8723 has been updated by Eregon (Benoit Daloze).

Status changed from Open to Feedback

Which version do you use? Please add your `ruby -v`.

irb for ruby 2.0.0 r36395
> [].any? { true }
=> false

I guess you meant for #all?

> [].all? { true }
=> true

The doc says it well:
"The method returns true if the block never returns false or nil."
Since the block is never used, it is not false or nil, so true.
----------------------------------------
Feature #8723: Array.any? predicate returns true for empty array.
https://bugs.ruby-lang.org/issues/8723#change-40830

Author: nurettin (Nurettin Onur TUGCU)
Status: Feedback
Priority: Normal
Assignee:
Category:
Target version:


Are all your children redheaded?
Would this be true if you have no children?
I have no children, therefore none of my children are redheaded.
Therefore
[].any?{ true } == true makes no sense.
Expected behavior:
[].any?{ true } == false because the array is empty.
65ed9a4414fcf018fd060b871177716c?d=identicon&s=25 nurettin (Nurettin Onur TUGCU) (Guest)
on 2013-08-02 14:43
(Received via mailing list)
Issue #8723 has been updated by nurettin (Nurettin Onur TUGCU).


Yes, I meant for .all? (wasn't able to edit) and the behavior is correct
according to docs, and incorrect according to my interpretation of sets.
(can a predicate be true when you have empty set?)
----------------------------------------
Feature #8723: Array.any? predicate returns true for empty array.
https://bugs.ruby-lang.org/issues/8723#change-40831

Author: nurettin (Nurettin Onur TUGCU)
Status: Feedback
Priority: Normal
Assignee:
Category:
Target version:


Are all your children redheaded?
Would this be true if you have no children?
I have no children, therefore none of my children are redheaded.
Therefore
[].any?{ true } == true makes no sense.
Expected behavior:
[].any?{ true } == false because the array is empty.
C4e88907313843cf07f6d85ba8162120?d=identicon&s=25 Eregon (Benoit Daloze) (Guest)
on 2013-08-02 17:41
(Received via mailing list)
Issue #8723 has been updated by Eregon (Benoit Daloze).

Status changed from Feedback to Rejected

One way to see it is

    enum.all? { |e| predicate(e) } == !enum.any? { |e| !predicate(e) }

And it seems logical to have #any? be false when the array is empty,
right?

Also,

    enum.all? { |e| predicate(e) } == enum.none? { |e| !predicate(e) }

If enum is empty, there is in fact *none* element which could not
satisfy the predicate.

And that also means *all* elements satisfy since there is no element
which could possibly not satisfy it.


Please comment if you find other interpretations supporting yours,
but my guess is most language will satisfy these semantics.
----------------------------------------
Feature #8723: Array.any? predicate returns true for empty array.
https://bugs.ruby-lang.org/issues/8723#change-40834

Author: nurettin (Nurettin Onur TUGCU)
Status: Rejected
Priority: Normal
Assignee:
Category:
Target version:


Are all your children redheaded?
Would this be true if you have no children?
I have no children, therefore none of my children are redheaded.
Therefore
[].any?{ true } == true makes no sense.
Expected behavior:
[].any?{ true } == false because the array is empty.
C4e88907313843cf07f6d85ba8162120?d=identicon&s=25 alexeymuranov (Alexey Muranov) (Guest)
on 2013-08-02 22:23
(Received via mailing list)
Issue #8723 has been updated by alexeymuranov (Alexey Muranov).


nurettin (Nurettin Onur TUGCU) wrote:
> Yes, I meant for .all? (wasn't able to edit) and the behavior is correct
according to docs, and incorrect according to my interpretation of sets. (can a
predicate be true when you have empty set?)

[].any? { |x| predicate(x) }

means in human/mathematical language: "there exists x in [] such that
predicate(x) is true", this is false because there are not elements in
[].

[].all? { |x| predicate(x) }

means: "for every x in [], predicate(x) is true", this is true because
there are not elements in [].

If you have no children, it is true that all your children are redhead.
----------------------------------------
Feature #8723: Array.any? predicate returns true for empty array.
https://bugs.ruby-lang.org/issues/8723#change-40836

Author: nurettin (Nurettin Onur TUGCU)
Status: Rejected
Priority: Normal
Assignee:
Category:
Target version:


Are all your children redheaded?
Would this be true if you have no children?
I have no children, therefore none of my children are redheaded.
Therefore
[].any?{ true } == true makes no sense.
Expected behavior:
[].any?{ true } == false because the array is empty.
05ba106041716c821d3ab34bd60ea220?d=identicon&s=25 David MacMahon (Guest)
on 2013-08-02 23:03
(Received via mailing list)
Just for fun...

# true regardless of whether [].all? returns true or false
[].all? { |x| predicate(x) } == [].all? { |x| !predicate(x) }

# true iff enum is empty, but false otherwise
enum.all? { |x| predicate(x) } == enum.all? { |x| !predicate(x) }

# Q: If enum.all? is true, can enum.any? be false?
# A: Yes, if enum is empty.  (This is arguably non-intuituve. IMHO.)
if enum.all? { |x| predicate(x) } && !enum.any? { |x| predicate(x) }
  puts "enum is empty"
end

True statement 1: All of my pets are dogs.
True statement 2: None of my pets are dogs.
Conclusion: I have no pets.

True statement 1: All of my pets are dogs.
True statement 2: All of my pets are cats.
Conclusion: I have no pets.

Dave
F52e87b92cafb1e8c6d155076b56ecff?d=identicon&s=25 "Martin J. Dürst" <duerst@it.aoyama.ac.jp> (Guest)
on 2013-08-03 07:03
(Received via mailing list)
Several explanations for the correctness of how Ruby currently works
have already been given. Here's one more:

For any Enumerable, e.g. [x, y, z], Enumerable#any {|x| predicate(x) }
is essentially the Ruby way of expressing predicate(x) ∨ predicate(y) ∨
predicate(z). This is similar to calculating a sum (with addition) or a
product (with multiplication). For #all, replace the logical or with a
logical and (∧).

In Math (and therefore in Unicode) there are even big versions of ∨ and
∧ for these operations, in the same way there are big versions of Σ and
Π for sum and product notations.

What do you get when you calculate the sum of 0 elements? 0 of course.
And what do you get when you calculate the product of 0 elements? 1. Why
do you get 0 and 1 in these cases? Because 0 ad 1 are the neutral
element for addition and multiplication. The neutral element is the
number that you can add (or multiply) as many times as you want without
changing the result.

So what's the neutral element of logical or (∨)? It's false. And what's
the neutral element of logical and (∧)? It's true. That means that we
get false for [].any {|x| predicate(x) }, and true for [].all {|x|
predicate(x) }.

Changing to a more programmer-oriented viewpoint, all the above can be
computated as follows (pseudocode):

memo = neutral_element
for x in Enumerable do
     memo = memo operation x # or predicate(x)
end

or in Ruby:

inject(neutral_element) { |memo, x| memo = memo operation x }

or for the inidividual cases:

sum:      inject(0)     { |memo, x| memo += x }
product:  inject(1)     { |memo, x| memo *= x }
any:      inject(false) { |memo, x| memo = memo || predicate(x) }
all:      inject(true)  { |memo, x| memo = memo && predicate(x) }

I hope you can see the symmetry and how this all works out nicely (and
how we would need to make all kinds of weird special rules if it worked
otherwise).

Regards,   Martin.
65ed9a4414fcf018fd060b871177716c?d=identicon&s=25 nurettin (Nurettin Onur TUGCU) (Guest)
on 2013-08-03 08:40
(Received via mailing list)
Issue #8723 has been updated by nurettin (Nurettin Onur TUGCU).


I find I need to address all the questions

=============

"If enum is empty, there is in fact *none* element which could not
satisfy the predicate. " -- Eregon

none element which could not satisfy, you could interpret this as "all
elements satisfy" however I think this is wrong because there are no
elements to satisfy, which means the result is undefined (maybe you
could say nil), not true.

=============

"So what's the neutral element of logical or (∨)? It's false. And what's
the neutral element of logical and (∧)? It's true. That means that we
get false for [].any {|x| predicate(x) }, and true for [].all {|x|
predicate(x) }. " -- duerst


I see completely what you are getting at and it does make sense only if
the result is either true or false. (which is what predicate is defined
as, mathematically, loosely speaking) However I find the result needs
not be defined. Also, defining "all?" or "any?" makes no sense for empty
set since they will never execute. Programmatically speaking, one could
treat, based on this opinion, the result of all and any as any false'ey
value such as nil or false.

============

Of course I understand that there are other languages which do this the
same, I also understand that it would break existing code, and I know
that docs are clear, and of course I can write my own, but is it really
correct behavior to treat undefinedness as truth? In my opinion, no.

----------------------------------------
Feature #8723: Array.any? predicate returns true for empty array.
https://bugs.ruby-lang.org/issues/8723#change-40841

Author: nurettin (Nurettin Onur TUGCU)
Status: Rejected
Priority: Normal
Assignee:
Category:
Target version:


Are all your children redheaded?
Would this be true if you have no children?
I have no children, therefore none of my children are redheaded.
Therefore
[].any?{ true } == true makes no sense.
Expected behavior:
[].any?{ true } == false because the array is empty.
C4e88907313843cf07f6d85ba8162120?d=identicon&s=25 alexeymuranov (Alexey Muranov) (Guest)
on 2013-08-03 09:10
(Received via mailing list)
Issue #8723 has been updated by alexeymuranov (Alexey Muranov).


Nurettin, what would be a benefit to introducing this exception to a
simple rule?  You propose to make the truth value undefined where it is
well defined.  Can you cite some mathematical theory or natural language
where it is undefined?

Do you agree at least that you initial proposal with assigning false to
[].all?{...} was unreasonable?

Trying to make sense of your alternative point of view in a natural
language, suppose it is false that ALL of your children are redhead.
Would it be true then that NOT ALL of them are redhead?  If i follow
your logic, this should mean that you have both redhead and non-redhead
children.  What if you have no children?

In my opinion, your confusion arrises from the fact that in natural
languages you would not say a phrase like this, because it is simpler
and more informative to say that you have no children.  If someone asks
you if all your children are readhead and you have none, you will answer
"yes" if you are a mathematician, and probably "i have not children/none
of your business" otherwise.
----------------------------------------
Feature #8723: Array.any? predicate returns true for empty array.
https://bugs.ruby-lang.org/issues/8723#change-40842

Author: nurettin (Nurettin Onur TUGCU)
Status: Rejected
Priority: Normal
Assignee:
Category:
Target version:


Are all your children redheaded?
Would this be true if you have no children?
I have no children, therefore none of my children are redheaded.
Therefore
[].any?{ true } == true makes no sense.
Expected behavior:
[].any?{ true } == false because the array is empty.
F52e87b92cafb1e8c6d155076b56ecff?d=identicon&s=25 "Martin J. Dürst" <duerst@it.aoyama.ac.jp> (Guest)
on 2013-08-03 10:02
(Received via mailing list)
On 2013/08/03 15:40, nurettin (Nurettin Onur TUGCU) wrote:
>
> Issue #8723 has been updated by nurettin (Nurettin Onur TUGCU).
>
>
> I find I need to address all the questions

> However I find the result needs not be defined. Also, defining "all?" or "any?"
makes no sense for empty set since they will never execute.

You say:

 > Also, defining "all?" or "any?" makes no sense for empty set since
they will never execute.

So should be write code like

unless enum.empty?
    enum.all { |x| predicate(x) }
end

Think about this in a bigger context. Assume we are applying .any or
.all not to a simple array, but to an array of arrays.

We would e.g. write

arrays.all { |a| a.all { |x| predicate(x) } }

If we use what we currently have in Ruby, this just works, even if there
are some empty lists in the 'arrays' array. With your proposal, we'd
have to write a lot of special code.

> ============
>
> Of course I understand that there are other languages which do this the same, I
also understand that it would break existing code, and I know that docs are 
clear,
and of course I can write my own, but is it really correct behavior to treat
undefinedness as truth? In my opinion, no.

It would be incorrect behavior to treat undefinedness as truth, but the
results of these operations are not undefined. They have a clear
underlying mathematical background. People familiar with this area know
what the results are, and they expect them to work the way they do.
Anything else would be highly confusing for everybody except maybe
beginners.

I suggest you read some introductory book in this area (discrete math).
An alternative is to read a book on Haskell, especially one that
discusses code transformations/equivalences and proofs.

Regards,   Martin.
22e767367fe9c51fc5d22af7a631c424?d=identicon&s=25 Fuad Saud (Guest)
on 2013-08-03 10:24
(Received via mailing list)
Some more explanation reading on the subject - and reasons for this:
http://en.m.wikipedia.org/wiki/Universal_quantification

http://en.m.wikipedia.org/wiki/Vacuous_truth

It's a basic classic logic definition.
65ed9a4414fcf018fd060b871177716c?d=identicon&s=25 nurettin (Nurettin Onur TUGCU) (Guest)
on 2013-08-03 12:59
(Received via mailing list)
Issue #8723 has been updated by nurettin (Nurettin Onur TUGCU).


=========

"Do you agree at least that you initial proposal with assigning false to
[].all?{...} was unreasonable?" --alexeymuranov

Well yes, I wanted it to return any false'y value, actually. Including
nil. Sorry for not making it clear.

=========

"They are true because a material conditional is defined to be true when
the antecedent is false (or the conclusion is true)." --
http://en.m.wikipedia.org/wiki/Vacuous_truth

OK I agree that the behavior is well-defined in mathematics now. Thanks
for the effort everyone.

My confusion arose from the fact that where the mathematical notation
for all? would be:

"for all x element of an sequence S where predicate Q is true, the
result of all? is true"

    ∀x(x ∈ S -> Q)

There were no x where predicate Q was true.

However I see now that Vacuous Truth principle defines that case as
well.

So this makes

"... but the results of these operations are not undefined." -- Martin

Completely correct. I have no more issue with any? or all?
----------------------------------------
Feature #8723: Array.any? predicate returns true for empty array.
https://bugs.ruby-lang.org/issues/8723#change-40848

Author: nurettin (Nurettin Onur TUGCU)
Status: Rejected
Priority: Normal
Assignee:
Category:
Target version:


Are all your children redheaded?
Would this be true if you have no children?
I have no children, therefore none of my children are redheaded.
Therefore
[].any?{ true } == true makes no sense.
Expected behavior:
[].any?{ true } == false because the array is empty.
This topic is locked and can not be replied to.