Backtracking (Was: What do you think about Mercury?)
Mon, 9 Apr 2001 10:09:38 -0700
Several people, including myself in my long forgotten thesis, have shown
that these are equivalent.
----- Original Message -----
From: "Jerzy Karczmarczuk" <email@example.com>
Sent: Monday, April 09, 2001 5:08 AM
Subject: Backtracking (Was: What do you think about Mercury?)
> 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,
> 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