Hostname: page-component-7c8c6479df-7qhmt Total loading time: 0 Render date: 2024-03-29T10:01:26.768Z Has data issue: false hasContentIssue false

Generalizing generalized tries

Published online by Cambridge University Press:  03 November 2000

RALF HINZE
Affiliation:
Institut für Informatik III, Universität Bonn, Römerstraße 164, 53117 Bonn, Germany (e-mail: ralf@informatik.uni-bonn.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 fixed 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 define tries and operations on tries generically for arbitrary datatypes of first-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 first-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 definition of tries is surprisingly simple, which is mostly due to the framework of polytypic programming.

Type
Research Article
Copyright
© 2000 Cambridge University Press
Supplementary material: Link

Hinze Supplementary Material

Link
Submit a response

Discussions

No Discussions have been published for this article.