计算列表中的元素而忽略相邻重复项 [英] Counting elements in list ignoring adjacent duplicates
问题描述
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)).
我的方法显然是具有平凡的基本情况，然后以初始N为0的方式调用新的谓词countDistinct.然后，仅当相邻元素不同时，N才递增.
My approach was to obviously have the trivial base case, and then call a new predicate countDistinct with the initial N as being 0. Then, N is incremented only if the adjacent elements are distinct.
我这样称呼countDistinct的想法错了吗?我应该如何适应它.
Is my idea of calling countDistinct like this wrong? How should I adapt it.
推荐答案
由于您尝试使用递归解决此问题，因此此答案将采用该方法.同样，此答案将仅涵盖列表绑定和计数未绑定的模式，并且不会使用剪切来删除选择点.你可以如果需要，可以增强代码.
Since you are trying to solve this with recursion this answer will take that approach. Also this answer will only cover the mode of a list being bound and count being unbound and will not use cuts to remove choice points. You can enhance the code if desired.
在为列表创建递归谓词时，我通常从以下模板开始:
When creating recursive predicates for list I typically start with a template like:
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 是结果.
The list is deconstructed using [H|T] where H is for head of list and T is for tail of list. R is for result.
使用以下方法处理主条目
The head item is processed using:
process_item(H,R)
，列表的尾部使用:
process_list(T,R)
由于这需要处理列表中的两个相邻项，因此需要进行修改:
Since this requires processing two adjacent items in the list modifications are needed:
process_list([H1,H2|T],R) :-
process_item(H1,H2,R),
process_list([H2|T],R).
process_list([],0).
process_list([_],1).
NB现在有 2 个基本案例，而不是一个.仅仅因为递归谓词通常是一个递归子句和一个基本案例子句，并不意味着它们始终是一个递归子句和一个基本案例子句.
NB There are now two base cases instead of one. Just because recursive predicates are typically one recursion clause and one base case clause does not mean they are always one recursive clause and one base case clause.
接下来更新 process_item
process_item(I1,I1,N,N).
process_item(I1,I2,N0,N) :-
I1 \== I2,
N is N0 + 1.
由于 is/2 用于递增计数，因此需要传入，更新和传出计数状态，因此变量 N0 和 N .
Since is/2 is used to increment the count, a count state needs to be passed in, updated and passed out, thus the variables, N0 and N.
使用状态变量或线程变量时，命名约定是在输入值后附加 0 ，在输出值后不附加数字，并在与线程相同的子句中增加附加的数字进展.
When using state variable or threaded variables, the naming convention is to append 0 to the input value, have no number appended to the output value and increment the appended number in the same clause as the threading progresses.
当项目相同时，不增加计数，方法是:
When the items are the same the count is not incremented which is done using:
process_item(I1,I1,N,N).
当项目不同时，使用以下方法递增计数:
When the items are different the count is incremented which is done using:
process_item(I1,I2,N0,N) :-
I1 \== I2,
N is N0 + 1.
在更改 process_item 的过程中， R 变为 N0 和 N ，因此这需要更改为 process_list
In the process of changing process_item, R became N0 and N so this requires a change to process_list
process_list([H1,H2|T],N0,N) :-
process_item(H1,H2,N0,N1),
process_list([H2|T],N1,N).
并为此使用辅助谓词，以便原始谓词的签名可以保持不变.
and to use this a helper predicate is added so that the signature of the original predicate can stay the same.
count(L,N) :-
process_list(L,0,N).
完整代码
The full code
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.
测试用例
Test cases
:- 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).
示例运行
Example run
?- run_tests.
% PL-Unit: count ........ done
% All 8 tests passed
true.
使用DCG的解决方案
Solution using 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
In your example code is the use of the ;/2
使用;/2 删除代码时的典型约定是这样格式化
A typical convention when forammting code with ;/2 is to format as such
(
;
)
，以便使; 脱颖而出.
您的代码重新格式化
countDistinct([H,H1|T], N) :-
(
(
H == H1,
countDistinct([H1|T], N)
)
;
(
H =\= H1,
N1 is N+1,
countDistinct([H1|T], N1)
)
).
这篇关于计算列表中的元素而忽略相邻重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
