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

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)
    )
  ).