[Haskell-beginners] Question about data structures

[Russ Abbott]

My previous two messages suggest a Haskell coding principle: distinguish
between fixed and (quasi-)mutable data structures. (I know values don't
change, but I hope you understand what I mean. The cage and the cell in my
previous example are quasi-mutable. They are conceptually mutable in the
context of the problem.)  The fixed data structures can be organized any way
one wants. The quasi-/conceptually-mutable elements should be referred to
symbolically and stored in a Map. The maps themselves should be stored at a
global level of the system's data structure so that it is easy to replace
them when values change.
*
-- Russ *



On Wed, Nov 24, 2010 at 5:54 PM, Russ Abbott <russ.abbott at gmail.com> wrote:

> 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.
> *
> -- Russ*
> ***
> *
> **
>
>
> 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
>>> 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/ff71826f/attachment.html