On the Expressive Power of Indexed Applicative and Monadic Structures

by Jan Malakhovski, published

A PhD thesis showing that Applicative and Monadic structures can express surprisingly more than conventionally believed.


It is well-known that very simple theoretic constructs such as Either (type-theoretic equivalent of the logical “or” operator), State (composable state transformers), Applicative (generalized function application), and Monad (generalized sequential program composition) structures (as they are named in Haskell) cover a huge chunk of what is usually needed to elegantly express most computational idioms used in conventional programs. However, it is conventionally argued that there are several classes of commonly used idioms that do not fit well within those structures, the most notable examples being transformations between trees (data types, which are usually argued to require ether generalized pattern matching or heavy metaprogramming infrastructure) and exception handling (which are usually argued to require special language and run-time support).

This work aims to show that many of those idioms can, in fact, be expressed by reusing those well-known structures with minor (if any) modifications. In other words, the purpose of this work is to apply the KISS (Keep It Stupid Simple) and/or Occam’s razor principles to algebraic structures used to solve common programming problems.

Technically speaking, this work aims to show that natural generalizations of Applicative and Monad type classes of Haskell combined with the ability to make Cartesian products of them produce a very simple common framework for expressing many practically useful things, some of the instances of which are very convenient novel ways to express common programming ideas, while others are usually classified as effect systems. On that latter point, if one is to generalize the presented instances into an approach to design of effect systems in general, then the overall structure of such an approach can be thought of as being an almost syntactic framework which allows different effect systems adhering to the general structure of the “marriage” framework [1] to be expressed on top of. (Though, this work does not go into too much into the latter, since this work is mainly motivated by examples that can be immediately applied to Haskell practice.)

Note, however, that, after the fact, these technical observation are completely unsurprising: Applicative and Monad are generalizations of functional and linear program compositions respectively, so, naturally, Cartesian products of these two structures ought to cover a lot of what programs usually do.



1. Wadler P., Thiemann P. The marriage of effects and monads // ACM Transactions on Computational Logic. 2003. Vol. 4, № 1. Pp. 1–32. http://homepages.inf.ed.ac.uk/wadler/papers/effectstocl/effectstocl.ps.gz.