<div dir="ltr"><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">Thanks, I'm still struggling with it. But here is what it looks like now.</font></font></font><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br>
</font></font></font></div><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">I'm working on a KenKen solver. One issue I'm having is that I'm not sure how many types to declare -- where by types I mean a "type X = ..." declaration. The more there are the better documented the code, but the more there are the harder it seems to be to remember what they all are. I've pasted the current version of my declarations below. By way of explanation, here's the representation strategy.</font></font></font></div>
<div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br></font></font></font></div><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">The puzzle board is called a Grid. It consists primarily of a Map CellRef Cells. I'm using a Map instead of an array (list of lists) as a way to avoid rebuilding the list of lists of cells when a Cell gets a value. A CellRef is (Int, Int) for row and column. A Cell contains its own CellRef along with a reference to the Cage that refers to it. It also has a place to put its actual value, an Int (called type CellValue). (In the current version a Cell has one value. In a subsequent version it will be more like a FiniteDomain variable with a Set of still possible values.)</font></font></font></div>
<div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br></font></font></font></div><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">A Grid also contains two other Maps. Each is of the type Map Int ValueSet. One of them represents the unused values for the rows; the other the unused values for the columns. A ValueSet is a Set of allowable values. If the puzzle is (size x size), its ValueSet will be Set.fromList [1 .. size].</font></font></font></div>
<div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br></font></font></font></div><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">The other main structure is the puzzle presentation, which is called a KenKen. It is a list of Cages, where a Cage is: a target value (what the operation on the cells has to come out to), an Op (the Operation to be performed), and a list of CellRef (which are (row, col) references to Cells).</font></font></font></div>
<div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br></font></font></font></div><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">When I give a Cell a value, I am forced to rebuild: the Map of row ValueSets, the Map of column ValueSets, the Map of Cells themselves, and the Grid that contains all these pieces. In this case, the pieces do change. (The cell changes since it gets a value; the candidates still left for the row and column also change since that value is no longer available.) But still it's a pain rebuilding it all.</font></font></font></div>
<div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br></font></font></font></div><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">So perhaps the first question is whether there is a cleaner and simpler way to represent all this.</font></font></font></div>
<div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br></font></font></font></div><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br></font></font></font></div>
<div>
<font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br></font></font></font></div><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><div>type CellValueList = [CellValue]</div>
<div><br></div><div>type CellRef = (Int, Int) </div><div><br></div><div>type CellValue = Int</div><div><br></div><div>data Grid = Grid { rowCandidatesSets :: CandidatesSets</div><div> , colCandidatesSets :: CandidatesSets</div>
<div> , gridCells :: (Map CellRef Cell) </div><div> }</div><div><br></div><div>type KenKen = [Cage]</div><div> </div><div>type ValueSet = Set CellValue</div>
<div><br></div><div>type CandidatesSets = Map Int ValueSet</div><div><br></div><div>data Cell = Cell { cellRef :: CellRef </div><div> , cage:: Cage</div><div> , value:: CellValue</div>
<div> } deriving (Eq, Show)</div><div> </div><div>row cell = fst (cellRef cell)</div><div>col cell = snd (cellRef cell)</div><div> </div><div><br></div>
<div>data Cage = Cage {target :: CellValue</div><div> , op :: Op</div><div> , cageCells :: [CellRef]</div><div> } deriving (Eq, Show)</div>
<div><br></div><div>data Op = Add | Subtract | Multiply | Divide deriving (Show, Eq)</div><div><br></div></font></font></font></div><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br>
</font></font></font></div><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br clear="all"></font></font></font><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 Wed, Nov 24, 2010 at 2:19 PM, matthew coolbeth <span dir="ltr"><<a href="mailto:mac01021@engr.uconn.edu">mac01021@engr.uconn.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
May we see a code sample of what you're describing?<br>
<br>
Generally, when you're writing haskell programs, you will not approach<br>
the problem in the same way that you would appoach it in a language<br>
with mutable objects.<br>
<br>
If you can provide a reasonably simple example of a computing task<br>
that someone would want to perform, I'm sure someone will be able to<br>
show you how it would be best approached in haskell, and how you need<br>
not write too many lines of code, provided that you use the proper,<br>
idiomatic style.<br>
<div><div></div><div class="h5"><br>
On 2010-11-24, Russ Abbott <<a href="mailto:russ.abbott@gmail.com">russ.abbott@gmail.com</a>> wrote:<br>
> OK. So putting a Map at Leaf nodes doesn't solve the problem. (Apparently<br>
> I haven't been able to communicate what I see as the problem.)<br>
><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>
> *<br>
> -- Russ *<br>
><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 stuff<br>
>> and a new part. Building the new value usually consists mostly of copying<br>
>> 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 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 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 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 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><font color="#888888">--<br>
mac<br>
</font></blockquote></div><br></div></div>