Prolog - 列表中的序列

Question

我们要构建一个谓词，它获取一个列表 L 和一个数字 N 并且如果 N 是最长的长度列表 L 的序列。 例如:

?- ls([1,2,2,4,4,4,2,3,2],3).
    true.

?- ls([1,2,3,2,3,2,1,7,8],3).
    false.

为此我 build 了-

head([X|S],X). % head of the list
ls([H|T],N) :- head(T,X),H=X, NN is N-1 , ls(T,NN) . % if the head equal to his following
ls(_,0) :- !. % get seq in length N
ls([H|T],N) :- head(T,X) , not(H=X) ,ls(T,N). % if the head doesn't equal to his following

这个概念很简单 - 检查头部是否等于他的后续，如果是，则继续尾部并递减 N。

我检查了我的代码，它运行良好(忽略 N = 1 的情况)-

 ls([1,2,2,4,4,4,2,3,2],3).
true ; 
false . 

但是 true 答案不是有限的，之后还有更多答案，我怎样才能让它返回有限答案呢？

Answer 1

Prolog-wise，你有一些问题。一个是您的谓词仅在两个参数都被实例化时才有效，这令 Prolog 感到失望。另一个是你的风格——head/2 并没有真正在 [H|T] 上添加任何东西。我也认为这个算法存在根本性的缺陷。我认为如果不保留猜测长度的未更改副本，您就无法确定列表尾部不存在更长长度的序列。换句话说，@Zakum 指出的第二件事，我不认为会有一个简单的解决方案。

这就是我处理问题的方式。首先是一个辅助谓词，用于获取两个值的最大值:

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- Y > X.

现在 sequence_length/2 所做的大部分工作都委托(delegate)给了一个循环，除了空列表的基本情况:

sequence_length([], 0).
sequence_length([X|Xs], Length) :- 
    once(sequence_length_loop(X, Xs, 1, Length)).

调用 once/1 确保我们只得到一个答案。这将阻止谓词有用地生成带有序列的列表，同时还使谓词具有确定性，这正是您想要的。 (它与放置得很好的切口具有相同的效果)。

循环的基本情况:将累加器复制到输出参数:

sequence_length_loop(_, [], Length, Length).

归纳案例 #1:我们有另一个相同值的副本。增加累加器并重复。

sequence_length_loop(X, [X|Xs], Acc, Length) :- 
    succ(Acc, Acc1), 
    sequence_length_loop(X, Xs, Acc1, Length).

归纳案例 #2:我们有不同的值。计算列表剩余部分的序列长度；如果它比我们的累加器大，就使用它；否则，使用累加器。

sequence_length_loop(X, [Y|Xs], Acc, Length) :- 
    X \= Y,
    sequence_length([Y|Xs], LengthRemaining),
    max(Acc, LengthRemaining, Length).

这就是我解决这个问题的方式。我不知道它是否对你有用，但我希望你能从中有所收获。