Free the Conqueror! Refactoring divide-and-conquer functions

Divide-and-conquer algorithms appear in the solution of many computationally intensive problems, and are good candidates for parallelization. A divide-and-conquer computation can be expressed in a programming language in many ways. This paper presents a set of small, semantics-preserving code transformations, and a methodology to refactor divide-and-conquer functions in a functional programming language. By applying a sequence of transformations using a refactoring tool, many divide-and-conquer functions can be restructured into a canonical form - which then can be refactored into an instance of a parallel divide-and-conquer pattern. This methodology offers an effective and safe way to parallelize HPC applications.