Числа в списке, меньшем заданного числа

Ответ 1

Использование ( if -> then ; else )

Структура управления, которую вы, возможно, ищете, - ( if -> then ; else ).

Предупреждение: вы должны, вероятно, поменять порядок первых двух аргументов:

lessthan_if([], _, []).
lessthan_if([X|Xs], Y, Zs) :-
    (   X < Y
    ->  Zs = [X|Zs1]
    ;   Zs = Zs1
    ),
    lessthan_if(Xs, Y, Zs1).

Однако, если вы пишете настоящий код, вы почти наверняка пойдете с одним из предикатов в library (apply), например include/3, как предложенный @CapelliC:

?- include(>(3), [1,2,3], R).
R = [1, 2].

?- include(>(4), [1,2,3], R).
R = [1, 2, 3].

?- include(<(2), [1,2,3], R).
R = [3].

Смотрите реализацию include/3, если вы хотите узнать, как решаются такие проблемы. Вы заметите, что lessthan/3 выше - это не что иное, как специализация более общей include/3 в библиотеке (применить): include/3 будет изменять порядок аргументов и использовать ( if -> then ; else ).

"Декларативное" решение

Альтернативно, менее "процедурный" и более "декларативный" предикат:

lessthan_decl([], _, []).
lessthan_decl([X|Xs], Y, [X|Zs]) :- X < Y,
    lessthan_decl(Xs, Y, Zs).
lessthan_decl([X|Xs], Y, Zs) :- X >= Y,
    lessthan_decl(Xs, Y, Zs).

(lessthan_if/3 и lessthan_decl/3 почти идентичны решениям Николаса Кэри, за исключением порядка аргументов.)

С другой стороны, lessthan_decl/3 оставляет точки выбора. Тем не менее, это хорошая отправная точка для общего, читаемого решения. Нам нужны два преобразования кода:

• Замените арифметические сравнения < и >= с ограничениями CLP (FD): #< и #>=;
• Используйте правило DCG, чтобы избавиться от аргументов в определении.

Вы прибудете в решение от lurker.

Другой подход

Самый общий предикат сравнения в Prolog - compare/3. Обычный шаблон, использующий его, заключается в явном перечислении трех возможных значений для Order:

lessthan_compare([], _, []).
lessthan_compare([H|T], X, R) :-
    compare(Order, H, X),
    lessthan_compare_1(Order, H, T, X, R).

lessthan_compare_1(<, H, T, X, [H|R]) :-
    lessthan_compare(T, X, R).
lessthan_compare_1(=, _, T, X, R) :-
    lessthan_compare(T, X, R).
lessthan_compare_1(>, _, T, X, R) :-
    lessthan_compare(T, X, R).

(По сравнению с любым из других решений этот будет работать с любыми членами, а не целыми или арифметическими выражениями.)

Замена compare/3 на zcompare/3:

:- use_module(library(clpfd)).

lessthan_clpfd([], _, []).
lessthan_clpfd([H|T], X, R) :-
    zcompare(ZOrder, H, X),
    lessthan_clpfd_1(ZOrder, H, T, X, R).

lessthan_clpfd_1(<, H, T, X, [H|R]) :-
    lessthan_clpfd(T, X, R).
lessthan_clpfd_1(=, _, T, X, R) :-
    lessthan_clpfd(T, X, R).
lessthan_clpfd_1(>, _, T, X, R) :-
    lessthan_clpfd(T, X, R).

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

?- lessthan_clpfd(3, [1,3,2], Xs).
Xs = [1, 2]. % no dangling choice points!

В других случаях он ведет себя так же, как решение DCG lurker:

?- lessthan_clpfd(X, [1,3,2], Xs).
Xs = [1, 3, 2],
X in 4..sup ;
X = 3,
Xs = [1, 2] ;
X = 2,
Xs = [1] ;
X = 1,
Xs = [] .

?- lessthan_clpfd(X, [1,3,2], Xs), X = 3. %
X = 3,
Xs = [1, 2] ; % no error!
false.

?- lessthan_clpfd([1,3,2], X, R), R = [1, 2].
X = 3,
R = [1, 2] ;
false.

Если вам не нужен такой общий подход, include(>(X), List, Result) достаточно хорош.

Ответ 2

Это также можно сделать с помощью DCG:

