Prolog List Plateau

Question

刚刚介绍了prolog,尝试通过一些简单的练习,但我一直在坚持这个.我正在尝试编写一个输出输入列表的所有子列表的程序,其中每个子列表的长度> 1,并且不能扩展到更大的子列表.它还将输出子列表列表中的起始位置.所以样本输出就是

| ?- plateau([a,a,b,2,2,2,a+1,a+1,s(1,2)], I, Len).
    I = 1,
    Len = 2 ? ;
    I = 4,
    Len = 3 ? ;
    I = 7,
    Len = 2 ? ;
    no

我仍然对整个声明性事物感到困惑,并且在切换到命令式模式时遇到了很多麻烦.我想我希望我的程序可以做类似的事情

program([H|T],I,L):-
    T = [H1|T1] %split the tail
    ([H] = [H1] -> Count is Count+1, program(T,I,Count) 
     %if First element = second element, recurse with new values
    ; length(T,Spot), 
      %get the spot where you are in the list, so we know where sublist starts
      program(T,Spot,L) %run again, from tail, since sublist didn't have another  element?
program([],I,L). %terminate when entire list has been run through?

所以这不起作用,从我能说出来有几个原因.我没有重置'count',所以它总共可以将所有子列表的值合计在一起？有办法解决这个问题吗？我的基本情况可能也不是我想要的 - 我只是不确定它应该是什么？我可能也错过了其他的东西...非常感谢任何帮助!:) 谢谢!

Answer 1

您的程序将许多不同的问题合并为一个谓词.我们试着把它们分开一点.此外,我假设您正在搜索包含相同元素的两个或更多元素的最大子列表.

让我们从你想要的近似开始:识别子列表.不要担心这太宽泛,我们稍后会对其进行改进.我会将DCG用于此目的.非终端seq//1描述任意序列.

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

这是一个非常有用的非终端!

?- phrase((seq(Prefix),seq(Sublist),seq(Postfix)),
      [a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Prefix = Sublist, Sublist = [],
Postfix = [a,a,b,2,2,2,a+1,a+1,s(1,2)] ;
Prefix = [],
Sublist = "a",
Postfix = [a,b,2,2,2,a+1,a+1,s(1,2)] ...

两个答案都不是预期的,我们只想要长度为2或更长的子列表,所以我们必须稍微限制一下这个定义.说,要求Sublist至少应包含两个元素.那是Sublist = [_,_|_].

?- Sublist = [_,_|_],
   phrase((seq(Prefix),seq(Sublist),seq(Postfix)),
      [a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Sublist = "aa",
Prefix = [],
Postfix = [b,2,2,2,a+1,a+1,s(1,2)] ;
Sublist = "aab",
Prefix = [],
Postfix = [2,2,2,a+1,a+1,s(1,2)] ...

第一个答案显示了我们正在搜索的子列表.但第二个仍然是错误的:子列表的所有元素应该相等.最简单的方法是使用maplist/2:

?- maplist(=(_),Es).
Es = [] ;
Es = [_G221] ;
Es = [_G221,_G221] ;
Es = [_G221,_G221,_G221] 

有几个地方我们可以说明这个要求.我会把它放在尽可能早的地方:

?- Sublist = [_,_|_],
        phrase(( seq(Prefix),
                 seq(Sublist),{maplist(=(_),Sublist)},
                 seq(Postfix)),
           [a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Sublist = "aa",
Prefix = [],
Postfix = [b,2,2,2,a+1,a+1,s(1,2)] ;
Sublist = [2,2],
Prefix = "aab",
Postfix = [2,a+1,a+1,s(1,2)] ;
Sublist = [2,2,2],
Prefix = "aab",
Postfix = [a+1,a+1,s(1,2)] ;
Sublist = [2,2],
Prefix = [a,a,b,2],
Postfix = [a+1,a+1,s(1,2)] ;
Sublist = [a+1,a+1],
Prefix = [a,a,b,2,2,2],
Postfix = [s(1,2)] ;
false.

所以现在,所有子列表都包含相同的元素.唉,我们得到两个[2,2]和[2,2,2]作为子列表.我们只想要最大子列表.那么我们如何描述最大子列表是什么？

一种方法是查看我们的子列表:我们的子列表中必须没有相同的元素.因此,要么前面没有(epsilon),要么以与我们不同的元素结束的序列.

difel(_E,[]).
difel(E, Es) :- dif(E,F), phrase((seq(_), [F]), Es).

?- Sublist = [_,_|_],
   phrase(( seq(Prefix),{difel(E,Prefix)},
            seq(Sublist),{maplist(=(E),Sublist)},
            seq(Postfix)),
      [a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Sublist = "aa",
Prefix = [],
E = a,
Postfix = [b,2,2,2,a+1,a+1,s(1,2)] ;
Sublist = [2,2],
Prefix = "aab",
E = 2,
Postfix = [2,a+1,a+1,s(1,2)] ;
Sublist = [2,2,2],
Prefix = "aab",
E = 2,
Postfix = [a+1,a+1,s(1,2)] ;
Sublist = [a+1,a+1],
Prefix = [a,a,b,2,2,2],
E = a+1,
Postfix = [s(1,2)] ;
false.

一个不正确的答案少.最后还有一个潜伏着.

?- Sublist = [_,_|_],
   phrase(( seq(Prefix),{difel(E,Prefix)},
            seq(Sublist),{maplist(=(E),Sublist)},
            ( [] | [F],{dif(E,F)},seq(_) ) ),
      [a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Sublist = "aa",
Prefix = [],
E = a,
F = b ;
Sublist = [2,2,2],
Prefix = "aab",
E = 2,
F = a+1 ;
Sublist = [a+1,a+1],
Prefix = [a,a,b,2,2,2],
E = a+1,
F = s(1,2) ;
false.

这不完全是你想要的:你只是想要长度.为此,添加length([_|Prefix],I), length(Sublist,Len).

所以这是最终的定义:

plateau(Xs, I, Len) :-
   Sublist = [_,_|_],
   phrase(( seq(Prefix),{difel(E,Prefix)},
            seq(Sublist),{maplist(=(E),Sublist)},
            ( [] | [F],{dif(E,F)},seq(_) ) ),
      Xs),
   length([_|Prefix],I),
   length(Sublist,Len).