Short circuiting in fold expressions

Viewed 160

This is a self triggered question based on a self-answer I gave here.

This seems a pretty convincing explanation of why short-circuiting of logical operators is available in fold expressions, and of the fact that wrapping a fold expression in a function with a variadic argument seems to be non short-circuting (in fact, the answer explains, it's the function call which triggers the evaluation of all arguments, before the short-circuit can take place inside the function body).

However, the following code seems to me, proves that (at least when the arguments in a fold expression are 2) the short-circuiting doesn't happen:

#include <assert.h>
#include <optional>

constexpr auto all_r = [](auto const& ... ps){
    return [&ps...](auto const& x){
        return (ps(x) && ...);
    };
};

constexpr auto all_l = [](auto const& ... ps){
    return [&ps...](auto const& x){
        return (... && ps(x));
    };
};

constexpr auto has_value = [](std::optional<int> o){
    return o.has_value();
};
constexpr auto has_positive = [](std::optional<int> o){
    assert(o.has_value());
    return o.value() > 0;
};

int main() {
    assert(!(has_value(std::optional<int>{}) && has_positive(std::optional<int>{})));
    //assert(!(has_positive(std::optional<int>{}) && has_value(std::optional<int>{}))); // expectedly fails at run-time


    assert(!all_r(has_value, has_positive)(std::optional<int>{}));
    assert(!all_l(has_value, has_positive)(std::optional<int>{})); // I expected this to fail at run-time
    //assert(!all_r(has_positive, has_value)(std::optional<int>{}));
    //assert(!all_l(has_positive, has_value)(std::optional<int>{})); // I expected this to succeed at run-time
}
2 Answers

... && ps(x) with four predicates a, b, c, d expands to

( ( a(x) && b(x) ) && c(x) ) && d(x)

which leads to this order of evaluation: a b c d

ps(x) && ... expands to

a(x) && ( b(x) && ( c(x) && d(x) ) )

which leads to the same order of evaluation: a b c d

This does not change anything about short-circuiting; as soon as one is false, the evaluation stops.

Start with what Pack && ... means.

Cppreference has a pretty readable description.

Pack && ... becomes Pack1 && (Pack2 && (Pack3 && Pack4))) ... && Pack becomes (((Pack1 && Pack2) && Pack3) && Pack4

When evaluating && we evaluate left to right at the top of the parse tree.

For the Pack&&... case, this top level && is Pack1 then the and operator, then (Pack2 && (Pack3 && Pack4)). && evaluates the left side first, and if false it stops.

For the ...&&Pack case, the top level && is way on the right. Its left hand is (((Pack1 && Pack2) && Pack3) and its right hand is Pack4.

But to find out if the left hand is true, we keep on applying that rule. And the very first term we end up evaluating is... Pack1. Which if it is false, we don't bother evaluating the rest.

While the shape of the tree is different, it doesn't matter as much as one might think.

  +
 / \
A   +
   / \
  B   C

and

      +
     / \
    +   C
   / \
  A   B

when doing an in order traversal visit the nodes in the same order, and left / right fold just switch which of these two expression trees is generated.

There are cases where the left/right fold matters, but && on things evaluating to bool isn't one of them.

Related