; ******************************** EXTRAS *********************************
;
;
; definitions for useful predicates like "and" ,"or", "find_all" 
; the 'and' and 'or' operators (usually represented by , and ; respectively)

? op (1, "and"), op (1, "or").

G and G' <- G, G'.

G or G' <- G.
G or G' <- G'.


; The quicksort algorithm in Prolog  (Sterling & Shapiro program 15.4)
; ? quicksort([3,5,2,7,1],Xs) will give Xs = [1,2,3,5,7].
; partition ([3,5,2,7,1],3,Littles, Bigs) gives Littles = [3,2,1], Bigs = [5,7].
; Littles and Bigs are quicksorted in their turn, and the results appended
; using difference-lists (Sterling & Shapiro chapter 15) 

quicksort (Xs,Ys) <- quicksort_dl (Xs,Ys\[]).
quicksort_dl ([X|Xs], Ys\Zs)  <-
     partition (Xs,X,Littles,Bigs),
     quicksort_dl (Littles, Ys\[X|Ys']),
     quicksort_dl (Bigs, Ys'\Zs).
quicksort_dl ([],Xs\Xs).
partition ([X|Xs],Y,[X|Littles],Bigs) <-
     X <= Y, !, partition (Xs,Y,Littles,Bigs).      
partition ([X|Xs],Y,Littles,[X|Bigs]) <-
     X > Y, !, partition (Xs,Y,Littles,Bigs).      
partition ([],Y,[],[]).

; reversing a list ussing difference-lists:
 
reverse (Xs,Ys) <-  reverse_dl(Xs, Ys\[]).
reverse_dl ([X|Xs],Ys\Zs) <-
     reverse_dl (Xs,Ys\[X|Zs]).
reverse_dl ([],Xs\Xs).

rev(X,Y) <- string(X,Z),reverse(Z,Z'), string(Y,Z').

; find_all (X, f(X,...), Xs) gives Xs = the set of X such that f(X,...)

find_all (X, Goal, Xs) <- find_all_dl (X, Goal, Xs\[]).

find_all_dl (X, Goal, Xs\Ys) <-
     asserta ([$instance ($mark)]), Goal, asserta ([$instance(X)]),fail.
find_all_dl (X, Goal, Xs\Ys)  <-
     retract ([$instance(X')]), reap (X', Xs\Ys).

reap (X, Xs\Ys)   <-
     X \= $mark, retract ([$instance (X1)]), !, reap (X1, Xs\[X|Ys]).
reap ($mark, Xs\Xs).