The expense of distributed method calls comes from the fact that you are dealing with objects -- that is, containers of mutable state -- where you either need to synchronize copies across the network (expensive in terms of traffic/latency) or run all method calls on the place where the object lives (likewise expensive in terms of latency).
Pure function calls don't depend on mutable state, and so don't have those issues (further, to the extent that you do set up a system that requires a remote call to execute them, once you've executed a given pure function with a given set of arguments, you don't need to do it again, as the result is cacheable and guaranteed good forever.) You still have to distribute the calls that actually depend on mutable state, but if your language starts out with a clean distinction between pure functions and operations whose result might depend on mutable state, you start out miles ahead when it comes to dealing with distribution compared to working with a language which provides no language level distinction between pure and impure code, requiring either manual segregation or treat-everything-as-state-dependent-and-pay-the-cost approaches.
Any function that is capable of returning varying results for the same arguments is impure. And a function call across the network could return anything - a correct response, a corrupt response, no response - depending on what the network's having for lunch at that moment. We do have clever tools like the I/O monad, yes. But the I/O monad doesn't take I/O and make it pure; it takes I/O and wraps it up in a clever facade that (usually) lets you pretend that it's pure.
Obviously, the medium of a network call is inherently impure -- but in the same way that anything implemented in an any physical device is (including internal computations in an electronic computer without network communication.)
Which is exactly the same in functional as OO languages. If service A has some data, and service B needs to make use of that data, then service B needs to make a call to service A.
The OO/functional axis is orthogonal to the monolithic/distributed axis.
Functional programming is all about avoiding shared mutable state, so it does have an advantage here.
The official answer is probably that you'd use some sort of monad to sweep that mess under the carpet. At which point you've just proposed a very close functional analogue to some of the worst shenanigans that used to happen with distributed objects back in the '90s.
A better answer would be to say that you use something like Erlang's actor model. At which point you've proposed something very similar to - perhaps indistinguishable from - microservices.
If its not a pure function of the type of the lists elements, its not really a predicate. (Though, in a language which doesn't distinguish pure from impure code, it might look like one.) So the question is somewhat incoherent from the start, though the problem is a real issue.
> What is correct behavior for higher-order functions which accept function arguments that may time out?
No different from any other operation that can timeout (or otherwise fail).
> The official answer is probably that you'd use some sort of monad to sweep that mess under the carpet.
Monads don't sweep mess under the carpet, they expose it. And they aren't really an answer to "what is the correct behavior...", they are an answer to "once you've determined the correct behavior, what language featuers do you use to implement it in a pure functional language."
But, yes, in Haskell or a similar language, the question of "how do you deal with this external interaction that can fail" does likely involve the use of monads.
> At which point you've just proposed a very close functional analogue to some of the worst shenanigans that used to happen with distributed objects back in the '90s.
That's quite a leap, since invoking monads doesn't specify anything about functionality.
> A better answer would be to say that you use something like Erlang's actor model.
That's actually an orthogonal (non-)answer, since (1) the Actor model isn't an alternative which excludes monads, they operate in different conceptual domains, and (2) it still doesn't answer the "What is the correct behavior...?" question.
> At which point you've proposed something very similar to - perhaps indistinguishable from - microservices.
Yes, microservices are closely related to the actor model. Yes, monads are part of how you'd implement either in Haskell or a similar language. One isn't "better" than the other.
I don't think it is the same, because the distinction is visible. Monadic code looks almost but not quite the same as pure code; it's not a lot of syntactic overhead, but it's enough to make it clear that something's going on. You can see right there in the type that this is invoking a remote call, and if you try to pretend that a distributed function is a regular function then the compiler will catch you and stop you. I don't think this is at all the same as CORBA, where there was literally no visible difference.
[0] Facebook's Haxl library comes to mind
If you read that post again you'll see that Fowler's admonition about "not distributing objects" is really about "not distributing method calls", and method calls aren't that different from function calls so far as his argument is concerned in that (1) the latency of distributed function calls is 10^3-10^6 greater than local function calls, and (2) distributed function calls often fail for reasons inherit to the network and not the application itself.
I'll agree that functional programming languages have many virtues, in that you can compose pure functions, run them in parallel and so forth, but functional programming does not make the issues Fowler talks about go away.