Red-black trees with types
- 1 January 2001
- journal article
- functional pearls
- Published by Cambridge University Press (CUP) in Journal of Functional Programming
- Vol. 11 (4) , 425-432
- https://doi.org/10.1017/s0956796801004026
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.Keywords
This publication has 0 references indexed in Scilit: