run length encoding using DCGs

Question

problem from: https://web.archive.org/web/20200718175929/http://www.pathwayslms.com/swipltuts/dcg/

Use a dcg to convert a sparse sequence like

[0,0,0,0,0,0,7,4,3,0,0,0,0,0,0,0,8,9,14,0,0,0,0....]

to

[zero(6), 7,4,3, zero(7), 8,9,14, ...]

i feel like i understand the material on this page up to here but don't really know how to start this one. any pointers would be appreciated

Answer 1

Try doing something like this:

code([X|Xs]) --> item(X), code(Xs).
code([])     --> [].

item(X) --> [0], zeros(1, X).
item(X) --> [X], { X \= 0 }.

zeros(M, N)       --> [0], { M1 is M + 1 }, zeros(M1, N).
zeros(N, zero(N)) --> \+ [0].

Example:

?- phrase(code(C), [0,0,0,0,0,0,7,4,3,0,0,0,0,0,0,0,8,9,14,0,0,0,0]).
C = [zero(6), 7, 4, 3, zero(7), 8, 9, 14, zero(4)] ;
false.

Answer 2

Alternate style:

% For eos
:- use_module(library(dcg/basics)).

list_rle(Lst, LstRle) :-
    must_be(list, Lst),
    phrase(rle, Lst, LstRle),
    % The first is correct
    !.
    
% Check for list of zeros
rle, [zero(N)] --> [0], zeros(1, N), rle.
% Accept anything otherwise
rle, [C] --> [C], rle.
% Being greedy - check for end last
% eos means no more input - better than [] which can leave a remainder
rle --> eos.

zeros(N, Tot) --> [0], { N1 is N + 1 }, zeros(N1, Tot).
% Being greedy - check for end last
zeros(N, N) --> [].

Result in swi-prolog:

?- time(list_rle([0,0,0,0,0,0,7,4,3,0,0,0,0,0,0,0,8,9,14,0,0,0,0], L)).
% 39 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 545073 Lips)
L = [zero(6),7,4,3,zero(7),8,9,14,zero(4)].

Another minor variant which can also be used as a generator:

rle --> eos.
rle, [zero(N)] --> [0], zeros(1, N), rle.
rle, [C] --> [C], { dif(C, 0) }, rle.

zeros(N, Tot) --> [0], !, { N1 is N + 1 }, zeros(N1, Tot).
zeros(N, N) --> [].

Result:

?- length(L, _), list_rle(L, LR).
L = LR, LR = [] ;
L = [0],
LR = [zero(1)] ;
L = LR, LR = [_A],
dif(_A,0) ;
L = [0,0],
LR = [zero(2)] ;
L = [_A,0],
LR = [_A,zero(1)],
dif(_A,0) ;
L = LR, LR = [_A,_B],
dif(_A,0),
dif(_B,0) ;
L = [0,0,0],
LR = [zero(3)] ;
L = [_A,0,0],
LR = [_A,zero(2)],
dif(_A,0) ;