Now that these functions are written like this, I wonder if it's worth adding monadic versions of All and Any that base's Data.Monoid has. Something like this:

newtype AllM m = AllM (m Bool)
instance Monad m => Semigroup (AllM m) where
  AllM x <> AllM y = AllM (x &&^ y)
instance Monad m => Monoid (AllM m) where
  mempty = AllM (pure True)

And then we could rewrite these all in terms of foldMap with them.

@josephcsible the behaviour of these functions indeed can be generalised using new newtypes. However, I prefer to use current explicit implementation via foldr and not introduce AllM and AnyM newtypes. There're multiple reasons for this:

1. These newtypes don't look very useful outside of these 4 functions. Quick Hoogle search shows that they are not even present on Hackage, which means that they are not that common and idiomatic to be included in the standard library.
2. One of the relude goals is to be minimalistic, which implies not introducing new abstractions without need. And since these 4 functions are exported by default, we can't just put AllM and AnyM in Extra modules.
3. We can have these 2 newtypes locally without exporting. But I guess that using coerced foldMap vs current foldr implementation is the same in terms of performance. So no need to complicate code and make it more difficult for beginners to read and understand.
4. If we reexport them by default, they steal names from the scope. And since these newtypes are not idiomatic, people can already use AnyM and AllM for some other stuff.

And I can add from myself that it's a bit unfortunate that App f Any and App f All don't have the desired behaviour of lazy monadic boolean operators...

Okay, I guess this can go in as-is then.

By the way, what is the type App that you're talking about? I see a lot of types with that name in Hoogle, but none look particularly relevant. EDIT: Oh, did you mean Ap?

@josephcsible Yeah, I mean Ap, Sorry, this was a typo 😞

CI is failing due to import issues. When CI pass, this PR is ready to be merged 🙂

It passes now.