less_than([], _) --> [].
less_than([H|T], N) --> [H], { H #< N }, less_than(T, N).
less_than(L, N) --> [H], { H #>= N }, less_than(L, N).

| ?- phrase(less_than(R, 4), [1,2,3,4,5,6]).

R = [1,2,3] ? ;

Вы можете написать свой предикат как:

xMenores(N, NumberList, Result) :- phrase(less_than(Result, N), NumberList).

Ответ 3

Вы можете записать его как однострочный, используя findall\3:

filter( N , Xs , Zs ) :- findall( X, ( member(X,Xs), X < N ) , Zs ) .

Однако, я подозреваю, что целью упражнения является изучение рекурсии, поэтому что-то вроде этого будет работать:

filter( _ , []     , []     ) .
filter( N , [X|Xs] , [X|Zs] ) :- X <  N , filter(N,Xs,Zs) .
filter( N , [X|Xs] , Zs     ) :- X >= N , filter(N,Xs,Zs) .

Тем не менее, он распаковывает список дважды при обратном трафике. Оптимизация здесь заключалась бы в том, чтобы объединить 2-й и 3-й пункты, введя мягкий разрез так:

filter( _ , []     , []     ) .
filter( N , [X|Xs] , [X|Zs] ) :-
  ( X < N -> Zs = [X|Z1] ; Zs = Z1 ) ,
  filter(N,Xs,Zs)
  .

Ответ 4

(Это скорее комментарий, чем ответ, но слишком длинный для комментария.)

Некоторые предыдущие ответы и комментарии предложили использовать "if-then-else" (->)/2 или использовать library(apply) meta-predicate include/3. Оба метода работают нормально, если используются только простые простые арифметики Prolog - is/2, (>)/2 и т.д....

?- X = 3, include(>(X),[1,3,2,5,4],Xs).
X = 3, Xs = [1,2].

?-        include(>(X),[1,3,2,5,4],Xs), X = 3.
ERROR: >/2: Arguments are not sufficiently instantiated
% This is OK. When instantiation is insufficient, an exception is raised.

..., но при выполнении кажущегося мягкого переключения от (>)/2 до (#>)/2 мы теряем устойчивость!

?- X = 3, include(#>(X),[1,3,2,5,4],Xs).
X = 3, Xs = [1,2].

?-        include(#>(X),[1,3,2,5,4],Xs), X = 3.
false.
% This is BAD! Expected success with answer substitutions `X = 3, Xs = [1,2]`.

Ответ 5

В этом ответе нет нового кода.

В дальнейшем мы подробно рассмотрим различные изменения этого ответа @lurker.

Редакция # 1, переименована в less_than_ver1//2. Используя dcg и clpfd, код как очень читаемый, так и универсальный

less_than_ver1(_, []) --> [].
less_than_ver1(N, [H|T]) --> [H], { H #< N }, less_than_ver1(N, T).
less_than_ver1(N, L) --> [H], { H #>= N }, less_than_ver1(N, L).

Пусть запрос!

?-  phrase(less_than_ver1(N,Zs),[1,2,3,4,5]).
  N in 6..sup, Zs = [1,2,3,4,5]
; N  = 5     , Zs = [1,2,3,4]
; N  = 4     , Zs = [1,2,3]
; N  = 3     , Zs = [1,2]
; N  = 2     , Zs = [1]
; N in inf..1, Zs = []
; false.

?- N = 3, phrase(less_than_ver1(N,Zs),[1,2,3,4,5]).
  N = 3, Zs = [1,2]       % succeeds, but leaves useless choicepoint
; false.

?-        phrase(less_than_ver1(N,Zs),[1,2,3,4,5]), N = 3.
  N = 3, Zs = [1,2]
; false.

Как небольшое несовершенство, less_than_ver1//2 оставляет некоторые бесполезные точки выбора.

Посмотрим, как обстоят дела с более новой версией...

Редакция № 3, переименована в less_than_ver3//2:

less_than_ver3([],_) --> [].
less_than_ver3(L,N) --> [X], { X #< N -> L=[X|T] ; L=T }, less_than_ver3(L,N).

Этот код использует if-then-else ((->)/2 + (;)/2) для улучшения детерминизма.

Просто повторите предыдущие запросы!

?- phrase(less_than_ver3(Zs,N),[1,2,3,4,5]).
  N in 6..sup, Zs = [1,2,3,4,5]
; false.                              % all other solutions are missing!

?- N = 3, phrase(less_than_ver3(Zs,N),[1,2,3,4,5]).
  N = 3, Zs = [1,2]                   % works as before, but no better.
; false.                              % we still got the useless choicepoint

?-        phrase(less_than_ver3(Zs,N),[1,2,3,4,5]), N = 3.
false.                                % no solution! 
                                      % we got one with revision #1!

Сюрприз! Два дела, которые работали до этого, теперь (несколько) нарушены, а детерминизм в основном случае не лучше... Почему?

• Ваниль if-then-else часто слишком быстро срезает, что особенно проблематично для кода, который использует сопроводительные и/или ограничения.

  Обратите внимание, что (*->)/2 (a.k.a. "soft-cut" или if/3), тарифы немного лучше, не так много!

• Поскольку if_/3 никогда не сокращает больше (чаще) ваниль if-then-else (->)/2, он не может использоваться в приведенном выше коде для улучшения детерминизма.

• Если вы хотите использовать if_/3 в сочетании с ограничениями, сделайте шаг назад и напишите код, который не является dcg как первый снимок.

• Если вы ленитесь, как я, подумайте об использовании meta-predicate, например tfilter/3 и (#>)/3.

Ответ 6

В этом ответе @Boris представлено логически чистое решение, в котором используется clpfd:zcompare/3, чтобы помочь улучшить детерминизм в определенных (наземных) случаях.

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

Давайте начнем с zcompare/3 и (#<)/3!

• zcompare/3 реализует трехстороннее сравнение конечных переменных домена и подтверждает трихотомию в один из <, =, или >.
• В качестве критерия включения, используемого OP, был арифметический тест менее чем, мы предлагаем использовать (#<)/3 для подтверждения дихотомии в один из true или false.

Рассмотрим ответы на следующие запросы:

?- zcompare(Ord,1,5), #<(1,5,B).
Ord = (<), B = true.    

?- zcompare(Ord,5,5), #<(5,5,B).
Ord = (=), B = false.   

?- zcompare(Ord,9,5), #<(9,5,B).
Ord = (>), B = false.    

Обратите внимание, что для всех элементов, которые должны быть выбраны как Ord = (<), так и B = true.

Здесь бок о бок сравнение трех не dcg на основе clpfd:

• Левая использует zcompare/3 и индексацию первого аргумента в трех случаях <, = и >.
• Средний использует (#<)/3 и индексирование первого аргумента в двух случаях true и false.
• Правильный использует (#<)/3 в сочетании с if_/3.

Обратите внимание, что нам не нужно определять вспомогательные предикаты в правом столбце!

less_than([],[],_).       % less_than([],[],_).          % less_than([],[],_).
less_than([Z|Zs],Ls,X) :- % less_than([Z|Zs],Ls,X) :-    % less_than([Z|Zs],Ls,X) :-
   zcompare(Ord,Z,X),     %    #<(Z,X,B),                %    if_(Z #< X,
   ord_lt_(Ord,Z,Ls,Rs),  %    incl_lt_(B,Z,Ls,Rs),      %        Ls = [Z|Rs],
   less_than(Zs,Rs,X).    %    less_than(Zs,Rs,X).       %        Ls = Rs),
                          %                              %    less_than(Zs,Rs,X).   
ord_lt_(<,Z,[Z|Ls],Ls).   % incl_lt_(true ,Z,[Z|Ls],Ls). %
ord_lt_(=,_,   Ls ,Ls).   % incl_lt_(false,_,   Ls ,Ls). %    
ord_lt_(>,_,   Ls ,Ls).   %                              % 

Затем, используйте dcg!

• В правой колонке мы используем if_//3 вместо if_/3.
• Обратите внимание на разные аргументы аргументов dcg и не dcg решения: less_than([1,2,3],Zs,3) vs phrase(less_than([1,2,3],3),Zs).

Следующие dcg соответствуют выше не dcg коды:

less_than([],_) --> [].   % less_than([],_) --> [].      % less_than([],_) --> [].  
less_than([Z|Zs],X) -->   % less_than([Z|Zs],X) -->      % less_than([Z|Zs],X) -->  
   { zcompare(Ord,Z,X) }, %    { #<(Z,X,B) },            %    if_(Z #< X,[Z],[]),
   ord_lt_(Ord,Z),        %    incl_lt_(B,Z),            %    less_than(Zs,X).     
   less_than(Zs,X).       %    less_than(Zs,X).          %
                          %                              %  
ord_lt_(<,Z) --> [Z].     % incl_lt_(true ,Z) --> [Z].   % 
ord_lt_(=,_) --> [].      % incl_lt_(false,_) --> [].    %
ord_lt_(>,_) --> [].      %                              % 

OK! Сохранение наилучшего для последнего... Просто используйте meta-predicate tfilter/3 вместе с (#>)/3!

less_than(Xs,Zs,P) :-
   tfilter(#>(P),Xs,Zs).