[Haskell-beginners] Question about data structures

[Russ Abbott]

OK. So putting a Map at Leaf nodes doesn't solve the problem.   (Apparently
I haven't been able to communicate what I see as the problem.)

The problem that I'm trying to get to is the need to write excessive code
for something that would require a lot less code in an OO world.  It's not a
matter of execution time or space. It's a matter of the amount of code one
is required to write.
*
-- Russ *



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

> On Wednesday 24 November 2010 22:12:37, Russ Abbott wrote:
> > 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.
>
> In general, values are immutable, so you can't "change something buried
> within it". You have to build a new value containing some of the old stuff
> and a new part. Building the new value usually consists mostly of copying a
> couple of pointers (plus building the new part of course), so isn't too
> expensive normally.
>
> You can have mutable values in the IO or (ST s) monads, if you need them.
>
> > That is, I can't change a
> > component of somethingNew without creating y. The point is there's
> > nothing about x that changed,
>
> The thing with the changed component is not x anymore.
>
> > 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 compiler takes care of that.
>
> >
> > 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,
>
> You can't in general, the thing with a different property is a different
> object.
>
> > I am forced to rebuild all the ancestor nodes of that leaf down to
> > rebuilding the root.
>
> Yes (well, not you, the compiler does it), except if your tree contains
> mutable objects (IORefs/STRefs for example).
>
> >
> > 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.
>
> Oh, it will. If you change a Map, you get a new one, thus you get a new
> tree containing the new Map.
>
> >
> > 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?
>
> Well, what's the problem with the compiler copying some nodes?
> Normally, that doesn't cost very much performance, if it does in your case,
> we'd need to know more to suggest the best way to go.
>
> > *
> > -- Russ *
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20101124/e9cf6707/attachment-0001.html