A Generalization of the Trie Data Structure

Tries, a form of string-indexed look-up structure, are generalized to permit indexing by terms built according to an arbitrary signature. The construction is parametric with respect to the type of data to be stored as values; this is essential, because the recursion which defines tries appeals from one value type to others. Trie (for any fixed signature) is then a functor, and the corresponding look-up function is a natural isomorphism. The trie functor is in principle definable by the initial fixed point semantics of Smyth and Plotkin. We simplify the construction, however, by introducing the category-cpo , a class of category within which calculations can retain some domain-theoretic flavor. Our construction of tries extends easily to many-sorted signatures