I don't really want multiple data structure primatives though, just the one. And have the language built up around it.
I have been mulling over better support for immutable data structures in Lua, but I haven't figured out a good and clean design yet.
Check out clojure - advanced data structures/primitives + immutability(functional programming)