[Haskell-beginners] Question about data structures
russ.abbott at gmail.com
Wed Nov 24 20:54:50 EST 2010
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.
On Wed, Nov 24, 2010 at 2:02 PM, Russ Abbott <russ.abbott at gmail.com> wrote:
> 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
>> 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
>> > 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
>> we'd need to know more to suggest the best way to go.
>> > *
>> > -- Russ *
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Beginners