Назначение пролога

Question

Это вопрос для одного из моих заданий:

Запись repCount(L, X, N), которая имеет значение true, когда N - количество вхождений X в списке L.

Вот мой код, в котором я пытаюсь рекурсивно решить проблему:

repCount([], X, N) :-
   N is 0.
repCount([H|T], X, N) :-
   count([H|T], X, N).

count([], X, 0).
count([H|T], X, N) :-
   count(T, X, N1), 
   X =:= H,
   N is N1 + 1.

И это работает, когда я предоставляю список, полный одинаковых номеров, например:

?- repCount([2,2,2], 2, N).
N = 3.

Но если я предоставлю список хотя бы с одним другим значением:

?- repCount([2,2,22], 2, N).
false.

Возвращает false. Я не могу понять, почему это происходит или как изменить его, чтобы «пропустить» несоответствующее значение, а не объявить все это ложным. Любой вклад приветствуется.

Answer 1

count([H|T], X, N):- count(T, X, N1), X=:=H, N is N1 + 1.

здесь вы заявляете, что N должно быть N1 + 1, если X является H; однако вы не определяете, что должно произойти, если X не является H (в основном отсутствует предложение else) это должно работать:

count([H|T], X, N):- 
    count(T, X, N1), 
    (X=:=H->
       N is N1 + 1
       ; N is N1).

другой способ будет:

count([H|T], X, N):- count(T, X, N1), X=:=H, N is N1 + 1.

count([H|T], X, N):- X=\=H, count(T, X, N1), N is N1.

но это неэффективно, так как count (T, X, N1) будет вызван дважды, если X не H. Мы можем это исправить, выполнив проверку в начале предложения:

count([H|T], H, N):- count(T, X, N1), N is N1 + 1.

count([H|T], X, N):- count(T, X, N1), N is N1.

или просто: count ([H | T], H, N): - считать (T, X, N1), N равно N1 + 1.

count([H|T], X, N1):- X=\=H, count(T, X, N1).

Answer 2

Сохранение логическая чистота - с небольшой помощью мета-предикат tcount/3 и (=)/3!

Цель tcount(=(X),Es,N) гласит: «В списке Es есть N элементов, равных X».

Пример запроса:

?- <i>tcount(=(X), [a,b,c,a,b,c,a,b,a], N).</i>
(  N = 4,     X=a
;  N = 3,               X=b
;  N = 2,                         X=c
;  N = 0, dif(X,a), dif(X,b), dif(X,c)
).                                        % terminates universally

Answer 3

Еще одно интересное дополнение к тому, что написал @magus: Если вас интересует только количество элементов, а не сами элементы, вы можете использовать findall / 3 следующим образом:

list_elem_num(Ls, E, N) :-
    findall(., member(E, Ls), Ds),
    length(Ds, N).

Answer 4

Но при условии, что вам не разрешено «обманывать», если вы хотите использовать рекурсию, вам не нужно делать сравнение «==». Вы можете использовать объединение переменных Prolog для достижения того же конца:

% Job done all instances
repCount2([], _, 0).

% Head unifies with X/2nd parameter - ie X found
repCount2([H|T], H, N) :-
    repCount2(T, H, NewN),
    N is NewN + 1.

% We got here, so X not found, recurse around
repCount2([_|T], X, N) :-
    repCount2(T, X, N).

Во втором предикате H упоминается дважды, что означает, что если заголовок списка такой же, как X, затем выполнить возврат вниз, а затем добавить 1 к результату остальной части рекурсии (чтозаканчивается добавлением 0 - базовый вариант, как строится аккумулятор).

Answer 5

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

Если вам разрешено «обманывать», т.е.используйте предикаты более высокого порядка, такие как «findall», которые рекурсируют для вас. Если вы выполняете рекурсию самостоятельно, это можно сделать в одном предикате:

repCount(L, X, N) :-
    findall(X, member(X, L), ListOfX),
    length(ListOfX, N).

Answer 6

Почти там ... вам нужно использовать аккумулятор , таким образом:

repCount(Xs,Y,N) :-
  count(Xs,Y,0,N) % the 3rd argument is the accumulator for the count, which we seed as 0
  .

count([],_,N,N).       % if the list is empty, unify the accumulator with the result
count([X|Xs],Y,T,N) :- % if the list is non-empty,
  X == Y ,             %   and the head of the list (X) is the the desired value (Y),
  T1 is T+1 ,          %   then increment the count, and
  count(Xs,Y,T1,N)     %   recurse down, passing the incremented accumulator
  .                    %
count([X|Xs],Y,T,N) :- % if the list is non-empty,
  X \== Y ,            %   and the head of the list(X) is not the desired value (Y),
  count(Xs,Y,T,N)      %   simply recurse down
  .                    %