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