My colleague Dave and I are writing our butts off so we can submit a paper to FLOPS 2010! Here's the abstract, which I just turned in:
Unification, a fundamental process for logic programming systems, relies on the ability to efficiently look up values of variables in a substitution. Triangular substitutions, which allow associations to values that are themselves bound by another association, are an attractive choice for purely functional implementations of logic programming systems because of their fast extension time and linear space requirement, but have the disadvantage of costly lookup. We present several representations for triangular substitutions that decrease the cost of lookup to linear or logarithmic time in the size of the substitution while maintaining most of their desirable properties. In particular, we show that triangular substitutions can be represented efficiently using deferred-extension skew binary random access lists, and that this representation provides a significant decrease in running time for existing programs written in miniKanren, a declarative logic programming system implemented in a pure functional subset of Scheme.
Yep, that says "deferred-extension skew binary random access lists". Best data structure ever! It's hilarious how I write about stuff like this, and then I go to job interviews and can't answer questions about hash tables.