I have found it handy to make a 'frozendict' type in Python, though my implementation scales horribly -- I'm not usually worrying about efficiency. I wish a good one were built in, too.

Re functional sequences, there's tuples.