For simplicity, suppose we extend the lambda calculus with a primitive for cards with string keys. Add two operations: set map key valand get map key. To actually implement this primitive, we could use a la Haskell's constant data structure Data.Map, which will give us O(log(n))sets and receive.
Suppose instead that we have implemented this structure with hash tables. getwill O(1), and setwill O(N), since it requires cloning the entire hash table. Is it possible during compilation to analyze all the places where it is safe to perform a mutation in place, replacing it setwith a hidden operation mset?
source
share