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 [1].
>
> 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,
multiple 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.
Jerzy Karczmarczuk
Caen, France
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
