Nordic Journal of Computing Bibliography

Tarmo Uustalu, Varmo Vene, and Alberto Pardo. Recursion Schemes from Comonads. Nordic Journal of Computing, 8(3):366-390, Fall 2001.

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.

Categories and Subject Descriptors: D.1.1 [Programming Techniques]: Applicative (Functional) Programming; D.3.3 [Programming Languages]: Language Constructs and Features; F.3.3 [Logics and Meanings of Programs]: Studies of Program Constructs

Additional Key Words and Phrases: inductive types, iteration, recursion schemes, initial functor-algebras, comonads, distributive laws, functional programming, genericity, category-theoretic

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database