[Haskell-beginners] Question about data structures

[Russ Abbott]

Thanks, Patrick. I'm disappointed, though, that no one has
actually responded to my question. It wasn't how to solve KenKen. It was how
best to deal with quasi-mutable data structures.
*
-- Russ *



On Thu, Nov 25, 2010 at 6:17 AM, Patrick LeBoutillier <
patrick.leboutillier at gmail.com> wrote:

> Russ,
>
> If I understand correctly KenKen is something like Sudoku except that
> the (more complicated) "cages"
> constraints replace the usual "square" constraints.
>
> Have you seen these sudoku solvers:
> http://www.haskell.org/haskellwiki/Sudoku ?
>
> Maybe you can get ideas there on how to attack the problem in a more
> functional fashion.
>
>
> Patrick
>
>
> On Wed, Nov 24, 2010 at 9:58 PM, Russ Abbott <russ.abbott at gmail.com>
> wrote:
> > 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 *
> >>>> >
> >>>
> >>
> >
> >
> > _______________________________________________
> > Beginners mailing list
> > Beginners at haskell.org
> > http://www.haskell.org/mailman/listinfo/beginners
> >
> >
>
>
>
> --
> =====================
> Patrick LeBoutillier
> Rosemère, Québec, Canada
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20101125/3f86955a/attachment.html