1

我需要做一个类似的练习： Prolog - 将列表分成两半，反转前半部分。

我被要求将一个字母列表放入两个大小相等的列表（我猜是偶数大小的原始列表）或一个比另一个大一个元素（奇数大小的列表），并在我时反转第一个m ，但仅使用差异列表。

这些是必需的查询和输出

?-dividelist2([a,b,c,d,e,f | T] - T, L1-[], L2-[]).
L1 = [c,b,a]
L2 = [d,e,f]

?-dividelist2([a,b,c,d,e | T] - T, L1-[], L2-[]).
L1 = [c,b,a]
L2 = [d,e]
% OR
L1 = [b,a]
L2 = [c,d,e]

这是我使用前面示例的代码，但经过修改，我不知道如何正确比较两个列表从输入中“扣除”它们并产生[d,e,f]？

dividelist2(In -[], L1-[], L2-[]) :-
     length_dl(In - [],L), % length of the list
     FL is L//2, % integer division, so half the length, Out1 will be 1 shorter than Out2 if L is odd
    ( \+ (FL*2 =:= L), % is odd
      FLP is FL + 1 % odd case
    ; FLP = FL % odd and even case
    ), 
    take(In,FLP,FirstHalf),
    conc([FirstHalf| L2]-l2,L2-[],In-[]),
    reverse1(FirstHalf-[], L1-[]). % do the reverse

reverse1(A- Z,L - L):-
  A == Z , !. 
reverse1([X|Xs] - Z,L - T):-
  reverse1(Xs - Z, L - [X|T]).

length_dl(L- L,0):-!.
length_dl([X|T] - L,N):-
    length_dl(T- L,N1),
    N is N1 + 1 .
take(Src,N,L) :- findall(E, (nth1(I,Src,E), I =< N), L).
conc(L1-T1,T1-T2,L1-T2).

这是当前的跟踪：

Call:dividelist2([a, b, c, d, e, f|_22100]-_22100, _22116-[], _22112-[])
 Call:length_dl([a, b, c, d, e, f]-[], _22514)
 Call:length_dl([b, c, d, e, f]-[], _22520)
 Call:length_dl([c, d, e, f]-[], _22526)
 Call:length_dl([d, e, f]-[], _22532)
 Call:length_dl([e, f]-[], _22538)
 Call:length_dl([f]-[], _22544)
 Call:length_dl([]-[], _22550)
 Exit:length_dl([]-[], 0)
 Call:_22554 is 0+1
 Exit:1 is 0+1
 Exit:length_dl([f]-[], 1)
 Call:_22560 is 1+1
 Exit:2 is 1+1
 Exit:length_dl([e, f]-[], 2)
 Call:_22566 is 2+1
 Exit:3 is 2+1
 Exit:length_dl([d, e, f]-[], 3)
 Call:_22572 is 3+1
 Exit:4 is 3+1
 Exit:length_dl([c, d, e, f]-[], 4)
 Call:_22578 is 4+1
 Exit:5 is 4+1
 Exit:length_dl([b, c, d, e, f]-[], 5)
 Call:_22584 is 5+1
 Exit:6 is 5+1
 Exit:length_dl([a, b, c, d, e, f]-[], 6)
 Call:_22590 is 6//2
 Exit:3 is 6//2
 Call:3*2=:=6
 Exit:3*2=:=6
 Call:_22590=3
 Exit:3=3
 Call:take([a, b, c, d, e, f], 3, _22594)
 Call:'$bags' : findall(_22518, (nth1(_22514, [a, b, c, d, e, f], _22518),_22514=<3), _22614)
 Exit:'$bags' : findall(_22518, '251db9a2-f596-4daa-adae-38a38a13842c' : (nth1(_22514, [a, b, c, d, e, f], _22518),_22514=<3), [a, b, c])
 Exit:take([a, b, c, d, e, f], 3, [a, b, c])
 Call:conc([[a, b, c]|_22112]-l2, _22112-[], [a, b, c, d, e, f]-[])
 Fail:conc([[a, b, c]|_22112]-l2, _22112-[], [a, b, c, d, e, f]-[])
 Fail:dividelist2([a, b, c, d, e, f|_22100]-_22100, _22116-[], _22112-[])
