Red-black trees with types
Red-black trees with types
复制标题
具有类型的红黑树
DOI：
--
复制
发表时间：
2001
影响因子：
1.1
通讯作者：
Stefan Kahrs
中科院分区：
文献类型：
--
作者：
Stefan Kahrs
Chris Okasaki 展示了如何用函数式编程语言实现红黑树。 Ralf Hinze 使用高阶嵌套数据类型甚至将此类数据结构的不变量合并到其类型中。我们展示了如何通过结合嵌套数据类型、幻像类型和存在类型变量的特性来实现非常相似的目标，而不会造成此类类型通常的性能损失。
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.