Russ Abbott
Cool. I wasn't aware of that notation. It doesn't quite get to the issue though.
The problem I'm concerned about is the need to define y in the first place. If one is chasing through a data structure and finds a need to change something buried within it, it seems necessary to rebuild everything that includes the changed thing. That is, I can't change a component of somethingNew without creating y. The point is there's nothing about x that changed, and there may be nothing about (var1 x) that changed, and there may be nothing about var11 . var1 $ x that changed, etc. Yet one is apparently forced to keep track of and reconstruct all those elements.
The data-accessor package makes those changes more syntactically lightweight: http://hackage.haskell.org/package/data-accessor http://hackage.haskell.org/package/data-accessor-template
Another example is to imagine a Tree in which the leaves contain "objects." If I want to change a property of one of those leaf objects, I am forced to rebuild all the ancestor nodes of that leaf down to rebuilding the root.
You could define a function like mapTree, or mapLeaves along with the data structure, that recurses over the tree and applies a function to its components. This also allows changing a leaf without going through the entire tree manually:
mapLeaves (\leaf -> if leaf == wantedLeaf then modifiedLeaf else leaf) tree
If you're concerned about memory usage when "rebuilding" the data structures, Daniel Fischer's previous statements still apply: The modified data structure will share everything with the old one except for the changed parts. Regards, Daniel