false

谢谢

4

2 回答 2

1

这不是答案，而是不符合评论长度限制的测试和调试建议。建议使用 Logtalk，您可以在大多数 Prolog 系统上运行它。

根据您的问题，dividelist2/3谓词需要满足几个properties，其中一个描述结果列表的长度。我们可以使用谓词轻松表达此属性p/1：

p(DL) :-
    difflist::length(DL, N),
    dividelist2(DL, DL1, DL2),
    difflist::length(DL1, N1),
    difflist::length(DL2, N2),
    N is N1 + N2,
    abs(N1 - N2) =< 1.

这里我使用 Logtalk 的difflist库对象来计算差异列表的长度。有了这个谓词，我们现在可以对您的谓词进行一些属性测试。dividelist2/3

使用 Logtalklgtunit工具实现属性测试，我们得到：

?- lgtunit::quick_check(p(+difference_list(integer))).
*     quick check test failure (at test 1 after 0 shrinks):
*       p(A-A)
false.

即，您的代码因空差异列表的琐碎情况而失败。在查询中，我们使用difference_list(integer)类型只是为了简化生成的反例。

让我们尝试通过在代码中添加以下子句来修复失败：

dividelist2(A-A, B-B, C-C).

重新尝试我们的测试查询，我们现在得到：

?- lgtunit::quick_check(p(+difference_list(integer))).
*     quick check test failure (at test 2 after 0 shrinks):
*       p([0|A]-A)
false.

即，dividelist2/3对于具有单个元素的差异列表，谓词失败。您现在可以使用生成的反例中的差异列表作为调试的起点：

?- dividelist2([0|A]-A, L1, L2).
A = [0|A],
L1 = _2540-_2540,
L2 = _2546-_2546 ;
false.

您还可以对辅助谓词使用属性测试。取length_dl/2谓语。我们可以通过定义另一个属性将它与计算差异列表长度的谓词的另一种实现进行比较，例如 Logtalk 库中的那个：

q(DL) :-
    difflist::length(DL, N),
    length_dl(DL, N).

测试它我们得到：

?- lgtunit::quick_check(q(+difference_list(integer))).
*     quick check test failure (at test 3 after 0 shrinks):
*       q([-113,446,892|A]-A)
false.

实际上，使用 counter.example，我们得到：

?- length_dl([-113,446,892|A]-A, N).
A = [-113, 446, 892|A],
N = 0.

希望这种见解有助于修复您的代码。

于 2019-08-21T09:29:23.077 回答
0

好的，我的想法可行，但似乎有些不雅。我们将从一个方便的实用程序开始，它将列表转换为差异列表：

list_dl([], W-W).
list_dl([H|T1], [H|T2]-W) :-
    list_dl(T1, T2-W).

现在我们想要一个谓词从差异列表中获取第一个和最后一个元素。只剩下一个元素的情况需要以不同的方式处理，因此我们将使其唯一。

head_last(Head, Head, DL-Hole, one) :-
    once(append([Head|_], [Last, Hole], DL)),
    var(Last), !.
head_last(Head, Last, DL-Hole, New) :-
    once(append([Head|Mid], [Last, Hole], DL)),
    list_dl(Mid, New).

现在我们可以创建递归拆分和反向谓词，它有 3 个基本情况：

splitrev(W-W, [], []) :- var(W), !. % Empty base case.
splitrev(DL, [V|[]], []) :- head_last(V, V, DL, one).
splitrev(DL, [], [V|[]]) :- head_last(V, V, DL, one).
splitrev(DL, [Head|Front], [Last|Back]) :-
    head_last(Head, Last, DL, Rest),
    splitrev(Rest, Front, Back).

不幸的是，将一个元素添加到差异列表的后面比从后面获取一个元素要容易得多，而且让该元素填补了列表中的漏洞。因此，我认为不同的策略会更好。

于 2019-08-20T12:40:55.483 回答