Thread: [q-lang-users] newbie: backtracking?

Brought to you by: agraef

q-lang-users

[q-lang-users] newbie: backtracking?

From: Arnoldo J. M. M. <ar...@da...> - 2005-10-26 03:56:34

Hi All:

I was reading the manual and it says the matching process explicitly
takes the first (from top to bottom) equation that matches (or the
equation with the highest priority) . Is there a way to make q backtrack
all the possible matchings instead of just the first? 

Thanks in advance,

AM.

Re: [q-lang-users] newbie: backtracking?

From: Albert G. <Dr....@t-...> - 2005-10-26 06:55:10

Arnoldo Jose Muller Molina wrote:
> I was reading the manual and it says the matching process explicitly
> takes the first (from top to bottom) equation that matches (or the
> equation with the highest priority) . Is there a way to make q backtrack
> all the possible matchings instead of just the first? 

Yes. The builtin fail function tells the interpreter to abort the 
current equation and try the next applicable one. Please see the "8 
queens" example in examples/queens2.q and section 10.6 in the manual 
(http://q-lang.sourceforge.net/qdoc/qdoc_10.html#SEC54).

There's also a purely functional way to do this, namely to enumerate the 
entire solution space as a stream (infinite list) and then traverse that 
stream to extract the wanted solutions. See examples/queens.q for an 
example. (But the "dirty" version using fail is usually much faster.)

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikwissenschaft.uni-mainz.de/~ag