[Haskell-beginners] Re: Question about data structures

Daniel Schoepe daniel.schoepe at googlemail.com
Wed Nov 24 16:26:39 EST 2010

Russ Abbott <russ.abbott at gmail.com> writes:

> 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


> 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.


More information about the Beginners mailing list