"Even when I'm programming normally in Arc or JavaScript, I use tables with immutable list keys all the time. It doesn't seem unusual to me."
You silly. Neither JavaScript nor Arc have immutable lists. Well, I guess you could use Object.freeze on an array in JS, but... even if you did that, it would just serialize the array to a string.
Lol, yep. The way I "implement" immutable lists in practical programming is by not modifying them. I rationalize that their static type would enforce this if only there were a type system. :-p
More specifically...
In Arc I can't really rely on using lists as keys, since (IIRC) Jarc converts table keys to strings using the same behavior as 'write. However, in practice I have used lists of alphanumeric symbols, since those have a predictable 'write representation on Jarc, a predictable Racket 'equal? behavior on pg-Arc, etc.
Similarly, in JavaScript I tend to use Arrays of strings, storing them as their ECMAScript 5 JSON representation.
