<div dir="ltr"><font class="Apple-style-span" color="#003333" face="'trebuchet ms', sans-serif">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. </font><br clear="all">
<div dir="ltr"><font><font face="'trebuchet ms', sans-serif"><i><font color="#003333"><br>-- Russ </font></i></font></font></div><br>
<br><br><div class="gmail_quote">On Thu, Nov 25, 2010 at 6:17 AM, Patrick LeBoutillier <span dir="ltr"><<a href="mailto:patrick.leboutillier@gmail.com">patrick.leboutillier@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Russ,<br>
<br>
If I understand correctly KenKen is something like Sudoku except that<br>
the (more complicated) "cages"<br>
constraints replace the usual "square" constraints.<br>
<br>
Have you seen these sudoku solvers: <a href="http://www.haskell.org/haskellwiki/Sudoku" target="_blank">http://www.haskell.org/haskellwiki/Sudoku</a> ?<br>
<br>
Maybe you can get ideas there on how to attack the problem in a more<br>
functional fashion.<br>
<br>
<br>
Patrick<br>
<div><div></div><div class="h5"><br>
<br>
On Wed, Nov 24, 2010 at 9:58 PM, Russ Abbott <<a href="mailto:russ.abbott@gmail.com">russ.abbott@gmail.com</a>> wrote:<br>
> My previous two messages suggest a Haskell coding principle: distinguish<br>
> between fixed and (quasi-)mutable data structures. (I know values don't<br>
> change, but I hope you understand what I mean. The cage and the cell in my<br>
> previous example are quasi-mutable. They are conceptually mutable in the<br>
> context of the problem.) The fixed data structures can be organized any way<br>
> one wants. The quasi-/conceptually-mutable elements should be referred to<br>
> symbolically and stored in a Map. The maps themselves should be stored at a<br>
> global level of the system's data structure so that it is easy to replace<br>
> them when values change.<br>
><br>
> -- Russ<br>
><br>
><br>
> On Wed, Nov 24, 2010 at 5:54 PM, Russ Abbott <<a href="mailto:russ.abbott@gmail.com">russ.abbott@gmail.com</a>> wrote:<br>
>><br>
>> Actually using a Map does solve the problem. The Map has to be kept at the<br>
>> level of the Tree rather than have each leaf node point to it. So instead<br>
>> of just a Tree one has, say (Map, Tree). Then when one wants to change the<br>
>> property of something associated with a leaf node, one can just change the<br>
>> map. The Tree is unchanged.<br>
>><br>
>> -- Russ<br>
>><br>
>><br>
>><br>
>> On Wed, Nov 24, 2010 at 2:02 PM, Russ Abbott <<a href="mailto:russ.abbott@gmail.com">russ.abbott@gmail.com</a>><br>
>> wrote:<br>
>>><br>
>>> OK. So putting a Map at Leaf nodes doesn't solve the problem.<br>
>>> (Apparently I haven't been able to communicate what I see as the problem.)<br>
>>> The problem that I'm trying to get to is the need to write excessive code<br>
>>> for something that would require a lot less code in an OO world. It's not a<br>
>>> matter of execution time or space. It's a matter of the amount of code one<br>
>>> is required to write.<br>
>>> -- Russ<br>
>>><br>
>>><br>
>>> On Wed, Nov 24, 2010 at 1:52 PM, Daniel Fischer<br>
>>> <<a href="mailto:daniel.is.fischer@web.de">daniel.is.fischer@web.de</a>> wrote:<br>
>>>><br>
>>>> 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>
>>>> 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<br>
>>>> stuff<br>
>>>> and a new part. Building the new value usually consists mostly of<br>
>>>> 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<br>
>>>> them.<br>
>>>><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>
>>>> The thing with the changed component is not x anymore.<br>
>>>><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>
>>>> The compiler takes care of that.<br>
>>>><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<br>
>>>> > objects,<br>
>>>><br>
>>>> You can't in general, the thing with a different property is a different<br>
>>>> object.<br>
>>>><br>
>>>> > I am forced to rebuild all the ancestor nodes of that leaf down to<br>
>>>> > rebuilding the root.<br>
>>>><br>
>>>> Yes (well, not you, the compiler does it), except if your tree contains<br>
>>>> mutable objects (IORefs/STRefs for example).<br>
>>>><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<br>
>>>> > 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>
>>>> 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>
>>>><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<br>
>>>> > Map.<br>
>>>> ><br>
>>>> > So now what?<br>
>>>><br>
>>>> 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<br>
>>>> case,<br>
>>>> we'd need to know more to suggest the best way to go.<br>
>>>><br>
>>>> > *<br>
>>>> > -- Russ *<br>
>>>> ><br>
>>><br>
>><br>
><br>
><br>
</div></div>> _______________________________________________<br>
> Beginners mailing list<br>
> <a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
> <a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
><br>
><br>
<font color="#888888"><br>
<br>
<br>
--<br>
=====================<br>
Patrick LeBoutillier<br>
Rosemère, Québec, Canada<br>
</font></blockquote></div><br></div>