Generalizing Generalized Tries

A trie is a search tree scheme that employs the structure of search keys to organize information. Tries were originally devised as a means to represent a collection of records indexed by strings over a xed alphabet. Based on work by C.P. Wadsworth and others, R.H. Connelly and F.L. Morris generalized the concept to permit indexing by elements built according to an arbitrary signature. Here we go one step further and de ne tries and operations on tries generically for arbitrary datatypes of rst-order kind, including parameterized and nested datatypes. The derivation employs techniques recently developed in the context of polytypic programming and can be regarded as a comprehensive case study in this new programming paradigm. It is well known that for the implementation of generalized tries nested datatypes and polymorphic recursion are needed. Implementing tries for rst-order kinded datatypes places even greater demands on the type system: it requires rank-2 type signatures and second-order nested datatypes. Despite these requirements the de nition of tries is surprisingly simple, which is mostly due to the framework of polytypic programming