<div dir="ltr">Let's look at the requirements for this problem, uncovering some of the unspoken ones:<br><br>1. very general problem<br>2. fast, or at least not too slow<br>3. memory-efficient<br>4. correct<br><br>Leaving aside performance issues 2 and 3, is it possible that 1 and 4 alone are enough to deliver plenty of heartburn?<br>

<br>I can think of at least one class of problems: the enumeration and application of choices lead to cyclical states. Hence resulting in a list of solutions pockmarked with bottoms.<br><br>I mean your backtrack function is a correct and succinct description of the very notion of backtracking. The devil is in the details of state design, including the enumeration and application issues I've described.<br>

<br>By narrowing the scope of the problem so that you first obtain a library that correctly solves it, you could then focus on performance issues.<br><br></div><div class="gmail_extra"><br clear="all"><div>-- Kim-Ee</div>


<br><br><div class="gmail_quote">On Sat, Mar 15, 2014 at 9:06 AM, Dennis Raddle <span dir="ltr"><<a href="mailto:dennis.raddle@gmail.com" target="_blank">dennis.raddle@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<div dir="ltr"><div><div><div><div><div><div><div><div>I want to implement backtracking search, but I wonder if I'm going to immediately run into memory usage problems if I don't use strict evaluation somewhere. I'm very hazy on how to implement strict evaluation. I'm thinking of creating a generic algorithm that looks something like the following.<br>


<br></div>We have the concept of a data construct that can be built step by step. At each step are choices. We are investigating all the choices and finding series of choices that lead to a completed data construct or "solution." We want to generate a list of all solutions. <br>


<br></div><div>(My Haskell syntax is rusty so there may be errors in the following.)<br></div><div><br><br></div>class Construct a where<br></div>  enumerateChoices :: a -> [b]<br></div>  applyChoice :: a -> b -> a<br>


</div>  isSolution :: a -> Bool<br><br></div>backtrack :: Construct a => a -> [a]<br></div>backtrack c <br>  | isSolution c = [c]<br></div><div>  | otherwise = <br></div><div>     concat . map (backtrack . applyChoice c) . enumerateChoices $ c<br>


</div>    <br><div><div><div><div><div>So my question is whether this is going to use a lot of memory to run, maybe by holding all partially solved data? Where would strict evaluation go?<br></div><div><div><br><div><div>


<div><br><br></div></div></div></div></div></div></div></div></div></div>
<br>_______________________________________________<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></blockquote></div><br></div>