Recursion schemes from comonads

Abstract

Within the setting of the categorical approach to total functional programming, we introduce a many-in-one recursion scheme that neatly unifies a variety of seemingly diverging strengthenings of the basic recursion scheme of iteration. The new scheme is doubly generic: in addition to being parametric in a functor capturing the signature of an inductive type, it is also parametric in a comonad and a distributive law (of the functor over the comonad) that together encode the recursive call pattern of a particular recursion scheme for this inductive type. Specializations of the scheme for particular comonads and distributive laws include (simple) iteration and mild generalizations of primitive recursion and course-of-value iteration.