recursion - prolog 中列表的解压

Question

我需要解压缩序言中的列表，如下例所示:

decode([[a,1],[b,2],[c,1],[d,3]],L). 
L = [a, b, b, c, d, d, d] ; 

我编写了这段代码:

divide(L,X,Y):-length(X,1),append(X,Y,L).

divide2(L,X,Y):-divide(L,[X|_],[Y|_]).


makelist(_,N,[]):- N =< 0 .
makelist(X,Y,[X|Result]):-Y1 is Y-1,makelist(X,Y1,Result).

makelist2(L,L2):-divide2(L,X,Y),makelist(X,Y,L2).

decode([],[]).
decode([H|T],L):-makelist2(H,H2),append(H2,L,L2),decode(T,L2).

当我打电话时

makelist2([a,3],L2).
L2 = [a,a,a].

但是当我打电话时

解码([[a,3],[b,1],[c,4]],L)

连续运行。我做错了什么？

Answer 1

主题的另一个变体，使用 Boris' repeat/3 的稍微修改版本。谓词:

% True when L is a list with N repeats of X
repeat([X, N], L) :-
    length(L, N),
    maplist(=(X), L).

decode(Encoded, Decoded) :-
    maplist(repeat, Encoded, Expanded),
    flatten(Expanded, Decoded).

如果Encode = [[a,1],[b,2],[c,1],[d,3]] ，那么上面的 decode/2 ，maplist/3调用将产生 Expanded = [[a],[b,b],[c],[d,d,d]] ，然后 flatten/2调用结果为Decoded = [a,b,b,c,d,d,d] .

在 SWI Prolog 中，而不是 flatten/2 ，您可以使用append/2因为你只需要一个级别的“扁平化”。

<小时/> 编辑:使用一点 CLPFD 添加“双向”版本:

rle([], []).
rle([X], [[1,X]]).
rle([X,Y|T], [[1,X]|R]) :-
    X \== Y,     % use dif(X, Y) here, if available
    rle([Y|T], R).
rle([X,X|T], [[N,X]|R]) :-
    N #= N1 + 1,
    rle([X|T], [[N1,X]|R]).

这将产生:

| ?- rle([a,a,a,b,b], L).

L = [[3,a],[2,b]] ? ;

(1 ms) no
| ?- rle(L, [[3,a],[2,b]]).

L = [a,a,a,b,b] ? ;

no
| ?- rle([a,a,a,Y,Y,Z], [X, [N,b],[M,c]]).

M = 1
N = 2
X = [3,a]
Y = b
Z = c ? a

no
| ?- rle([A,B,C], D).

D = [[1,A],[1,B],[1,C]] ? ;

C = B
D = [[1,A],[2,B]] ? ;

B = A
D = [[2,A],[1,C]] ? ;

B = A
C = A
D = [[3,A]] ? ;

(2 ms) no
| ?- rle(A, [B,C]).

A = [D,E]
B = [1,D]
C = [1,E] ? ;

A = [D,E,E]
B = [1,D]
C = [2,E] ? ;

A = [D,E,E,E]
B = [1,D]
C = [3,E] ? ;
...

| ?- rle(A, B).

A = []
B = [] ? ;

A = [C]
B = [[1,C]] ? ;

A = [C,D]
B = [[1,C],[1,D]] ? ;
...

正如 @mat 在他的评论中建议的那样，在具有 dif/2 的 Prolog 实现中，然后dif(X,Y)优于X \== Y如上所述。