"But to make a hash the fundamental data structure out of which everything else is constructed would be crazy." A hash can easily model a vector, including spa

"But to make a hash the fundamental data structure out of which everything else is constructed would be crazy." A hash can easily model a vector, including sparse vectors. There are efficient functional implementations such as Clojure's which is based on Bagwell's Array Mapped Tries. Functional vectors/arrays are an open research problem. So I would say maps might be very reasonable as the single structure in a functional language. Also, there are many ways to cope with tagging more types than are practically fit within the low bits of a pointer. The simplest dates all the way back to MACLISP (no relation to macintosh). The idea is to tag regions of memory that hold uniform values. This fits very well with modern memory allocators based on the slab allocator.