A coworker came up with this puzzler: What will
(equal (union l1 l2) (union l1 l2))
return? Note that the question is not about what an invidual call to
UNION does. (According to the ANS CL spec [*], UNION makes no
guarantees about the stability of the order of elements in the lists
involved.) One would imagine functions to be, well, functional if not
otherwise noted, but there are some not terribly far-fetched
implementations of UNION where this is not so. For example, a hash
table-based implementation with address-dependent hash keys where a
copying GC causes tables to be rehashed.
--David Gadbois
[*] See KMP's most excellent version at
http://www.harlequin.com/books/HyperSpec/.