Аргументы недостаточно конкретизированы по отношению к 2 примерам

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

Правильный пример:

k_th_element(X,[X|_],1).
k_th_element(X,[_|L],K):- K>1,K1 is (K-1),k_th_element(X,L,K1).

Неправильный пример

length2(1,[_]).  
length2(X,[_|Ys]) :- X>1, X1 is (X-1), length(X1,Ys).

Почему пролог жалуется или нет для каждого случая?

Обновление: кажется, я понял. Чего я не мог понять, так это того, что неважно, что такое предикат, но как вы его называете. так что это правильно: k_th_element(X,[1,2,3,4,5],3), потому что у вас есть значение для K, которое является правильной переменной оператора «есть». Но при этом k_th_element(3,[1,2,3,4,5],Y) работать не будет, т.к. Y это переменная, наша "цель" и мы не можем иметь ее в правой части " есть" оператор. Поправьте меня если я ошибаюсь.


list prolog clpfd
person Cris Tsan    schedule 06.08.2015    source источник
comment
Чтобы сделать ваши отношения более общими и понятными, я рекомендую вам использовать ограничения CLP(FD) вместо примитивной целочисленной арифметики. Ограничения CLP(FD) работают во всех направлениях, и ваши примеры работают, если вы просто используете (вместо is/2 и >/2) ограничения конечной области (#=)/2 и #>/2. При использовании этих ограничений любые части обеих сторон могут содержать переменные, и вы можете использовать эти предикаты как истинные отношения.   -  person mat    schedule 06.08.2015
comment
@Cris: Попробуйте написать это с помощью CLP(FD), ответив на свой вопрос!   -  person false    schedule 06.08.2015
comment
это довольно круто @mat :) я обновлю его, как предложено false   -  person Cris Tsan    schedule 06.08.2015
comment
Очень хорошо! Я согласен с @false, что вы должны опубликовать это как ответ, а затем принять свой собственный ответ, чтобы мы могли проголосовать за него и принести пользу другим читателям. Скобки можно опустить: X1 #= X0 - 1. Пожалуйста, используйте :- use_module(library(clpfd)). для доступа к декларативной целочисленной арифметике в SICStus, SWI и YAP. (В GNU Prolog и B-Prolog он уже доступен с самого начала.)   -  person mat    schedule 06.08.2015
comment
Ты понял! Продолжайте в том же духе, и вы далеко пойдете!   -  person repeat    schedule 07.08.2015

Ответы (3)


arrow_upward
3
arrow_downward

как предложил мат, есть более гибкий способ добиться того же:

:- use_module(library(clpfd)).

length2(0,[]).  
length2(X,[_|Ys]) :- X#>0, X1#=X-1, length2(X1,Ys).
person Cris Tsan    schedule 06.08.2015
comment
Хотя декларативно все в порядке, у вас все еще есть возможность сделать его более эффективным (в дополнительном ответе). - person false; 06.08.2015
comment
@false, опуская первое условие (X#>0)? - person Cris Tsan; 06.08.2015
comment
Это было бы неограниченным для length2(0,Xs) - person false; 06.08.2015
comment
тогда вы можете помочь мне с этим :-). - person Cris Tsan; 06.08.2015

arrow_upward
3
arrow_downward

Во-первых, порядок аргументов. Для length/2 это скорее length(List, Length).

Для данного списка и неизвестной длины ваша версия относительно неэффективна из-за всех X1 #= X-1 ограничений, которые подразумевают N переменных с ограничениями. Версия length3/2 имеет одну ограниченную переменную. (Это примерно в 7 раз быстрее. Я все еще удивлен, что это не быстрее, чем есть, может быть, кто-то может помочь с другим ответом?)

:- use_module(library(clpfd)).

length2([], 0).
length2([_E|Es], N0) :-
   N0 #> 0,
   N1 #= N0-1,
   length2(Es, N1).

length3(Es, N) :-
   length3(Es, 0, N).

length3([], N,N).
length3([_E|Es], N0,N) :-
   N1 is N0+1,
   N #>= N1,
   length3(Es, N1,N).

/*

?- length(L,1000), time(length2(L,N)).
% 783,606 inferences, 0.336 CPU in 0.347 seconds (97% CPU, 2332281 Lips)
L = [_G23, _G26, _G29, _G32, _G35, _G38, _G41, _G44, _G47|...],
N = 1000.

?- length(L,1000), time(length3(L,N)).
% 127,006 inferences, 0.047 CPU in 0.058 seconds (81% CPU, 2719603 Lips)
L = [_G23, _G26, _G29, _G32, _G35, _G38, _G41, _G44, _G47|...],
N = 1000.

*/
person false    schedule 06.08.2015
comment
Жаль, что length3(L,0) оставляет точку выбора открытой - полностью проблема производительности. - person false; 06.08.2015

arrow_upward
1
arrow_downward

Используя предикаты отражения, можно построить следующий вариант list_length/2:

:- use_module(library(clpfd)).

list_length(Es, N) :-
   (  fd_sup(N, Ub), integer(Ub)
   -> (  length(Es, M),
         (  M >= Ub
         -> !,
            M == Ub
         ;  true
         ),
         M = N
      )
   ;  length(Es, N)
   ).

Приведенная выше реализация сочетает в себе два приятных свойства:

  • Он хорошо работает с clpfd.

    В частности, list_length(Xs,N) завершается универсально всякий раз, когда N имеет конечную верхнюю границу.

    Использование SWI-Prolog 8.0.0:

    ?- N in 1..3, list_length(Xs, N).
   N = 1, Xs = [_A]
;  N = 2, Xs = [_A,_B]
;  N = 3, Xs = [_A,_B,_C].    % terminates universally

  • Он минимизирует вспомогательные вычисления (и, следовательно, время выполнения) за счет использования встроенного предиката length/2.

    Давайте сравним время выполнения list_length/2 с length3/2, представленным в этом предыдущем ответе!

    Использование SWI-Prolog 8.0.0 с параметром командной строки -O:

    ?- time(( N in 1..100000, list_length(_,N), false ; true )).
% 2,700,130 inferences, 0.561 CPU in 0.561 seconds (100% CPU, 4812660 Lips)
true.

?- time(( N in 1..100000, length3(_,N), false ; true )).
% 14,700,041 inferences, 3.948 CPU in 3.949 seconds (100% CPU, 3723234 Lips)
true.

Обратите внимание, что приведенное выше также работает с SICStus Prolog: fd_sup/2 SWI называется fd_max/2 в SICStus.

person repeat    schedule 28.02.2019
comment
Ваше решение во многом зависит от хорошей согласованности. Что, если конечность N проявляется только после исключения первых элементов? Я слишком ленив для контрпримера - person false; 02.03.2019
comment
@ЛОЖЬ. Хорошая точка зрения! Кроме того, потенциальный выигрыш с SWI (> 5X) сокращается примерно на 10% быстрее с SICStus 4.5.0... - person repeat; 02.03.2019