我有一个Prolog练习，要求我计算列表L2在L1中作为子列表出现的次数。
我需要做的是从用另一种语言(我们在大学里使用的某种说教性语言)编写的代码开始编写Prolog代码。
所以我写的算法是这种语言，一切都很顺利，但Prolog版本失败了，我不知道为什么。
这个想法很简单：
- 获取
L2的长度并将其称为SizeL2 - 从L1的头开始，得到每个大小为
SizeL2的子列表 - 检查是否为
subList(L1, SizeL2)==L2，如果为true则加1 - 当到达
L1的末尾时，我们返回count
这意味着类似于：
L1=[1，2，3，4，5，2，2，4，4]，L2=[2，3，4]，SizeL2=3，count=0
步骤1->[1，2，3]
步骤2->[2,3,4]-true，计数+1
步骤3->[3,4,5]
步骤4->[4,5,2]
步骤5->[5,2,3]
步骤6->[2,3,2]
步骤7->[3,2,3]
步骤8->[2,3,4]-true，计数+1
步骤9->L1完成，返回2
现在，我就是这样把它翻译成Prolog的。
请注意，我必须避免任何类型的系统谓词
%% we get the size of a list
size([], 0):-!.
size([H|T], R):- size(T,R1), R is R1+1.
%% we get the sublist of the given size
subList(_, 0, []):-!. %% if size is 0, we return an empty list
subList([], _, []):-!. %% if the list is empty, we're done
subList([H|T], Size, [H|Tr]):- Size1 is Size-1,
subList(T, Size1, Tr).
%% we count how many times L2 is sublist of L1
countSublist([], _, 0):-!. %% if L1 is empty we return 0
countSublist(L1, L2, 0):- size(L1, S1),
size(L2, S2),
S1 < S2. %% if L1 is shorter than L2, we return 0
countSublist([H|T], L2, R):- size(L2, SizeL2), %% we need L2's size
subList([H|T], SizeL2, SubL1), %% we get L1's sublist
countSublist(T, L2, R),
SubL1 = L2,
R1 is R+1. %% we do R+1 only if L2=Sublist of L1
我们语言的翻译非常直接，我相信我做得对，但我仍然不明白为什么Prolog版本不起作用。
我认为问题应该出现在最后一个谓词(countSublist([H|T], L2, R))中，因为size和subList运行良好。
知道吗？
我想每个人都有自己的简化版本。我的只是略有不同的尾部递归：
% headsub(S, L) is true if S is a sublist at the head of L
headsub([Hs|Ts], [Hs|Tl]) :-
headsub(Ts, Tl).
headsub([], _).
subcount(L, S, C) :-
subcount(L, S, 0, C).
subcount([Hl|Tl], S, A, C) :-
( headsub(S, [Hl|Tl])
-> A1 is A + 1 % if S is a sublist in front, count it
; A1 = A % otherwise, don't count it
),
subcount(Tl, S, A1, C). % Count the rest, adding it into the accumulator
subcount([], _, C, C). % We're done here. Accumulator becomes the answer.
在你最初的解决方案中，一个哲学问题是你处理问题的方法。你所拥有的更复杂的算法来自于像在传统编程语言中那样以程序的方式思考问题，而不是以声明的方式思考，这正是Prolog的设计目的。更简单的代码来自于将问题视为定义一个谓词，该谓词指示子列表何时位于列表的前面。然后定义一个谓词，递归地检查子列表是否在该列表的后续尾部的前面，并计算它为真的次数。
就原始解决方案中的特定错误而言，现在有两个问题，都有以下谓词：
countSublist([H|T], L2, R):- size(L2, SizeL2), %% we need L2's size
subList([H|T], SizeL2, SubL1), %% we get L1's sublist
countSublist(T, L2, R),
SubL1 = L2,
R1 is R+1. %% we do R+1 only if L2=Sublist of L1
在这里，您希望您的最终计数结果为R。但是，您使用R作为中间结果，然后使用R1作为最终结果。这些都是相反的。
其次，SubL1 = L2失败，则上述子句失败并回溯以重新评估countSublist(T, L2, R)。这可能不是您想要的，因为查询的成功应该计入您的结果中。因此，这种逻辑需要重新思考。快速修复显示了基本需求，但需要一点清理：
countSublist([H|T], L2, R):- size(L2, SizeL2), %% we need L2's size
subList([H|T], SizeL2, SubL1), %% we get L1's sublist
countSublist(T, L2, R1),
( SubL1 = L2
-> R is R1+1 %% we do R+1 only if L2=Sublist of L1
; R = R1
).
如果SubL1 = L2失败，这就有一个成功的分支，这根本不包括不匹配。所以现在你得到了正确的答案，但多次：
| ?- countSublist([1,2,3,4,5,2,3,2,3,4], [2,3,4], R).
R = 2 ? a
R = 2
R = 2
我把它留给读者整理一下
如果你能避免计算大小/2等，你的解决方案会更简单。
BTW注意，您在解决方案中不是避免系统谓词，因为is/2是一个"逻辑外"系统谓词，以及(<)/2。
如果必须避免这样的系统谓词，那么就必须使用Peano算术(例如，将-2表示为s(s(0)))，并用更简单的术语重写：
countSublist([], Sought, 0).
countSublist([H|List], Sought, s(C)) :-
isprefix(Sought, [H|List]),
% !, can you use cuts ?
countSublist(List, Sought, C).
countSublist([H|List], Sought, C) :-
% + isprefix(Sought, [H|List]), can you use not ?
countSublist(List, Sought, C).
% isprefix(Sought, List) is simple enough
顺便说一句，使用一些高级库要简单得多，比如聚合：
这是DCG版本的
countSublist(List, SubL, Count) :-
aggregate(count, R^phrase((..., SubL), List, R), Count).
... --> [] ; [_], ... .
这里是一个附加/3一个
countSublist(List, SubL, Count) :-
aggregate(count, U1^U2^U3^(append(U1,U2,List),append(SubL,U3,U2)), Count).
而且，我更喜欢使用append/2
countSublist(List, SubL, Count) :-
aggregate(count, L^R^append([L,SubL,R], List), Count).
这个答案是之前答案的后续，并试图以不同的方式改进它：
-
：-use_module(库(clpfd))。%对于声明性整数算术
-
我们通过使用累加器来最小化clpfd开销——比如
fd_length/2。 -
此外，我们以更一致的方式处理一些角落案例。
让我们开始吧！在prefix_of_t/3的基础上，我们定义：
list_contains_count(list，Sub，N)：-list_contains_count_acc(列表，子，N，0)。list_contains_count_acc(列表、Sub、N、N0)：-prefix_of_t(Sub，List，t)，t_ 01(t，N1#＝N0+T01，N1#=<Naux_list_contains_(列表，Sub，N，N1)。aux_list_contains_([]，_，N，N)。aux_list_contains_([_|Es]，Sub，N，N0)：-list_contains_count_acc(Es、Sub、N、N0)。t_01(真，1)。t_01(false，0)
一些示例查询：
?- list_contains_count([1,2,3,4,5,2,3,2,3,4], [2,3,4], N).
N = 2.
?- list_contains_count([2,2,2,2,2,2], [2,2,2], N).
N = 4.
?- list_contains_count([1,2,3,1,2,3], [1,2], N).
N = 2.
好的！和以前一样。。。一些角落的箱子怎么样？
？-长度(Sub，N)，list_contains_count([]，Sub，C)。N=0，C=1，Sub=[]；N=1，C=0，Sub=[A]；N=2，C=0，Sub=[A，_B]；N=3，C=0，Sub=[A，_B，_C]；N=4，C=0，Sub=[A，_B，_C，_D]。。。？-length(List，N)，List_contains_count(List，[]，C)。；N=0，C=1，List=[]；N=1，C=2，List=[A]；N=2，C=3，列表=[A，_B]；N=3，C=4，列表=[A，_B，_C]；N=4，C=5，列表=[A，_B，_C，_D]…
好吧…事实上，即使也比以前更好1！
?- ( Version = old, list_contains_countX([], [], C)
; Version = new, list_contains_count( [], [], C)
).
Version = old, C = 0
; Version = new, C = 1.
clpfd给我们带来了哪些开销？让我们来测量和比较一些运行时2,3！
？-set_prolog_flag(toplevel_print_anon，false)。是的。？-长度(_Xs，100_000)，映射列表(=(x)，在(0，6，_Exp)之间，L#=2^_ Exp，长度(_Sub，映射列表(=(x)，(版本=旧，call_time(list_contains_countX(_Xs，_Sub，_N)，T_ms)；版本=新，调用时间(list_contains_count(_Xs，_Sub，_N)，T_ms))。L=1，版本=旧，N=100000，T_ms=101；L=1，版本=新，N=100000，T_ms=1422/*1500%慢*/；L=2，版本=旧，N=99999，T_ms=153；L=2，版本=新，N=99999，T_ms=1479；L=4，版本=旧，N=99997，T_ms=240；L=4，版本=新，N=99997，T_ms=1572/*650%慢*/；L=8，版本=旧，N=99993，T_ms=417；L=8，版本=新，N=99993，T_ms=1760；L=16，版本=旧，N=99985，T_ms=778；L=16，版本=新，N=99985，T_ms=2212/*280%慢*/；L=32，版本=旧，N=99969，T_ms=1497；L=32，版本=新，N=99969，T_ms=2859；L=64，版本=旧，N=99937，T_ms=2948；L=64，版本=新，N=99937，T_ms=4330。/*速度慢150%*/
与非clpfd代码相比，上述clpfd码在最坏情况下的速度慢1500%。
所以。。。是否存在clpfd变体优于非clpfd对应变体的情况是的
？-长度(_Xs，100_000)，映射列表(=(x)，成员(Ub，[0,101001000100001000000])，_N#<Ub，(版本=旧，call_time(忽略(list_contains_countX(_Xs，[x]，_N))，T_ms)；版本=新，调用时间(忽略(list_contains_count(_Xs，[x]，_N))，T_ms))。Ub=0，Version=old，T_ms=100；Ub=0，版本=新，T_ms=0/*10000%更快*/；Ub=10，Version=old，T_ms=107；Ub=10，版本=新，T_ms=1/*5000%更快*/；Ub=100，版本=旧，T_ms=104；Ub=100，版本=新，T_ms=3/*3000%更快*/；Ub=1000，Version=old，T_ms=104；Ub=1000，版本=新，T_ms=17/*611%更快*/；Ub=10000，Version=old，T_ms=106；Ub=10000，版本=新，T_ms=130/*125%慢*/；Ub=100000，版本=旧，T_ms=102；Ub=100000，Version=new，T_ms=1238。/*速度慢1300%*/
底线？如果预先约束N，则新代码的速度会快很多！YMMV！
脚注1:prefix([], [])成功；CCD_ 27不太适合
脚注2:与早期的定义在这个答案中被称为list_contains_countX/3
脚注3:所有运行时测量均使用SWI Prolog 7.3.13(AMD64)进行
直接使用if_/3和prefix_of_t/3:
list_contains_count(Ls、Es、N)：-list_contains_acc_count(Ls，Es，0，N)。list_contains_acc_count([]，_，N，N)。list_contains_acc_count([X]，Sub，N0，N)：-如果_(prefix_of_t(Sub，[X|Xs])，N1是N0+1，N1＝N0)，list_contains_acc_count(X、Sub、N1、N)
示例查询：
？-list_contains_count([1,2,3,4,5,2,3,2,3,4]，[2,3,4]、N)。N＝2。？-list_contains_count([2,2,2,2,2]、[2,2,2]，N)。N＝4。？-list_contains_count([1，2，3，1，2，3]，[1，2]，N)。N=2.
来一点更一般的怎么样？
？-dif(N，0)，Sub=[_|_]，list_contains_count([1，2，3，1，2，3]，Sub，N)。N=2，Sub=[1]；N=2，Sub=[1，2]；N=2，Sub=[1，2，3]；N=1，Sub=[1,2,3,1]；N=1，Sub=[1,2,3,1,2]；N=1，Sub=[1,2,3,1,2,3]；N=2，Sub=[2]；N=2，Sub=[2,3]；N=1，Sub=[2,3,1]；N=1，Sub=[2,3,1,2]；N=1，Sub=[2,3,1,2,3]；N=2，Sub=[3]；N=1，Sub=[3,1]；N=1，Sub=[3,1,2]；N=1，Sub=[3,1,2,3]；false
为了简化解决方案，您不需要计算任何列表的大小，也不需要检查一个列表是否比另一个短。。一个子列表是主列表的成员，或者它不是。因此，唯一需要的计数器是子列表匹配的计数。
% H1 is the head of both lists. When done recursively, checks whole list.
isl(_, []).
isl([H1|T1], [H1|T2]) :-
isl(T1, T2).
% Base of recursion, finished first parameter
subby([], _, 0).
% ToFind is a sublist of first parameter
subby([H|T], ToFind, N) :-
isl([H|T], ToFind),
% recurse around, increment count
subby(T, ToFind, Inc),
N is Inc+1.
% ToFind is not sublist, decapitate and recurse
subby([_|T], ToFind, N) :-
subby(T, ToFind, N).
此解决方案不使用尾部递归，这对于较长的列表效率较低，但对于较小的列表则可以。也就是说，在第二个子谓词中，首先完成到尾部的递归，然后随着递归在返回的过程中出现气泡而添加计数。
它似乎不应该比更复杂
sublist_count(L,S,N) :-
sublist_count(L,S,0,N)
.
sublist_count([],_,N,N) :-
!.
sublist_count([X|Xs],S,T,N) :-
prefix_of([X|Xs],S) ,
T1 is T+1 ,
sublist_count(Xs,S,T1,N)
!.
prefix_of(_,[]) :-
!.
prefix_of([X|Xs],[X|Ys]) :-
prefix_of(Xs,Ys)
.
下面是我的尝试。这更像是一种基于谓词/关系方法的解决方案，而不是过程方法。
pe([],[]).
pe(X,X).
pe([_|T],X) :- pe(T,X).
sbls(_,[]).
sbls([H|T],[H|Y]) :- sbls(T,Y).
sblist(L,S) :- pe(L,X), sbls(X,S).
| ?- findall(_,sblist([1,2,3,1,2,3],[1,2]),L), length(L,Count).
Count = 2
| ?- findall(_,sblist([2,2,2,2,2,2],[2,2,2]),L), length(L,Count).
Count = 4