A Generalization of the Trie Data Structure (1995)

Richard H. Connelly and F. Lockwood Morris

Abstract

Tries, a form of string-indexed look-up structure, are generalized, in a manner first discovered by Wadsworth, 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.