Re: [Haskell-beginners] Question about data structures

On Thu, Nov 25, 2010 at 09:12:05AM -0800, Russ Abbott wrote:

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 *

Someone did respond to your question, with a link to the data-accessor package on Hackage (you could also take a look at fclabels or lenses). Do those help address your issue? -Brent

On Thu, Nov 25, 2010 at 6:17 AM, Patrick LeBoutillier < patrick.leboutillier@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

...

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 wrote:

...

Actually using a Map does solve the problem. The Map has to be kept at

...

...

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

...

...

property of something associated with a leaf node, one can just change

...

...

map. The Tree is unchanged.

-- Russ

On Wed, Nov 24, 2010 at 2:02 PM, Russ Abbott 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

...

...

...

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 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

On Wed, Nov 24, 2010 at 9:58 PM, Russ Abbott wrote: the the the problem.) 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@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners