# Logical "and", &&, and mapreduce

**URL:** <https://discourse.julialang.org/t/logical-and-and-mapreduce/119659>\
**Category:** Performance\
**Created:** [September 20, 2024, 8:58pm UTC](https://discourse.julialang.org/t/logical-and-and-mapreduce/119659 "2024-09-20T20:58:15Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [September 20, 2024, 8:58pm UTC](https://discourse.julialang.org/t/logical-and-and-mapreduce/119659/1 "2024-09-20T20:58:16Z")

</div>

I wonder if a function like `and(x::Bool, y::Bool) = x && y` would be useful.

You can currently do  
`mapreduce(f, &, x, y)`, where `f` takes two arguments and returns `Bool`.

But `and` always returns `Bool` (only has this one method). So you could write a method for `mapreduce(f, and, x, y)` with a fast exit.

Apparently, `any` is not always an option. `isapprox` uses `mapreduce` instead of `any`.

A couple of potential problems. First, if you add a method for `and` that does not return `Bool`, then this will fail. But you shouldn’t do that. (`missing` and `Symbolics` might want to anyway.)

Another potential problem is that `all` was replaced by `mapreduce` in `isapprox` in order for it to work with GPU arrays. The issue ([#44893](https://github.com/JuliaLang/julia/pull/44893)) that led to the change said it was because `zip` was used. But if it is related to the fact that `mapreduce` is less predictable with a fast exit, then you lose the advantage. I mean if you know the lengths of `x` and `y`, then you know how many times `f` is called and with what data, as long as there is no fast exit.

You can see that `isapprox` suffers in performance in losing the fast exit. It was judged that the performance loss was worth the gain in generality, which is probably reasonable.

Off the top of my head, I can’t think of other advantages of `and` over `&`.

---

<div class="post-metadata">

**Author:** ![danielwe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielwe/32/35657_2.png) [@danielwe](https://discourse.julialang.org/u/danielwe)\
**Post date:** [September 20, 2024, 9:53pm UTC](https://discourse.julialang.org/t/logical-and-and-mapreduce/119659/2 "2024-09-20T21:53:17Z")

</div>

> [@jlapeyre](#):
>
> The issue ([#44893](https://github.com/JuliaLang/julia/pull/44893)) that led to the change said it was because `zip` was used. But if it is related to the fact that `mapreduce` is less predictable with a fast exit

As the author of that PR: the point was just that more or less every array type implements the `mapreduce` machinery as the foundation for functions like `sum`, while many common array types such as GPU arrays don’t support iteration/scalar indexing and hence can’t be used with `zip`. That’s why using `mapreduce` made the method more generic. This doesn’t preclude having a short-circuiting `mapreduce` for array types that do support iteration, someone just has to implement it.

I know mapreduce sometimes replaces the provided reducer with a slightly tweaked one, e.g., `mapreduce(f, +, x)` dispatching to `mapreduce(f, Base._secret_add_only_for_mapreduce, x)` or something along those lines. So perhaps rather than adding a new public function `and` and hoping that people start using it, one could dispatch `mapreduce(f, &, x)` to a short-circuiting `mapreduce(f, Base._secret_and, x)` if it is inferred that `f(::eltype(x))` returns `Bool`.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [September 21, 2024, 12:30am UTC](https://discourse.julialang.org/t/logical-and-and-mapreduce/119659/3 "2024-09-21T00:30:31Z")

</div>

Isn’t `all` an option?

---

<div class="post-metadata">

**Author:** ![danielwe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielwe/32/35657_2.png) [@danielwe](https://discourse.julialang.org/u/danielwe)\
**Post date:** [September 21, 2024, 12:42am UTC](https://discourse.julialang.org/t/logical-and-and-mapreduce/119659/4 "2024-09-21T00:42:11Z")

</div>

Option for what?

Edit: I guess you mean using `all(f, x)` instead of `mapreduce(f, &, x)`. That’s true. The issue is actually with `mapreduce(f, &, x, y)` as described in the OP, because the equivalent `all(((x, y),) -> f(x, y), zip(x, y))` uses `zip`. Sorry for confusing those in my post above.

But maybe you mean implementing multi-argument methods like `all(f, x, y)` which are equivalent to `mapreduce(f, &, x, y)` but short-circuiting by default. That sounds like an interesting proposal to me.

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [September 21, 2024, 3:17am UTC](https://discourse.julialang.org/t/logical-and-and-mapreduce/119659/5 "2024-09-21T03:17:07Z")

</div>

> [@danielwe](#):
>
> if it is inferred that `f(::eltype(x))` returns `Bool`

Yes, if that’s possible, it would be preferable to another public function. I have no idea how feasible that would be.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [September 21, 2024, 7:21am UTC](https://discourse.julialang.org/t/logical-and-and-mapreduce/119659/6 "2024-09-21T07:21:43Z")

</div>

Such a function does not preserve the short circuiting behavior of `&&` correctly. `and(and(a,b), and(c,d))` requires `b` as well as `and(c,d)` to be evaluated when `a` is false, while a version written with `&&` does not. In `(a && b) && (c && d)`, only `a` needs to be evaluated. This is because function arguments need to be fully evaluated before the function can be called.

---

<div class="post-metadata">

**Author:** ![danielwe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielwe/32/35657_2.png) [@danielwe](https://discourse.julialang.org/u/danielwe)\
**Post date:** [September 21, 2024, 7:41am UTC](https://discourse.julialang.org/t/logical-and-and-mapreduce/119659/7 "2024-09-21T07:41:08Z")

</div>

True, `and` wouldn’t be semantically equivalent to `&&`, but I don’t think that was the point; the point was to have a function to specialize on when implementing a short-circuiting method of `mapreduce(f, &, xs...)`. You can’t simply make the method for `&` short-circuiting because it doesn’t always return a `Bool`, and `mapreduce(f, &&, xs...)` is nonsense because `&&` is not a function.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [September 21, 2024, 7:50am UTC](https://discourse.julialang.org/t/logical-and-and-mapreduce/119659/8 "2024-09-21T07:50:13Z")

</div>

> [@danielwe](#):
>
> True, `and` wouldn’t be semantically equivalent to `&&`, but I don’t think that was the point;

I think it was, at least in part:

> [@jlapeyre](#):
>
> So you could write a method for `mapreduce(f, and, x, y)` with a fast exit.

The only possible reduction for such an `and` that preserves short circuiting is one like `foldl` or `foldr`, you can’t split up the reduction space into a tree-like reduction. `&&` is inherently serial.

---

<div class="post-metadata">

**Author:** ![danielwe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielwe/32/35657_2.png) [@danielwe](https://discourse.julialang.org/u/danielwe)\
**Post date:** [September 21, 2024, 8:23am UTC](https://discourse.julialang.org/t/logical-and-and-mapreduce/119659/9 "2024-09-21T08:23:07Z")

</div>

> [@Sukera](#):
>
> you can’t split up the reduction space into a tree-like reduction

Why not? For each node that executes its branches in sequence, if the first branch returned `false` you skip the second and return. This can save you a lot of computation on a serial processor where every node is of this type. If you’re doing a GPU-style reduction where all branches are concurrent you won’t save anything of course, but that’s the point: `mapreduce` can have different methods for different array types, with optimizations like this for the ones where it’s suitable.

Also, in the Base implementation of `mapreduce`, tree reduction only kicks in for lengths greater than 1024, so there can be big serial chunks to short circuit in the base case.

As far as I understood the OP, the question is only about opportunistic performance optimization, not about wanting a semantic guarantee that only values left (or right) of the first `false` will be inspected.