LFCS seminar: Tarmo Uustalu: Dynamic programming and coalgebras with sharing

Dynamic programming is about recognizing sharing opportunities in recursive call trees of a function. If the pattern of sharing opportunities is known in advance, it can be taken into account so that instead of a tree one builds a dag from the start.

We present a framework for doing so based on coalgebras and comonads, which we demonstrate in action with some classical examples. We use systems of coequations for cooperations to describe sharing opportunity patterns. Further, we use techniques from term rewrite systems, namely Knuth-Bendix completion, to obtain unique normal forms of coterms.

In a Haskell implementation of the framework, we rely on circular programming and zippers implemented generically with derivatives of functors.

This is joint work with Nicolas Wu, University of Bristol.