When it comes to the design of algorithms, one often employs the following techniques:Dynamic ProgrammingThe Greedy-StrategyDivide-and-ConquerWhile for the first two methods, there are well-known theoretical foundations, namely the Bellman Optimality Principle and matroid (resp. greedoid) theory, I could not find such a general framework for algorithms based on D&C. Firstly, I am aware of something that we (or rather, the prof) introduced  in a functional programming class,  called an algorithmic skeleton, that arose in the context of combinators. As an example hereof, we gave such a skeleton for D&C algorithms as follows: Definition: Let $A,S$ be non-empty sets. We call the elements of $S$ solutions, and the elements of $P:=\mathfrak{P}(A)$ (that is, the subsets of $A$) are referred to as problems.Then, a D&C-skeleton is a 4-tuple $(P_\beta, \beta, \mathcal{D}, \mathcal{C})$, where: $P_\beta$ is a predicate over the set of problems and we say that a problem $p$ is basic iff $P_\beta(p)$ holds.$\beta$ is a mapping $P_\beta \rightarrow S$ that assigns a solution to each basic problem. $\mathcal{D}$ is a mapping  $P \rightarrow \mathfrak{P}(P)$ that divides each problem into a set of subproblems.$\mathcal{C}$ is a mapping $P\times \mathfrak{P}(S) \rightarrow S$ that joins the solutions (depending on kind of a pivot problem) of the subproblems to produce a solution. Then, for a given skeleton $s=(P_\beta, \beta, \mathcal{D}, \mathcal{C})$ and a problem $p$, the following generic function $f_s: P\rightarrow S$ computes a solution (in the formal sense) for $p$:$f_s(p)= \left\{  \begin{array}{l l}    \beta(p) & \quad \text{if $p$ is basic}\\    \mathcal{C}(p,f(\mathcal{D}(p))) & \quad \text{otherwise}  \end{array} \right.$where in the second line we use the notation $f(X) := \{f(x)  : x\in X\}$ for subsets $X$ of the codomain of a mapping $f$.However, we did not further examine the underlying, structural properties of problems that can be formulated this way (as I said, it was a functional programming class and this was only a small example). Unfortunately, I could not find further reference on this very approach. Hence I don't think the above definitions are quite standard. If someone recognizes what I have stated above, I would be glad about related articles.Secondly, for the greedy strategy we have the famous result that a problem is correctly solved by the general greedy algorithm if and only if its solutions constitute a weighted matroid. Are there similar results for D&C-algorithms (not necessarily based on the method outlined above)?
Theoretical foundations of Divide and Conquer
algorithms;reference request;divide and conquer
A formal treatment (somewhat resembling the model proposed in the question) of the subject using what is called pseudo-morphisms (that is, functions that are almost morphisms, with some pre- and post-computation done), as well as considerations of complexity analysis and parallel implementation of such algorithms are given in:An algebraic model for divide-and-conquer and its parallelism by Zhijing G. Mou and Paul Hudak (in The Journal of Supercomputing , Volume 2, Issue 3, pp. 257-278, November 1988)