Сортировка списка только два элементов в прологе

Question

во-первых, посмотрите на следующий пример:

?- fp(X,[b,a,b]). 

ложные Ok, потому что второй аргумент должен быть двух элементов отсортированного списка. (В моей программе я предполагаю, что a<b)

?-fp(X,[a,b,b]). 
X = [a, b, b] ; 
X = [b, a, b] ; 
X = [b, b, a] ; 
false. 

Да, это правильный результат.
Однако для

?-fp ([b,a,b], X) 
X = [a,b,b]. 

Да, это ожидаемый результат.
Однако в случае

?-fp ([b,a,b], X) 
X = [a,b,b]; 

Вот обхват ....

Есть ли существует способ борьбы с этим зацикливанием? Я долго думал, но не успел. Можете ли вы попытаться мне помочь?

fp(L, F) :- 
    fp(L, [], [], F). 

fp([], AccA, AccB, F):- 
    append(AccA, AccB, F), !. 
fp([a|L], AccA, AccB, F) :- 
    append([a|AccA], _, F), 
    fp(L, [a|AccA], AccB, F). 
fp([b|L], AccA, AccB, F) :- 
    append(_, [b|AccB], F), 
    fp(L, AccA, [b|AccB], F). 

Answer 1

Проблема заключается в том, что запрос к append/3 с таким количеством переменных дает очень почти неограниченное число решений, чтобы попробовать. Один из способов ограничить это - обеспечить, чтобы длина списка была одинаковой. И, как говорит @mat, вы избавляетесь от сокращения.

fp(L, F) :- 
    same_length(L, F), 
    fp(L, [], [], F). 

fp([], AccA, AccB, F):- 
    append(AccA, AccB, F). 
fp([a|L], AccA, AccB, F) :- 
    append([a|AccA], _, F), 
    fp(L, [a|AccA], AccB, F). 
fp([b|L], AccA, AccB, F) :- 
    append(_, [b|AccB], F), 

same_length/2 определяется в SWI Prolog уже, но имеет простую реализацию:

same_length([], []). 
same_length([_|T1], [_|T2]) :- same_length(T1, T2). 

---

| ?- fp(X, [a,b,b,b]). 

X = [a,b,b,b] ? a 

X = [b,a,b,b] 

X = [b,b,a,b] 

X = [b,b,b,a] 

(1 ms) no 
| ?- fp([a,b,a], X). 

X = [a,a,b] ? a 

no 
| ?-