In logic programming, a *substitution* is a mapping from logic variables to values (including other logic variables). Logic programs are composed of **goal**s, with the type signature `Subst => Subst*` — i.e. it might fail (thus generating 0 possible substitution), succeed once, or succeed multiple times, or even an infinite number of times.

It is necessary for substitutions to behave as values — if you take a substitution, and add a binding, you better get a new substitution, rather than do the modification in place, because that substitution might be used by other goals. In Lisp, the traditional data structure for this is the **association list**: a list of lists, where the **car**s (first elements) of each inner list are the keys. Clojure takes Phil Bagwell’s Hash Array Mapped Trie and adds persistency on top of it, to the effect that you have a copy-on-write trie map, with logarithmic rather than linear lookup times.

Technorati Tags: functional, logic, programming, clojure, scala, jvm, data-structures, tries