Let's look at the requirements for this problem, uncovering some of the unspoken ones:

1. very general problem
2. fast, or at least not too slow
3. memory-efficient
4. correct

Leaving aside performance issues 2 and 3, is it possible that 1 and 4 alone are enough to deliver plenty of heartburn?

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.

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.

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.

-- Kim-Ee

On Sat, Mar 15, 2014 at 9:06 AM, Dennis Raddle <dennis.raddle@gmail.com> wrote:

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.

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.

(My Haskell syntax is rusty so there may be errors in the following.)

class Construct a where
enumerateChoices :: a -> [b]
applyChoice :: a -> b -> a

isSolution :: a -> Bool

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

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?

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