Danel Ahman: Comodule Representations of Second-Order Functionals

Danel Ahman (University of Tartu, Estonia)

Abstract: We demonstrate that the well-known approach of representing continuous second order functionals in terms of well-founded question-answer trees is an instance of a general compositional category-theoretic framework in which representations of second-order functionals are modulated by a monad on containers and a certain right comodule for it. By varying the monad and the comodule we naturally capture in the same framework standard tree-represented functionals, as well as many others, such as: functionals with finite support; functionals that query their input on one instance; functionals that either query the input once or indicate that no query is needed; and instance reductions as studied in reverse constructive mathematics and Weihrauch reducibility.

This is joint work with Andrej Bauer.