Backtracking (Was: What do you think about Mercury?)

[Erik Meijer]

Several people, including myself in my long forgotten thesis, have shown
that these are equivalent.

Erik
----- Original Message -----
From: "Jerzy Karczmarczuk" <karczma@info.unicaen.fr>
Cc: <haskell-cafe@haskell.org>
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 [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
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe