使用Prolog获取列表中偶数的最长子序列

Question

我想实现一个谓词 longest_even_sequence(X,Y)，其中 X 是给定列表，Y 是返回最长子序列的列表偶数。例如，对于给定列表 2,4,6,3,5,2,2 我想返回 2,4,6。

这是我尝试过的代码，但我不知道如何使其工作（我是 Prolog 的初学者）

longest_even_sequence([],[]).
longest_even_sequence([H|T],[R]):-
    H mod 2 =:= 0,
    longest_even_sequence(T,R1)
    R is [H|R1]                .
longest_even_sequence([H|T],[]):-
    H mod 2 =\= 0,
    longest_even_sequence(T,R2),
    R2 is [].

Answer 1

老实说，这是一个对初学者来说相当不友好的任务，因为它没有直接指出 prolog 的优点，并且使用递归方法存在多个问题。

第一次尝试：添加一个参数。以基本的递归方式执行此操作需要您添加一个参数来保持当前的连续记录，以便将其与当前的最佳记录进行比较。这需要引入一个新的谓词，并且似乎是使用递归的最简单的初学者友好解决方案。为了不给自己太大压力，我使用 if-then-else ( ... -> ... ; ...) 来处理最大值选择。基本思想是遍历列表并收集第二个参数中的连续数据。一旦我达到奇数，我就会得到列表其余部分的最大偶数子序列 (longest_even_sequence(T,[],Rtmp)) 并将其与当前的条纹进行比较 (LT > LR）。较大的列表将被复制到输出参数。一旦到达终点，我只需复制当前的连胜 (longest_even_sequence([],R,R).)。

这一问题的潜在问题是连胜的顺序相反，因此您需要将其反转。另外，使用 if-then-else 也不是初学者水平。以连胜开始并以连胜结束是没有问题的。

longest_even_sequence(In,Out) :-
    longest_even_sequence(In,[],ROut),
    reverse(ROut,Out).

longest_even_sequence([],R,R).
longest_even_sequence([H|T],Tmp,R):-
    H mod 2 =:= 0,
    longest_even_sequence(T,[H|Tmp],R).
longest_even_sequence([H|T],Tmp,R):-
    H mod 2 =\= 0,
    longest_even_sequence(T,[],Rtmp),
    length(Rtmp,LR),
    length(Tmp,LT),
    (
        LT > LR
    ->  R = Tmp
    ;   R = Rtmp
    ).

使用 SWISH 进行测试：

?- longest_even_sequence([2,4,6,2,3,4,5,4,4,4,5,6],R).
R = [2, 4, 6, 2]; 
false.
 

只是为了好玩（是的，我是认真的），让我们用另一种更复杂且计算密集的方式进行测试：

range(High, _, High).
range(Out,Low,High) :- 
    NewH is High-1, 
    NewH >= Low, 
    range(Out, Low, NewH).

alleven([]).
alleven([H|T]):-
    H mod 2 =:= 0,
    alleven(T).

les(In,Out):-
    length(In,Lin),
    range(N,0,Lin),
    length(Out,N),
    append(_,InRest,In),
    append(Out,_,InRest),
    alleven(Out), 
    !.

测试：

?- les([2,4,6,2,3,4,5,4,4,4,5,6],R).
R = [2, 4, 6, 2].

那么会发生什么？首先生成 0 和输入列表长度之间的数字（使用 range(N,0,Lin)，修改后的代码来自 此处）按降序排列。然后创建一个包含N（未知）元素的列表length(Out,N),。然后输入列表 In 被分成 3 部分，其中开始和结束并不有趣，但中间必须有 N 元素，这是通过将其统一为Out，这是一个包含 N 元素的列表。该列表必须全部为偶数。如果成功，则跳过所有其他答案（!，称为剪切，更高级的序言）。如果不成功，则测试下一个拟合子列表。如果没有适合长度 N 的列表，则测试下一个较低的 N，直到最终达到 N=0。

Answer 2

我现在已经对此进行了投票，但我想推荐使用foldl，但有一点不同：

is_even(Stop, ListElement, Ittr, Result) :-
    ((ListElement mod 2) =:= 0 , \+(\+(Stop=0)), \+(\+(Stop=1)) ->  
        append(Ittr, [ListElement], Result) ;
        Stop is 1, Result = Ittr
    ).

longest_even_sequence(List, Result) :-
    foldl(is_even(_), List, [], Result).

longest_even_sequence([2,4,6,1,5,3,2,1], Result)

Result = [2, 4, 6 ]