Prolog：P-12：九十九个 Prolog 问题（已修改）

Question

我正在尝试解码包含两个不同元素的特定列表，例如[4, a] 或只是 b

我预计 decode([[4,a],b,[2,c],[2,a],d,[4,e]], X). 会导致 X=[a,a,a,a,b,c,c,a,a,d,e,e,e,e]。

与

decode([], []).
decode([[N, X]|Xs], R) :-
    create_list(N, X, L1),
    append(L1, R),
    decode(Xs, R).
decode([X|Xs], [X|R]) :-
    \+ is_list(X),
    decode(Xs, R).

create_list(0, _, []).
create_list(N, X, [X|R]) :-
    N > 0,
    N1 is N - 1,
    create_list(N1, X, R).

仅生成 false 我已经测试了 create_list 谓词并且它有效。

我不知道我错过了什么，但可能只是一个小错误。但是我已经尝试了一段时间没有成功找到问题所以为什么不在这里问:)问题是九十九序言问题（问题12）的修改版本。

Answer 1

您的问题在于使用 append/2 连接列表列表，但您有一个原子列表。

您可以使用 append/3 构建一个带有未绑定尾部的列表，并将该尾部传递给您的过程的递归步骤，即：

decode([], []).
decode([[N, X]|Xs], R) :-
    create_list(N, X, L1),
    append(L1, Tail, R),
    decode(Xs, Tail).
decode([X|Xs], [X|R]) :-
    \+ is_list(X),
    decode(Xs, R).

create_list(0, _, []).
create_list(N, X, [X|R]) :-
    N > 0,
    N1 is N - 1,
    create_list(N1, X, R).

样本运行：

?- decode([[4,a],b,[2,c],[2,a],d,[4,e]], X).
X = [a, a, a, a, b, c, c, a, a, d, e, e, e, e] ;
false.

您也可以通过向 create_list 添加第三个参数来完全摆脱 append ，它包含那个尾巴：

decode([], []).
decode([[N, X]|Xs], R) :-
    create_list(N, X, R, Tail),
    decode(Xs, Tail).
decode([X|Xs], [X|R]) :-
    \+ is_list(X),
    decode(Xs, R).

create_list(0, _, Tail, Tail).
create_list(N, X, [X|R], Tail) :-
    N > 0,
    N1 is N - 1,
    create_list(N1, X, R, Tail).

或者您可以使用 length/2 and maplist/2:

来摆脱 create_list

decode([], []).
decode([[N, X]|Xs], R) :-
    length(L, N),
    maplist(=(X), L),
    append(L, Tail, R),
    decode(Xs, Tail).
decode([X|Xs], [X|R]) :-
    \+ is_list(X),
    decode(Xs, R).

Answer 2

这是运行长度编码和运行长度解码的问题。

运行-长度编码很容易：

encode( []     , []     ) .  % the run-length encoding of the empty list is the empty list
encode( [X|Xs] , [R|Ys] ) :- % For non-empty lists, 
  run(Xs,X:1,R,Rs),          % - seed the run with the first element and compute the run length
  encode(Rs, Ys)             % - then recurse down
.                            % Easy!

run( []     , Y:N , Y:N , []     ) .
run( [X|Xs] , Y:N , Y:N , [X|Xs] ) :- X \== Y .
run( [X|Xs] , Y:T , N   , Rs     ) :- X  == Y , T1 is T+1 , run(Xs,Y:T1,N,Rs) .

解码一个运行长度的编码列表是相反的

decode( []       , [] ) .  % the run-length decoding of the empty list is the empty list
decode( [X:N|Xs] , Ys ) :- % for non-empty lists, 
  expand(X,N,Ys,Zs) ,      % - expand the run
  decode(Xs,Zs)            % - recurse down
  .

expand( _ , 0 ,    Zs  , Zs ) . 
expand( X , N , [X|Ys] , Zs ) :-
  N > 0,
  N1 is N-1,
  expand(X,N1,Ys,Zs)
  .

然后将其放在一个双向工作的转码器中：

run_length_transcode( PlainText, RleText ) :- nonvar( PlainText ) , encode( PlainText , RleText   ).
run_length_transcode( PlainText, RleText ) :- nonvar( RleText   ) , decode( RleText   , PlainText ).

Prolog：P-12：九十九个 Prolog 问题（已修改）

Prolog: P-12: Ninety-Nine Prolog Problems (Modified)

list

prolog