Several people, including myself in my long forgotten thesis, have shown
that these are equivalent.
Erik
----- Original Message -----
From: "Jerzy Karczmarczuk"
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