[Haskell-beginners] Question about data structures

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

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.

One way to avoid that is for the leaves to refer to their objects through a
Map. Then changing a leaf object requires only that the value associated
with key represented by the leaf be (re-)inserted into the Map.  The Tree
itself need not change at all.

But that trick isn't always available.  In the example we are talking about
we can't make a Map where they keys are the instance variable names and the
values are their values.  That would seem to do the job, but since the
values are of different types, we can't create such a Map.

So now what?
*
-- Russ *



On Wed, Nov 24, 2010 at 12:26 PM, Daniel Fischer
<daniel.is.fischer at web.de>wrote:

> On Wednesday 24 November 2010 20:40:02, Russ Abbott wrote:
> > I would appreciate some advice about the best way to manipulate data
> > structures in Haskell.
> >
> > Let's assume I have what in an OO language would be a class with a
> > number of instance variables.  When I want to change one of the values
> > of one of those instance variables in Haskell I must rebuild the entire
> > structure.  Even worse, if one of those instance variables is a
> > reference to another data structure, then when I change that referenced
> > data structure, I am forced to rebuild my top level variable.  For
> > example.
> >
> > data Struct1  =  Struct1  {var1  :: Struct11, var2 :: Struct1, ... }
> > data Struct11 = Struct11 {var11 :: ... }
> >
> > Let's assume I have x :: Struct1 and that I change the value of var11 .
> > var1 $ x.  Doesn't that require that I rebuild x?
>
> No, x doesn't change.
> What you probably mean is
>
> y = x{ var1 = (var1 x){ var11 = somethingNew } }
>
> Then y shares all fields except var1 with x, the var1 field of y must be
> built, but it shares everything except the var11 field with (var1 x).
>
> Since values are immutable, the bulk of the structure is shared between an
> original value and a modified one (except if the structures are very small
> so there's little to share, but then building is cheap, or the modification
> changes very much of the structure, but then the modification would be
> expensive also in a language with mutable values).
>
> >
> > Is there a better way?
> >
> > Thanks.
> > *
> > -- Russ*
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20101124/b463c22e/attachment.html