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