This paper proposes a new approach to writing and verifying
divide-and-conquer programs in Coq. Extending the rich line of
previous work on algebraic approaches to recursion schemes, we
present an algebraic approach to divide-and-conquer recursion:
recursions are represented as a form of algebra, and from outer
recursions, one may initiate inner recursions that can construct
data upon which the outer recursions may legally
recurse. Termination is enforced entirely by the typing discipline
of our recursion schemes. Despite this, our approach requires little
from the underlying type system, and can be implemented in System
Fω plus a limited form of positive-recursive types. Our
implementation of the method in Coq does not rely on structural
recursion or on dependent types. The method is demonstrated on
several examples, including mergesort, quicksort, Harper's
regular-expression matcher, and others. An indexed version is also
derived, implementing a form of divide-and-conquer induction that
can be used to reason about functions defined via our method.
