Search code examples
listprologdcg

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

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]).
Solution

  • 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 for more information about this convenient formalism!