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

Question

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

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

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

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

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

Answer 1

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

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

Для примера рассмотрим:

 
abs --> [a], abs_rest. 

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

Пример запроса и ответа:

 
?- 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] . 

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

Answer 2

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

Это - другие правила.

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] 

, который является одним из упражнений из Using Definite Clause Grammars in 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). 

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

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] 

Answer 3

Предикат Вы писали слишком общо:

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

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

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

Можно сказать, что вы cribe промежуточный результат, который не является решением вашей реальной проблемы.Чтобы исправить это, можно утверждать, чем 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). 

Удачи :)