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.
Connelly, Richard H. and Morris, F. Lockwood, "A Generalization of the Trie Data Structure" (1993). Electrical Engineering and Computer Science - Technical Reports. 162.