Search control in Haskell

Suppose you're writing a program that searches an exponentially large or infinite space: gameplaying, theorem proving, optimization etc, anything where you can't search the entire space, and the quality of results depends heavily on choosing which parts of it to search within available resources.

In an eager language, this is conceptually straightforward: the language lets you specify order of evaluation, and you use that to control what parts of the search space to evaluate first. (In practice, it tends to get messy and complicated because your code layout for inference control gets mixed in with the problem definition, which is one of the reasons I'm interested in ways to do this in a lazy language instead. But it is conceptually straightforward.)

In a lazy language like Haskell, you can't do it that way. I can think of two ways of doing it instead:

1. Write code that depends on the exact order of evaluation that happens to be chosen by the current version of the compiler you are using, with the optimization flags you are using, so that stuff ends up happening in just the right order. This seems likely to lead to maintainability issues.

2. Write code that writes code, specifically, write code that transforms the problem definition together with a set of heuristics, into a sequence of instructions in an eager language, that specifies the exact order in which things should be done. This seems to h开发者_JAVA百科ave merit, if you're willing to pay the upfront costs.

Are there other recommended ways to do this sort of thing?

The typical way of doing this in a lazy language is to define the search space as a (possibly infinite) data structure and then write whatever strategy you wish to use to traverse this structure separately. This way, you're in control of the strategy used, but it's kept separate from the problem definition.

You can make parts of your haskell code to be based on strict evaluation

http://www.haskell.org/haskellwiki/Performance/Strictness