2009/2/9 Joachim Breitner <mail@joachim-breitner.de>
Now while this works, and while ST is still somewhat pure, I'm wondering
if there is no better way of expressing "This piece of information came
from the point in a data structure, so something else can be put here
easily".

You might want to look into zippers:  http://haskell.org/haskellwiki/Zipper

Luke