For simplicity, suppose we extend the lambda calculus with a primitive for maps with string keys. We add two operations: set map key val and get map key. To actually implement this primitive, we could use a persistent data structure a la Haskell's Data.Map, which would give us O(log(n)) sets and gets.
Suppose we, instead, implemented this structure with hash-tables. get would be O(1) and set would be O(N), as it requires cloning the whole hash-table. Would it be possible to, during compile-type, analyze all places where it is safe to perform an in-place mutation, replacing set by a hidden mset operation?