检查第二个列表是否是第一个列表大小的一半

Question

我是一个 noob prolog 程序员，在我学习的书中给出的一个基本问题上遇到了困难。问题。这个问题基本上要求我们写下一个 Prolog 过程，该过程将两个列表作为参数，如果第一个列表的大小是第二个列表的两倍并且两个列表以相同的元素开头，则该过程成功。如果两个列表为空，该过程应该 return false。

例如，如果我们通过查询，它应该 return 为真：

a2b([a,a,a,a],[a,b]).

并且会因以下查询而失败：

a2b([a,a],[a,b,b,b]).

我不知道如何递归地解决这个问题，任何帮助将不胜感激。谢谢！

Answer 1

可爱的问题。可以使用以下代码解决：

% fail of the first element of each list don't unify
% or if one or both lists are empty
a2b([First| List1], [First| List2]) :-
    % calculate the length of the second list
    % while traversing both lists in parallel
    a2b_first(List2, 1, N, List1, Rest1),
    % check that the length of the rest of the first
    % list is equal to the length of the second list
    a2b_second(Rest1, N).

a2b_first([], N, N, Tail1, Tail1).
a2b_first([_| Tail2], N0, N, [_| Tail1], Rest1) :-
    N1 is N0 + 1,
    a2b_first(Tail2, N1, N, Tail1, Rest1).

a2b_second([], 0).
a2b_second([_| Tail1], N) :-
    M is N - 1,
    a2b_second(Tail1, M).

当然，还有一个更简单（但编码起来没那么有趣！）的解决方案：

% fail of the first element of each list don't unify
% or if one or both lists are empty
a2b([First| List1], [First| List2]) :-
    length([First| List1], N1),
    length([First| List2], N2),
    N1 is 2 * N2.

length/2 谓词通常可以作为内置谓词或库谓词使用。

对于学习Prolog，研究第一个解很有趣。例如，它举例说明了如何利用第一个参数索引以及如何使用累加器编写尾递归谓词（因此 space 有效）。

另外，第一种解决方案比第二种解决方案更有效。在第二种解决方案中，我们总是遍历两个列表，直到找到它们的长度。但是，在第一个解决方案中，这并不总是必要的。

Answer 2

首先，关于长度的要求：

/* empty list fulfills request */   
a2b_length([],[]). 
/* non-empty: discard two elements of first list, 
                one of second list, and verify
                remainder */
a2b_length([_,_|Q1],[_|Q2]) :- 
   a2b_length(Q1,Q2).

现在，我们可以添加需求"starts by the same term and are non empty"，并写下最后一个子句：

a2b([X,_|Q1],[X|Q2]) :-
   a2b_length(Q1,Q2).

Answer 3

不要想太多：只需描述解决方案，然后让 Prolog 解决。

解决方案不需要计数或谓词，除了它的微不足道的自我。都是模式匹配。我们有一个特殊的（终止情况），断言长度为 2 的列表的长度是长度为 1 的列表的两倍（这应该很明显）：

is_twice_as_long_as( [_,_] , [_] ) .

然后是一般情况，它断言给定两个任意长度的列表，左边的长度是右边的两倍如果我们可以 (A) 从左边删除 2 个项目，(B) 删除 1 个项目从右开始，递归地断言它们各自的余数同样是两倍长：

is_twice_as_long_as( [_,_|A] , [_|B] ) :- is_twice_as_long_as( A , B ) .

给我们成品：

is_twice_as_long_as( [_,_]   , [_]   ) .
is_twice_as_long_as( [_,_|A] , [_|B] ) :- is_twice_as_long_as( A , B ) .

简单！

编辑以注意要求两个列表以相同元素开头：

取决于如何解释...

这要求列表在每次迭代中都有一个共同的头部：

is_twice_as_long_as( [A,_]   , [A]   ) .
is_twice_as_long_as( [A,_|L] , [A|R] ) :- is_twice_as_long_as( L , R ) .

这只检查一次普通头::

is_twice_as_long_as( [A|As] , [A|Bs] ) :-
  is_2x([A|As],[A|Bs]) .

is_2x( [_,_]   , [_] ) .
is_2x( [_,_|L] , [_|R] ) :- is_2x( L , R ) .

检查第二个列表是否是第一个列表大小的一半

Checking if the second list is half the size of first list

prolog