[Haskell-beginners] backtracking search and memory usage

[Kim-Ee Yeoh]

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 at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140315/b81fdebe/attachment.html>