Seq No More: Better Strategies for Parallel Haskell

The authors present a complete redesign of evaluation strategies, a key abstraction for specifying pure, deterministic parallelism in Haskell. Their new formulation preserves the compositionality and modularity benefits of the original, while providing significant new benefits. First, they introduce an evaluation-order monad to provide clearer, more generic, and more efficient specification of parallel evaluation. Secondly, the new formulation resolves a subtle space management issue with the original strategies, allowing parallelism (sparks) to be preserved while reclaiming heap associated with superfluous parallelism. Related to this, the new formulation provides far better support for speculative parallelism as the garbage collector now prunes unneeded speculation.