And this comes so: the main entry point to our solution is a call to the map function and the type signature of map is

Let’s start with the first argument ( α → β ).

It means that the first argument to map is a function from any unconstrained type α to any unconstrained type β. Let’s call that function f. The map function applies its argument function f to all elements of a list of α values to produce a list of β values, not knowing any specifics about f.

In our case f happens to be (probe lookahead). We are probing each board, looking no further than the given lookahead where probing can be either the valuation of the board or the detection of the forecast.

Mapping any function f over a list of α values cannot possibly perform a side effect. The closest possibility would be a specific function f that returns an IO action as type β. But even in that case, the IO action is only created, not performed. No implementation of map would ever be able to perform such an action since map cannot assume anything about β - particularly it cannot assume that β is an action.

In other words: the signature of map asserts purity of map f and the Frege type system enforces this down the whole call chain! We do not have to go back and check the code ourselves for possible purity breaches nor can any maintainer accidentally undermine our foundation through subsequent changes.

Now, what happens if we go parallel and use mapP (the parallel version of map) instead of map? Here is the type signature of mapP:

That is exactly the same! The whole line of argumentation about purity of map f equally applies to mapP f!

With Frege, we can again apply a non-intrusive increment: from sequential to parallel execution in an absolutely safe manner. Purity and its handling in the type system makes that possible. In all other popular JVM languages this would have been an immensely intrusive change (even if old code was not edited at all - changing its mode of operation is intrusive) with a huge potential to introduce hard-to-detect errors.

And again, we were able to apply this non-intrusive increment without having planned for it. We just did what is usual in Frege and it turned out to just fit.

We can almost always safely go from map to mapP.

There are two considerations, however, that we should apply before blindly making all calls to map parallel:

1) Granularity We applied parallel execution on the top-most layer of the evaluation only, not down to all splits of possible boards. That is a usual performance concern for data-parallel code where we weigh the relative overhead of thread scheduling against the size of the unit of work.

2) Infinite data structures Parallel execution makes usually no sense to work lazily since new threads should start working eagerly to have the result ready when requested. But that approach would never finish when applied to infinite data structures.

But those considerations are fully inside our mental context when applying our increment. We are in the position to decide about granularity and we know that possibleMoves is a finite list. It is a reasoning that is local to one single increment.

My personal experience was very strange when I applied parallelism to the tic tac toe game. I went from map to mapP,  let the code run, and enjoyed the speedup. Then I fell back into my old habit of paranoid concurrency thinking: what could possibly go wrong?

And for the first time ever in such a situation, I couldn’t think of any possible issue.