People reading the update-notation thread might also be interested in
"Imperative functional programming"
Peyton Jones & Wadler, POPL 93
which you can grab by ftp
from ftp.dcs.glasgow.ac.uk
in pub/glasgow-fp/papers/imperative.ps.Z
The paper mainly deals with I/O and updatable arrays, but the same
technology allows other update-in-place data structures too. It is
all implemented in the Glasgow Haskell compiler.
No claims here that our approach, which is generally similar to the one Paul
describes, solves all the problems. I completely agree that the difficulty
of reasoning about space and time behaviour is a Problem for non-strict
languages.
Simon