计算Prolog中列表中出现的次数

Question

我在Prolog中编写了这个小代码,用于计算列表中某些术语的出现次数.它工作,但它不是尾递归(所以没有递归优化).

我怎么能用尾递归编写相同的程序？

counter(T,[],X) :- 
   X is 0.
counter(T,[T|D],X1) :-
   !,
   counter(T,D,X),
   X1 is X+1.
counter(T,[_|D],X1) :-
   counter(T,D,X1).

我认为我应该使用累加器,但我不知道如何实现.有帮助吗？

Answer 1

程序可读性

即使在Prolog中也欢迎缩进,以使程序易于理解:

counter(T, [], X) :- 
    X is 0.
counter(T, [T|D], X1) :-
    !,
    counter(T, D, X),
    X1 is X+1.
counter(T, [_|D], X1) :-
    counter(T, D, X1).

变量命名

正确命名变量也是一种很好的做法,我们可以在这里使用:

counter(Elem, [], Result) :- 
    Result is 0.
counter(Elem, [Elem|Tail], Result) :-
    !,
    counter(Elem, Tail, NewResult),
    Result is NewResult + 1.
counter(Elem, [_|Tail], Result) :-
    counter(Elem, Tail, Result).

单例变量

为单例变量赋予一个特殊名称(在它们前面加上a _)也是一种很好的做法:

counter(_Elem, [], Result) :- 
    Result is 0.
counter(Elem, [Elem|Tail], Result) :-
    !,
    counter(Elem, Tail, NewResult),
    Result is NewResult + 1.
counter(Elem, [_Head|Tail], Result) :-
    counter(Elem, Tail, Result).

统一头脑

您可以利用Prolog在条款的头部使用统一来重写您的第一个条款:

counter(_Elem, [], Result) :- 
    Result is 0.

可以变成

counter(_Elem, [], 0).

那些仅由头部组成的条款也称为事实

尾递归

您必须更改的子句是middle子句:递归调用不在其中的谓词的末尾.可悲的是,它也将影响其他条款,让我们看看为什么.

为了得到尾递归,我们使用一个称为累加器的习语:一个在递归过程中保存中间结果的附加参数.例如这里:

counter(Elem, List, Result) :-
    counter(Elem, List, 0, Result).

counter(_Elem, [], Acc, Acc).
counter(Elem, [Elem|Tail], Acc, Result) :-
    !,
    NewAcc is Acc + 1,
    counter(Elem, Tail, NewAcc, Result).
counter(Elem, [_Head|Tail], Acc, Result) :-
    counter(Elem, Tail, Acc, Result).

正如您所看到的,我们现在有一个谓词counter/3,只有调用counter/4,而后者跟踪Acc变量中的中间结果.

获得更一般的计划

您的程序中存在的问题是您使用的问题is/2.这不会给你一个通用程序:你不能打电话counter(X, [1, 2, 3, 4], R)给我答案.要纠正您可以使用约束编程:

:- use_module(library(clpfd)).

counter(Elem, List, Result) :-
    counter(Elem, List, 0, Result).

counter(_Elem, [], Acc, Acc).
counter(Elem, [Elem|Tail], Acc, Result) :-
    NewAcc #= Acc + 1,
    counter(Elem, Tail, NewAcc, Result).
counter(Elem, [Head|Tail], Acc, Result) :-
    Elem #\= Head,
    counter(Elem, Tail, Acc, Result).

测试:

?- counter(X, [1, 2, 3, 4], R).
X = R, R = 1 ;
X = 2,
R = 1 ;
X = 3,
R = 1 ;
X = 4,
R = 1 ;
R = 0,
X in inf..0\/5..sup.