Hal Daume
p.s., I sense your next question is going to be something like "why can't the compiler detect that the array can be updated in place instead of copied" and the answer, from what i can tell, is simply that it doesn't try.
And one might argue that it should not try since the result would be incredibly fragile with small, semantics preserving changes to the program confusing the analysis and causing changes in the big-O complexity of your program and, since the analysis would undoubtedly be pretty darn cunning, it'd also be virtually impossible to understand why it did or did not manage to detect the single-threadedness of your code. I think one of the reasons that approaches based on types (monads, MADTs, linear types, etc.) are so popular is that they make the programmers assertion (X is used in a single-threaded manner) sufficiently explicit that the compiler can complain when it disagrees and, since parts of the analysis show through in the typesystem, they make the analysis less of a black box. -- Alastair Reid alastair@reid-consulting-uk.ltd.uk Reid Consulting (UK) Limited http://www.reid-consulting-uk.ltd.uk/alastair/ ps The opening paragraphs of Paul Hudak's MADT paper (http://www.haskell.org/papers/madt.ps) have a more coherent explanation of why smarter compilers are not the answer.