Вопрос: Prolog - генерировать чередующиеся символы на обратном пути: [a]; [А, Ь]; [А, Ь, а]; [А, Ь, а, Ь]


Я много обдумал и не мог понять. Можно ли создать скрипт, который с помощью backtrack генерирует списки в этом формате:

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

Я создал тот, который генерирует два элемента за раз, но моя голова начала болеть, пытаясь создать тот, который генерирует «а», а в следующий раз «b» и следующий «а» и так далее.

Вот сценарий для двух элементов за раз:

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

4


источник


Ответы:


При описании списки , всегда рассматривайте использование Обозначение DCG ,

Это делает очень удобным сосредоточить сущность  о том, что вы хотите описать, без большого количества дополнительных переменных и аргументов.

Например, рассмотрим:

abs -> [a], abs_rest.

abs_rest -> [].
abs_rest -> [b], ([] | 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].
 

Видеть  для получения дополнительной информации об этом удобном формализме!


7



Я согласен с @mat, что нужно использовать  когда это возможно для этих проблем.

Вот другой набор правил.

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] 

Интересно, что эти правила начались с этого варианта

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] 

который является одним из упражнений из Использование грамматик с определенными параметрами в SWI-Prolog

Если вы предпочитаете не использовать DCG, то я согласен с @mat и предлагаю вам использовать listing/1 чтобы увидеть DCG в стандартном синтаксисе Prolog.

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

Как обычные правила Prolog они могут быть использованы как таковые:

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] 

3



Предикат, который вы написали, слишком общий:

?- ab([b,a]).
true

Причиной является следующее правило

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

Можно сказать, что вы описываете промежуточный результат, который не является решением вашей реальной проблемы. Чтобы исправить это, вы можете указать, что ab последовательность начинается с a а остальное - быть ba последовательности, где ba последовательности снова определяются в терминах ab последовательности:

ab([a]).
ab([a|Xs]) :-
    ba(Xs).

ba([b]).
ba([b|Xs]) :-
    ab(Xs).

В качестве альтернативы вы могли бы подумать о abs как государственный автомат, который  производит a всякий раз, когда последний элемент b и наоборот.  Если мы введем дополнительный аргумент для отслеживания истории, мы получим:

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

Теперь определим ab последовательности, которая была a:

ab(Xs) :-
    abs(a,Xs).

Повеселись :)


1