Polymorphic dynamic programming by algebraic shortcut fusion
  Dynamic programming (DP) is a broadly applicable algorithmic design paradigm
for the efficient, exact solution of otherwise intractable, combinatorial
problems. However, the design of such algorithms is often presented informally
in an ad-hoc manner, and as a result is often difficult to apply correctly. In
this paper, we present a rigorous algebraic formalism for systematically
deriving novel DP algorithms, either from existing DP algorithms or from simple
functional recurrences. These derivations lead to algorithms which are provably
correct and polymorphic over any semiring, which means that they can be applied
to the full scope of combinatorial problems expressible in terms of semirings.
This includes, for example: optimization, optimal probability and Viterbi
decoding, probabilistic marginalization, logical inference, fuzzy sets,
differentiable softmax, and relational and provenance queries. The approach,
building on many ideas from the existing literature on constructive
algorithmics, exploits generic properties of (semiring) polymorphic functions,
tupling and formal sums (lifting), and algebraic simplifications arising from
constraint algebras. We demonstrate the effectiveness of this formalism for
some example applications arising in signal processing, bioinformatics and
reliability engineering.
