Par[A] describes a parallel computation that eventually produces an A. Rather than starting threads while a program is being assembled, it keeps the computation as a value. A separate run operation supplies an ExecutorService and performs the computation, separating a parallel program’s description from its execution. section 7.2 section 7.5
The basic operations expose distinct choices. unit lifts a value, map2 combines two results, and fork marks a computation for concurrent evaluation. Keeping combination separate from forking avoids imposing one global policy about which work should run asynchronously. lazyUnit is derived from unit and fork when deferred evaluation is wanted. section 7.1.3 section 7.2
Listing 7.4 Basic sketch for an API for Par
def unit[A](a: A): Par[A] #1 extension [A](pa: Par[A]) def map2[B, C](pb: Par[B])(f: (A, B) => C): Par[C] #2 def fork[A](a: => Par[A]): Par[A] #3 def lazyUnit[A](a: => A): Par[A] = fork(unit(a)) #4 extension [A](pa: Par[A]) def run: A #5
The small API makes the shape of Par visible before committing to an implementation: construct computations, combine their results, choose forks, and run only at the boundary. section 7.2
Parallel sum
A divide-and-conquer sum returns Par[Int] rather than extracting each partial result immediately. Each half is recursively described, optionally wrapped in fork, and map2 combines the two Int results with addition. Calling get during recursion would collapse the parallel structure back into sequential waiting. section 7.1.2 section 7.1.3
One representation is ExecutorService => Future[A]: applying a Par to an executor starts or prepares work and returns its handle. This keeps Java Future machinery behind a pure Par interface, but a naive implementation can block while combining results. With bounded thread pools, nested fork operations can deadlock when an occupied worker waits for work that requires that same pool. section 7.2 section 7.2.1 section 7.3.3
A non-blocking representation replaces Future.get with a callback-based Future. Par then yields a function that accepts a callback for the completed result; fork schedules work and map2 coordinates both callbacks without blocking worker threads. Actors are used to safely collect the two results for map2. section 7.3.4 section 7.3.4
Derived combinators demonstrate that Par values remain composable without running them:
- map transforms a completed result, such as sorting a Par[List[Int]], by expressing map through map2 and unit. section 7.2.1
- asyncF turns an A => B into an A => Par[B], allowing parMap to apply a function across a list asynchronously. section 7.2.1
- sequence combines a collection of Par[A] values into one Par[List[A]], with a balanced IndexedSeq version dividing work into halves. section 7.9
- flatMap and join express result-dependent parallel choices, including choice and choiceN. section 7.9
Par operations are constrained by laws. For example, mapping f over unit(x) should be equivalent to unit(f(x)), and mapping identity should leave a Par unchanged. Such laws make implementations testable and let callers treat computations as black boxes; violating the intended behavior of fork can make combinators like parMap unsafe. section 7.3.1 section 7.3.3
Par also serves as a target for asynchronous interpretation. Console requests can be compiled into Par actions, and callback-based non-blocking reads can be lifted into Par before being used inside Free programs. The interface abstracts over the particular non-blocking I/O library underneath. section 13.5 section 13.5
