A functional approach to generic programming using adaptive traversals

摘要

Writing functions over complex user-defined datatypes can be tedious and error prone. Generic (or polytypic) programming and higher order functions like f oldr have resolved some of these issues, but can be too general to be practically useful for larger collections of data types. In this paper we present a traversal-based approach to generic programming using function sets. Our traversal is an adaptive, higher-order function that employs an asymmetric type-based multiple dispatch to fold over arbitrarily complex structures. We introduce our approach in the context of our Scheme library implementation, present a typed model of our system, and provide a proof of type soundness, showing that our flexible, adaptive approach is both useful and safe.