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?