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

сначала посмотрите на следующий пример:

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

false Хорошо, потому что второй аргумент должен быть отсортированным списком из двух элементов. (В моей программе я предполагаю, что 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).

prolog failure-slice
person Community    schedule 18.05.2016    source источник
comment
Вы пытались сделать trace, чтобы посмотреть, что происходит?   -  person lurker    schedule 18.05.2016
comment
Да, я пробовал. Когда мы добавляем ! после fp(L, AccA, [c|AccB], F)., это не зацикливается, но дает неверный результат (не все возможности), когда первым аргументом является X.   -  person    schedule 18.05.2016
comment
В вашем последнем предложении X и AccA являются одноэлементными. Это намеренно? Кроме того, второе предложение к fp/4 вызывает fp([b|AccA], _, F) (fp/3), которого не существует.   -  person lurker    schedule 18.05.2016
comment
Ок, ошибся при написании поста, исправил.   -  person    schedule 18.05.2016
comment
Код, который вы показываете, не дает результатов, которые вы показываете.   -  person lurker    schedule 18.05.2016
comment
Посмотрите еще раз, извините за мои ошибки.   -  person    schedule 18.05.2016
comment
append(_, [b|AccB], F) и append([a|AccA], _, F) напрашиваются на неприятности. Существует почти бесконечное количество решений для этих запросов, и (если вы посмотрите на свой trace) ваш код зацикливается, проверяя каждое из них, пытаясь найти другое решение. Вы хотите подумать о рефакторинге, чтобы избежать этих конкретных запросов.   -  person lurker    schedule 18.05.2016
comment
Сначала удалите !/0: это разрушает логический смысл вашей программы. Например, попробуйте с текущей версией запрос: ?- fp(L, F).. Вы получаете только единственное решение, F = L = []. Очевидно, должно быть гораздо больше терминов, для которых выполняется это соотношение!   -  person mat    schedule 18.05.2016
comment
Избежать append не так просто..   -  person    schedule 18.05.2016
comment
@HaskellFun да, append/3 очень удобен и всегда заманчив для использования. Однако иногда более подходящим является пользовательский предикат, который более точно делает то, что вам нужно, а иногда есть способ ограничить аргументы для append/3, чтобы они были более ограниченными. Или, может быть, есть способ полностью переосмыслить проблему...   -  person lurker    schedule 18.05.2016

Ответы (1)


arrow_upward
1
arrow_downward

Проблема в том, что запрос к 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
| ?-
person lurker    schedule 18.05.2016
comment
Большое спасибо, я не знаю, что это легко исправить. - person ; 18.05.2016