Next: , Up: prolog-libraries   [Index]


16.13.1 Interleaving constructs.

Generally prolog empowers a depth first search. But with the interleaving constructs it is at least in principle possible to do a wide search. Especially if there is branches that are huge or infinite, a solver can get stuck in that branch, missing a simple shallow solution in another branch. The interleaving constructs can cure this.

16.13.1.1 Api

or_i(branch,...), will execute branch... cyclically e.g. first try branch1, if that fails, then try branch2 and if branch-n, the end branch fails, then start all over from the beginning with the next try of branch1 and so on.

and_i(factor,...), will interleave the backtracking of factor... when the whole expression backtracks.

or_union(branch,...), The same as with or_i, but any results will be unique.

16.13.1.2 Examples

/* X = A,A+1,A+2,...,A+10  */
c(X,A)   :- c(X,A,0). 
c(X,A,N) :- N < 10, 
              (X = A ; (B is A + 1, M is N + 1, c(X,B,M))).

/* or_i test */
f1(X) :- or_i(c(X,0),c(X,100)).

/* and_i test */
f2(X,Y) :- and_i(c(X,0),c(Y,100)).

/* or_union test */
f3(X) :- or_union(c(X,0),c(X,2)).

(prolog-run 10 (X)   (f1 X))
$1 = (0 100 1 101 2 102 3 103 4 104)

(prolog-run 10 (X Y) (f2 X Y))
$2 = ((0 100) (1 100) (0 101) (2 100) (1 101) 
      (0 102) (3 100) (2 101) (1 102) (0 103))

(prolog-run 10 (X)   (f3 X))
$3 = (0 2 1 3 4 5 6 7 8 9)