`choose` Your Own Derivative HD

Kenneth Foner C◦mp◦se :: Conference http://www.composeconference.org/2017/ May 18, 2017 In event-driven programming, an event is a computation that will eventually produce a value. Selective choice is a mechanism that takes in a list of events, runs them all concurrently, and returns the value of the first event to terminate. This primitive appears throughout systems and concurrent programming, ranging from Unix system calls (select) to asynchronous programming libraries in Haskell and in OCaml Core. Despite their ubiquity, these primitives are typically restricted to taking a list of events that all produce values of the same type. In this talk, we describe a natural type-directed generalization of selective choice to arbitrary data structures, including those containing events of different types. The crucial observation we make is that selecting one event out of a data structure is reminiscent of zipping into that data structure. Conor McBride defines zippers into arbitrary “regular” algebraic data types by means of a type-level operation that acts like the partial derivative from calculus. We extend this notion of derivative to support data types containing events, and show how to use these derivatives to give a type to our generalization of selective choice. We implement these ideas in Haskell using GHC’s support for dependent types and generic programming, and demonstrate the use of generalized selective choice with a variety of examples.