Разделение списка целых чисел на список положительных чисел и список отрицательных чисел - PullRequest
Новая
       14

Разделение списка целых чисел на список положительных чисел и список отрицательных чисел

7 голосов
/ 03 марта 2012

Я пытался создать предикат в Прологе, который разбивает список целых чисел на список целых положительных чисел и список отрицательных целых чисел.

Пример запроса с ожидаемым результатом: 

?- split([1,-2,3,4,-8],X,Y).
X = [1,3,4],
Y = [-2,-8].

Это код, который я получил до сих пор: 

split([], [], []).
split([Head|Tail], List1, List2) :- split(Tail, [Head|List1], List2), Head>=0.
split([Head|Tail], List1, List2) :- split(Tail, List1, [Head|List2]), Head<0.

Я не могу понять, что я делаю неправильно.

Ответы [ 4 ]

9 голосов
/ 03 марта 2012

Рекурсивная часть не совсем корректна. 

split([], [], []).
split([Head|Tail], [Head|List1], List2) :- Head>=0, split(Tail, List1, List2).
split([Head|Tail], List1, [Head|List2]) :- Head<0, split(Tail, List1, List2).

Head следует добавить в положительный список, если Head >= 0, и в отрицательный список, когда Head < 0.

* 1008.* Кроме того, лучше проверять знак Head в начале , поскольку это предотвратит ненужные рекурсивные вызовы.
6 голосов
/ 03 марта 2012

В SWI-Prolog вы можете использовать предикат partition/4 (который обычно автоматически загружается из модуля apply): 

?- partition(=<(0), [1,-2,3,4,-8,0], X, Y).
X = [1, 3, 4, 0],
Y = [-2, -8].
3 голосов
/ 03 марта 2012

Вот определение, использующее ограничения. В этом случае это library(clpfd) SWI и YAP (возможно, также XSB). Эта библиотека настолько общая, что включает в себя обычные целочисленные значения. 

:- use_module(library(clpfd)).

Использование reification: 

split([], [], []).
split([E|Es], Poss, Negs) :-
   E #>= 0 #<==> B,
   i_split(B, E, Es, Poss, Negs).

i_split(1, E, Es, [E|Poss], Negs) :-
   split(Es, Poss, Negs).
i_split(0, E, Es, Poss, [E|Negs]) :-
   split(Es, Poss, Negs).

В качестве альтернативы вы можете использовать zcompare/3, я предпочитаю эту версию: 

split([], [], []).
split([E|Es], Poss, Negs) :-
   zcompare(Order, E, 0),
   c_split(Order, E, Es, Poss, Negs).

c_split(>, E, Es, [E|Poss], Negs) :-
   split(Es, Poss, Negs).
c_split(=, E, Es, [E|Poss], Negs) :-
   split(Es, Poss, Negs).
c_split(<, E, Es, Poss, [E|Negs]) :-
   split(Es, Poss, Negs).

Вы можете использовать его как для обычных запросов, так и для более общих, например 

?- split(Es,[A],[]).
Es = [A],
A in 1..sup ;
Es = [0],
A = 0 ;
false.
2 голосов
/ 05 мая 2015

Оставайтесь логически чистыми и эффективными. Как? С помощью мета-предиката tpartition/4 и (#=<)/3!

Во-первых, давайте определим (#=<)/3, усовершенствованную версию (#=<)/2, основанную bool01_t/2.
Для полноты картины давайте также определим (#<)/3, (#>)/3 и (#>=)/3! 

#=<(X,Y,Truth) :- X #=< Y #<==> B, bool01_t(B,Truth).

#<( X,Y,Truth) :- X #<  Y #<==> B, bool01_t(B,Truth).

#>( X,Y,Truth) :- X #>  Y #<==> B, bool01_t(B,Truth).

#>=(X,Y,Truth) :- X #>= Y #<==> B, bool01_t(B,Truth).

Вот и все! Теперь давайте сделаем разделение, которое хотел ОП: 

?- tpartition(#=<(0),[1,-2,3,4,-8,0],Ts,Fs).
Ts = [1,3,4,0], Fs = [-2,-8].                   % succeeds deterministically

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

?- tpartition(#=<(0),[A,B,C],Ts,Fs).
Ts = [     ], Fs = [A,B,C], A in inf.. -1, B in inf.. -1, C in inf.. -1 ;
Ts = [    C], Fs = [A,B  ], A in inf.. -1, B in inf.. -1, C in   0..sup ;
Ts = [  B  ], Fs = [A,  C], A in inf.. -1, B in   0..sup, C in inf.. -1 ;
Ts = [  B,C], Fs = [A    ], A in inf.. -1, B in   0..sup, C in   0..sup ;
Ts = [A    ], Fs = [  B,C], A in   0..sup, B in inf.. -1, C in inf.. -1 ;
Ts = [A,  C], Fs = [  B  ], A in   0..sup, B in inf.. -1, C in   0..sup ;
Ts = [A,B  ], Fs = [    C], A in   0..sup, B in   0..sup, C in inf.. -1 ;
Ts = [A,B,C], Fs = [     ], A in   0..sup, B in   0..sup, C in   0..sup .

Редактировать 2015-06-02

Что если мы использовали предикат библиотеки SWI-Prolog partition/4 в запросе выше? 

?- partition(#=<(0),[A,B,C],Ts,Fs).
Ts = [A,B,C], Fs = [], A in 0..sup, B in 0..sup, C in 0..sup.

Мы бы потеряли 7 из 8 решений, потому что partition/4 не является монотонным!

...