Hostname: page-component-7c8c6479df-7qhmt Total loading time: 0 Render date: 2024-03-18T14:41:15.599Z Has data issue: false hasContentIssue false

Red-black trees with types

Published online by Cambridge University Press:  04 September 2001

STEFAN KAHRS
Affiliation:
University of Kent at Canterbury, Canterbury, Kent, UK
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.

Chris Okasaki showed how to implement red-black trees in a functional programming language. Ralf Hinze incorporated even the invariants of such data structures into their types, using higher-order nested datatypes. We show how one can achieve something very similar without the usual performance penalty of such types, by combining the features of nested datatypes, phantom types and existential type variables.

Type
Functional Pearls
Copyright
© 2001 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.