On 09-Apr-2001, Jerzy Karczmarczuk
The usual way of handling backtracking in Haskell is using lazy lists. ... This is a way to deal with *data backtracking*. Sure, most of classical combinatoric algorithms belong to this category, the gene- ration of permutations/combinations, 8 queens, etc. And of course
Fergus Henderson wrote: the non-deterministic parsing.
But there is also the question of *control backtracking*, used to emulate iterations, etc. This may be implemented functionally as well by using continuations.
Using continuations to implement backtracking is another important idiom, I agree. (In fact, that is how the new back-end for the Mercury compiler deals with backtracking Mercury code: it converts it into C (or IL, or Java) code that uses continuation passing to handle the backtracing.) However, in a lazy functional language, I'm not sure that you can so easily or usefully distinguish between _control_ backtracking and _data_ backtracking. In a lazy functional language the control flow is mainly implicit rather than explicit, and is determined by the data flow.
You may have conditional continuations, multiple continuations,...
If you use other lazy data structures, e.g. lazy trees rather than lazy
lists, then you can do the same kinds of things that you could do using
conditional or multiple continuations.
--
Fergus Henderson