Backtracking (Was: What do you think about Mercury?)
Mon, 09 Apr 2001 13:08:48 +0100
Fergus Henderson wrote:
> On 08-Apr-2001, Terrence Brannon wrote:
> > 1- Haskell is a pure functional language, but I don't see any support
> > for backtracking or other logic features... but my guess is you have
> > some way of handling this? How?
> The usual way of handling backtracking in Haskell is using lazy lists.
> See Phil Wadler's 1985 paper .
> For an example of this, I've attached a program for solving the
> 8-queens problem; you can compare this one with the Mercury version
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
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. You may have conditional continuations,
Unfortunately such techniques are rarely taught.
I suspect that Mark Jones' Prolog implementation in Haskell/Gofer
used them, but I don't remember the details.