Prolog - Generate alternating symbols on backtrack: [a] ; [a,b]; [a,b,a]; [a,b,a,b]

Question

I've wrapped my mind a lot and couldn't figure it out. Is it possible to make a script that with backtrack generates lists in this format:

[a]
[a,b]
[a,b,a]
[a,b,a,b]
...

I've made one that generates two elements at a time but my head started to hurt trying to make one that generates "a" and the next time "b" and the next "a" and so on.

Here is the script for two elements at a time:

ab([a]).
ab([b,a|T]):-ab([a|T]).
ab([a,b|T]):-ab([b|T]).

Answer 1

When describing lists, always consider using DCG notation.

This makes it very convenient to focus an the essence of what you want to describe, without so many additional variables and arguments.

For example, consider:

abs --> [a], abs_rest.

abs_rest --> [].
abs_rest --> [b], ( [] | abs ).

Sample query and answer:

?- phrase(abs, ABs).
ABs = [a] ;
ABs = [a, b] ;
ABs = [a, b, a] ;
ABs = [a, b, a, b] ;
ABs = [a, b, a, b, a] ;
ABs = [a, b, a, b, a, b] .

See dcg for more information about this convenient formalism!

Answer 2

I agree with @mat that one should use dcg when possible for these type of problems.

Here is a different set of rules.

abs --> [a].
abs --> [a,b].
abs --> [a,b], abs.

?- phrase(abs, Ls).
Ls = [a] ;
Ls = [a, b] ;
Ls = [a, b, a] ;
Ls = [a, b, a, b] ;
Ls = [a, b, a, b, a] ;
Ls = [a, b, a, b, a, b] ;
Ls = [a, b, a, b, a, b, a] ;
Ls = [a, b, a, b, a, b, a, b] ;
Ls = [a, b, a, b, a, b, a, b, a] 

Interestingly those rules started from this variation

abs2 --> [].
abs2 --> [a].
abs2 --> [a,b], abs2.

?- phrase(abs2, Ls).
Ls = [] ;
Ls = [a] ;
Ls = [a, b] ;
Ls = [a, b, a] ;
Ls = [a, b, a, b] ;
Ls = [a, b, a, b, a] ;
Ls = [a, b, a, b, a, b] ;
Ls = [a, b, a, b, a, b, a] ;
Ls = [a, b, a, b, a, b, a, b] 

which is one of the exercises from Using Definite Clause Grammars in SWI-Prolog

If you prefer not to use DCG, then I agree with @mat and suggest that you use listing/1 to see the DCG in standard Prolog syntax.

listing(abs).

abs([a|A], A).
abs([a, b|A], A).
abs([a, b|A], B) :-
        abs(A, B).

listing(abs2).  

abs2(A, A).
abs2([a|A], A).
abs2([a, b|A], B) :-
        abs2(A, B).

As normal Prolog rules they can be used as such:

abs(X,[]).
X = [a] ;
X = [a, b] ;
X = [a, b, a] ;
X = [a, b, a, b] ;
X = [a, b, a, b, a] ;
X = [a, b, a, b, a, b] ;
X = [a, b, a, b, a, b, a]

abs2(X,[]).
X = [] ;
X = [a] ;
X = [a, b] ;
X = [a, b, a] ;
X = [a, b, a, b] ;
X = [a, b, a, b, a] ;
X = [a, b, a, b, a, b]