<div dir="ltr"><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">Actually using a Map does solve the problem. The Map has to be kept at the level of the Tree rather than have each leaf node point to it. So instead of just a Tree one has, say (Map, Tree). Then when one wants to change the property of something associated with a leaf node, one can just change the map. The Tree is unchanged.<br clear="all">
</font></font></font><div dir="ltr"><font><font face="'trebuchet ms', sans-serif"><i><font color="#003333"><br>-- Russ</font></i></font></font></div><div dir="ltr"><font><i></i></font><font class="Apple-style-span" color="#003333" face="'trebuchet ms', sans-serif"><i><br>
</i></font><div><font><font face="'trebuchet ms', sans-serif"><i><font color="#003333"></font></i></font><br></font></div></div>
<br><br><div class="gmail_quote">On Wed, Nov 24, 2010 at 2:02 PM, Russ Abbott <span dir="ltr"><<a href="mailto:russ.abbott@gmail.com">russ.abbott@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div dir="ltr"><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">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.)</font></font></font><div>
<font color="#003333" face="'trebuchet ms', sans-serif"><br></font></div><div><font size="2"></font><font color="#003333" face="'trebuchet ms', sans-serif">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.</font></div>
<div><div><div dir="ltr"><font><font face="'trebuchet ms', sans-serif"><i><font color="#003333"><br><font color="#888888">-- Russ </font></font></i></font></font></div><div><div></div><div class="h5"><br>
<br><br><div class="gmail_quote">On Wed, Nov 24, 2010 at 1:52 PM, Daniel Fischer <span dir="ltr"><<a href="mailto:daniel.is.fischer@web.de" target="_blank">daniel.is.fischer@web.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>On Wednesday 24 November 2010 22:12:37, Russ Abbott wrote:<br>
> Cool. I wasn't aware of that notation. It doesn't quite get to the<br>
> issue though.<br>
><br>
> The problem I'm concerned about is the need to define y in the first<br>
> place. If one is chasing through a data structure and finds a need to<br>
> change something buried within it, it seems necessary to rebuild<br>
> everything that includes the changed thing.<br>
<br>
</div>In general, values are immutable, so you can't "change something buried<br>
within it". You have to build a new value containing some of the old stuff<br>
and a new part. Building the new value usually consists mostly of copying a<br>
couple of pointers (plus building the new part of course), so isn't too<br>
expensive normally.<br>
<br>
You can have mutable values in the IO or (ST s) monads, if you need them.<br>
<div><br>
> That is, I can't change a<br>
> component of somethingNew without creating y. The point is there's<br>
> nothing about x that changed,<br>
<br>
</div>The thing with the changed component is not x anymore.<br>
<div><br>
> and there may be nothing about (var1 x)<br>
> that changed, and there may be nothing about var11 . var1 $ x that<br>
> changed, etc. Yet one is apparently forced to keep track of and<br>
> reconstruct all those elements.<br>
<br>
</div>The compiler takes care of that.<br>
<div><br>
><br>
> Another example is to imagine a Tree in which the leaves contain<br>
> "objects." If I want to change a property of one of those leaf objects,<br>
<br>
</div>You can't in general, the thing with a different property is a different<br>
object.<br>
<div><br>
> I am forced to rebuild all the ancestor nodes of that leaf down to<br>
> rebuilding the root.<br>
<br>
</div>Yes (well, not you, the compiler does it), except if your tree contains<br>
mutable objects (IORefs/STRefs for example).<br>
<div><br>
><br>
> One way to avoid that is for the leaves to refer to their objects<br>
> through a Map. Then changing a leaf object requires only that the value<br>
> associated with key represented by the leaf be (re-)inserted into the<br>
> Map. The Tree itself need not change at all.<br>
<br>
</div>Oh, it will. If you change a Map, you get a new one, thus you get a new<br>
tree containing the new Map.<br>
<div><br>
><br>
> But that trick isn't always available. In the example we are talking<br>
> about we can't make a Map where they keys are the instance variable<br>
> names and the values are their values. That would seem to do the job,<br>
> but since the values are of different types, we can't create such a Map.<br>
><br>
> So now what?<br>
<br>
</div>Well, what's the problem with the compiler copying some nodes?<br>
Normally, that doesn't cost very much performance, if it does in your case,<br>
we'd need to know more to suggest the best way to go.<br>
<br>
> *<br>
> -- Russ *<br>
><br>
</blockquote></div><br></div></div></div></div></div>
</blockquote></div><br></div>