© University of Kent - Contact | Feedback | Legal | Cookies
The University of Kent, Canterbury, Kent, CT2 7NZ, T +44 (0)1227 764000
Red-black trees with types
Stefan Kahrs
Journal of Functional Programming, 11(4):425-432, July 2001.Abstract
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.
Bibtex Record
@article{1293,
author = {Stefan Kahrs},
title = {Red-black trees with types},
month = {July},
year = {2001},
pages = {425-432},
keywords = {balanced trees, existential types},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2001/1293},
publication_type = {article},
submission_id = {13813_1001084587},
journal = {Journal of Functional Programming},
volume = {11},
number = {4},
publisher = {Cambridge University Press},
}