[Haskell-beginners] backtracking search and memory usage

[Dennis Raddle]

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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140314/1908a961/attachment.html>