The search algorithm I'm implementing (a simple partial order planner) just has a few choices to make at each invocation. Ideally I would like it to backtrack over the possibilities and return the first found solution.
Take a look at the list ([]) monad instance. It's commonly used for non-determinism.