Подсчет элементов в списке без учета смежных дубликатов

Question

count([], 0).

count(L, N) :- countDistinct(L, 0).

countDistinct([H,H1|T], N) :-
                      (H == H1,
                      countDistinct([H1|T], N));

                      (H =\= H1, N1 is N+1,
                      countDistinct([H1|T], N1)).   

Мой подход состоял в том, чтобы, очевидно, иметь тривиальный базовый случай, а затем вызывать новый предикат countDistinct с начальным N равным 0. Тогда N увеличивается, только если смежные элементы различны.

Неужели моя идея назвать countDistinct неправильной?Как я должен адаптировать это.

Answer 1

Поскольку вы пытаетесь решить эту проблему с помощью рекурсии, этот ответ будет иметь такой подход.Также этот ответ будет охватывать только режим связывания списка и подсчета несвязанности и не будет использовать сокращения для удаления точек выбора.Вы можете улучшить код, если хотите.

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

process_list([H|T],R) :-
    process_item(H,R),
    process_list(T,R).
process_list([],R).

с рекурсивным регистром:

process_list([H|T],R) :-
    process_item(H,R),
    process_list(T,R).

и базовый случай:

process_list([],R).

Список деконструируется с использованием [H|T], где H для заголовка списка и T для хвоста списка.R для результата.

Элемент заголовка обрабатывается с использованием:

process_item(H,R)

, а хвост списка обрабатывается с использованием:

process_list(T,R)

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

process_list([H1,H2|T],R) :-
    process_item(H1,H2,R),
    process_list([H2|T],R).
process_list([],0).
process_list([_],1).

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

Следующее обновление process_item

process_item(I1,I1,N,N).
process_item(I1,I2,N0,N) :-
    I1 \== I2,
    N is N0 + 1.

Поскольку is/2 используется для увеличения счетчика, состояние счета должно быть передано, обновлено и передано, таким образом, переменные,N0 и N.

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

Когда элементы одинаковы, счет не увеличивается, что делается с помощью:

process_item(I1,I1,N,N).

Когда элементы отличаются, счет увеличивается, что делается с помощью:

process_item(I1,I2,N0,N) :-
    I1 \== I2,
    N is N0 + 1.

В процессе изменения process_item, R стало N0 и N, поэтому для этого требуется изменить на process_list

process_list([H1,H2|T],N0,N) :-
    process_item(H1,H2,N0,N1),
    process_list([H2|T],N1,N).

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

count(L,N) :-
    process_list(L,0,N).

---

Полный код

count(L,N) :-
    process_list(L,0,N).

process_list([H1,H2|T],N0,N) :-
    process_item(H1,H2,N0,N1),
    process_list([H2|T],N1,N).
process_list([],N,N).
process_list([_],N0,N) :-
    N is N0 + 1.

process_item(I1,I1,N,N).
process_item(I1,I2,N0,N) :-
    I1 \== I2,
    N is N0 + 1.

---

Контрольные примеры

:- begin_tests(count).

test(1,[nondet]) :-
    count([],N),
    assertion( N == 0 ).

test(2,[nondet]) :-
    count([a],N),
    assertion( N == 1 ).

test(3,[nondet]) :-
    count([a,a],N),
    assertion( N == 1 ).

test(4,[nondet]) :-
    count([a,b],N),
    assertion( N == 2 ).

test(5,[nondet]) :-
    count([b,a],N),
    assertion( N == 2 ).

test(6,[nondet]) :-
    count([a,a,b],N),
    assertion( N == 2 ).

test(7,[nondet]) :-
    count([a,b,a],N),
    assertion( N == 3 ).

test(8,[nondet]) :-
    count([b,a,a],N),
    assertion( N == 2 ).

:- end_tests(count).

---

Пример выполнения

?- run_tests.
% PL-Unit: count ........ done
% All 8 tests passed
true.

---

Решение с использованием DCG

% Uses DCG Semicontext 
lookahead(C),[C] -->
    [C].

% empty list
% No lookahead needed because last item in list.
count_dcg(N,N) --> [].

% single item in list
% No lookahead needed because only one in list.
count_dcg(N0,N) -->
    [_],
    \+ [_],
    { N is N0 + 1 }.

% Lookahead needed because two items in list and
% only want to remove first item.
count_dcg(N0,N) -->
    [C1],
    lookahead(C2),
    { C1 == C2 },
    count_dcg(N0,N).

% Lookahead needed because two items in list and
% only want to remove first item.
count_dcg(N0,N) -->
    [C1],
    lookahead(C2),
    {
        C1 \== C2,
        N1 is N0 + 1
    },
    count_dcg(N1,N).

count(L,N) :-
    DCG = count_dcg(0,N),
    phrase(DCG,L).

Пример выполнения:

?- run_tests.
% PL-Unit: count ........ done
% All 8 tests passed
true.

Лучше Решение с использованием DCG.

---

Примечание:

В вашем примере кода используется ;/2

Типичным условием для получения кода с ;/2 являетсяотформатировать

(
;
)

так, чтобы ; выделялся.

Ваш код переформатирован

countDistinct([H,H1|T], N) :-
  (
    (
      H == H1,
      countDistinct([H1|T], N)
    )
  ;
    (
      H =\= H1, 
      N1 is N+1,
      countDistinct([H1|T], N1)
    )
  ).