以紧凑形式实现列表的分配

Question

我对课程作业有疑问。

Consider repetitive lists of the form [a,a,a,b,b,c,a,a,a,a] and their compact form, defined as lists of couples, [[a,3],[b,2],[c,1],[a,4]].

Define the predicate compress/2 such that compress(+L1, ?L2) is satisfied if, given a list L1, L2 is its compact form.

到目前为止，我已经想出了下面的代码：

compress(X,[[X,1]]).
compress([H1,H2|T1],[[H1,C]|T2]):-
   H1 = H2,
   compress(T1,T2),
   C is R + 1.

我不确定我做的是否正确。谁能指点正确的方向。

Answer 1

这里有一些帮助您入门的想法。

您将需要保留运行个重复元素计数，因为您的结果有计数器。所以马上考虑一个包含计数器的辅助谓词，这是在 Prolog 中处理它的典型方式。这种计数器的使用通常称为 累加器。

compress(L, C) :-
    compress(L, 1, C).   % Start counter at 1

现在您需要考虑几种不同的情况：

compress([], _, []).                 % This is an easy one!

这是说如果我压缩一个空列表，我得到一个空列表。

compress([H], Count, [[H,Count]]).   % This is an easy one!

这个说如果我压缩一个元素的列表并且我当前的运行计数是 Count，那么结果是 [[H, Count]]。

compress([H, H|T], Count, TC) :-
    ...

在这种情况下，我有一个运行计数并且该元素仍在重复。结果将是一个列表 TC 但我还不知道它是什么样子，因为我们仍处于重复循环中，需要通过递归来确定。这个谓词应该是什么样的？在您的示例中，当前两个元素相同时，您在结果中包含了一个计数，这不是包含计数的正确时间（请参阅下面的子句）。

compress([H1, H2|T], Count, [[H1,Count]|TC]) :-
    dif(H1, H2),
    ...

在这种情况下，我有一个运行计数并且重复停止在 H1。由于当前循环的重复以 H1 结束，我们知道结果看起来像 [[H1, Count]|TC] 因为 H1 已经重复了 Count 次。我们还没有通过递归确定列表的其余部分TC。这个谓词实现应该是什么样的？

还有其他方法可以实现上述逻辑（例如，使用 -> 和 ; 构造等），但这将使事情变得简单。

尝试将这些视为规则，其中谓词子句的头部是断言，如果子句的以下元素为真，则该断言为真。并递归思考。

作为事后的想法，这可以在没有单独的累加器的情况下通过使用结果来携带累加器来完成：

compress([], []).
compress([H], [[H,1]]).
compress([H1,H2|T], [[H1,1]|R]) :-
    dif(H1, H2),
    compress(...).                 % left as an exercise
compress([H,H|T], [[H,N]|R]) :-
    N #= N1 + 1,
    compress(...).                 % left as an exercise

Answer 2

我选择这样做：

?- compress([a,a,a,b,b,c,a,a,a,a],L), write(L), nl, fail.

compress(X,R) :-
    enumerate(X,Y),
    collapse(Y,R).

enumerate([],[]).
enumerate([H|T],[[H,1]|R]) :- enumerate(T,R).

collapse([],[]).
collapse([X],[X]).
collapse([[X,N1],[X,N2]|T],R) :- N is N1 + N2, collapse([[X,N]|T],R).
collapse([[X,N1],[Y,N2]|T],[[X,N1]|R]) :- X \= Y, collapse([[Y,N2]|T],R).

enumerate 谓词简单地将 [a, a, a, b, b, c, a, a, a, a] 映射到 [[a, 1], [a, 1], [a, 1], [b, 1], [b, 1], [c, 1], [a, 1], [a, 1], [a, 1], [a, 1]]。

然后我 collapse 通过匹配列表的前两个头向下列表 - 如果它们统一添加值并再次尝试 collapse。如果它们不统一，则从列表中弹出一个元素并再次 collapse 。否则有两种基本情况 - 一个空列表和一个包含一个元素的列表。

结果是：[[a, 3], [b, 2], [c, 1], [a, 4]].

Answer 3

以下是使用 splitlistIfAdj/3 的方法结合 dif/3.

首先，确定相邻列表项的运行次数：

?- splitlistIfAdj(dif, [a,a,a,b,b,c,a,a,a,a], Xss).
Xss = [[a,a,a],[b,b],[c],[a,a,a,a]].

然后，使用 maplist/3 and length/2:

映射每个运行的长度

?- maplist(length, [[a,a,a],[b,b],[c],[a,a,a,a]], Ls).
Ls = [3,2,1,4].

快完成了！让我们使用 Prolog lambdas:

将它们放在一起

:- use_module(library(lambda)).

list_compressed(Xs, Yss) :-
   splitlistIfAdj(dif, Xs, Xss),
   maplist(\Es^(E-N)^(Es=[E|_],length(Es,N)), Xss, Yss).

示例查询：

?- list_compressed([a,a,a,b,b,c,a,a,a,a], Xss).
Xss = [a-3,b-2,c-1,a-4].

以紧凑形式实现列表的分配

Assignment that implements a list in compact form

list

prolog