How to replace a sequence of tokens in a DCG grammar in Prolog?

Question

I would like to replace a sequence of tokens in a DCG grammar in Prolog. In other words replace the sequence or sublist A: [a,a,a,a] by the sublist B: [b].
chain --> chain_where_sublist_A_is_replaced_by_sublist_B but entirely using the DCG formalism.

For example: [c,a,a,a,a,d] gives [c,b,d]

Answer 1

As at Prolog - substitute substring of string by letter not used in string itself

replace(Find, Replace), Replace --> Find, !, replace(Find, Replace).
% Otherwise accept char-by-char
replace(Find, Replace), [C] --> [C], !, replace(Find, Replace).
% Accept success when reached end
replace(_Find, _Replace) --> [].

substitute(Find, Replace, Request, Result):-
    phrase(replace(Find, Replace), Request, Result).

In swi-prolog:

?- substitute([a,a,a,a], [b], [c,a,a,a,a,d], S).
S = [c,b,d].

Answer 2

First solution:

eos_([], []).

transform --> call(eos_).
transform, [b] --> [a,a,a], transform.
transform, [c] --> [c], transform.
transform, [d] --> [d], transform.

Then the query:

?- phrase(transform, "caaad", Cs).
   Cs = "cbd"

Second solution:

step(b) --> [a,a,a].
step(C) --> [C].

transform([]) --> [].
transform([C|Cs]) --> step(C), transform(Cs).

Then the query:

?- phrase(transform(Cs), "caaad").
   Cs = "cbd"

Answer 3

Using difference lists rather than DCG, to be faster (due in part to tail-end recursion) and also more widely compatible with Prolog systems:

find_replace_list(Find, Replace, Lst, Result) :-
    find_replace_list_(Lst, Find, Replace, Result).

find_replace_list_([], _Find, _Replace, []).
find_replace_list_([H|T], Find, Replace, Result) :-
    list_begins_dl(Find, [H|T], Tail),
    !,
    append(Replace, Result0, Result),
    find_replace_list_(Tail, Find, Replace, Result0).
find_replace_list_([H|T], Find, Replace, [H|Result]) :-
    find_replace_list_(T, Find, Replace, Result).

list_begins_dl([], T, T).
list_begins_dl([H|TShort], [H|TLong], Tail) :-
    list_begins_dl(TShort, TLong, Tail).

Performance comparison in swi-prolog:

?- numlist(1, 1_000_000, L), time(find_replace_list([a,a,a,a], [b], L, S)).
% 2,000,002 inferences, 0.231 CPU in 0.231 seconds (100% CPU, 8649354 Lips)

?- numlist(1, 1_000_000, L), time(substitute([a,a,a,a], [b], L, S)).
% 16,000,024 inferences, 2.081 CPU in 2.081 seconds (100% CPU, 7689631 Lips)


?- length(L, 1_000_000), maplist(=(1), L), time(find_replace_list([1], [2], L, S)).
% 5,000,002 inferences, 0.421 CPU in 0.421 seconds (100% CPU, 11865099 Lips)

?- length(L, 1_000_000), maplist(=(1), L), time(substitute([1], [2], L, S)).
% 25,000,021 inferences, 2.962 CPU in 2.962 seconds (100% CPU, 8439159 Lips)

Result:

?- find_replace_list([a,a,a,a], [b], [c,a,a,a,a,d], S).
S = [c,b,d].

Answer 4

Being compatible with non-ground elements, and reasonably avoiding unwanted choicepoints:

find_replace(Find, Replace, Lst, Result) :-
    % Find must contain at least 1 element
    Find = [_|_],
    find_replace_(Lst, Find, Replace, Result).

find_replace_([], _Find, _Replace, []).
find_replace_([H|T], Find, Replace, Result) :-
    lists_begin_t(Find, [H|T], Tail, Bool),
    find_replace_comp_(Bool, T, Tail, T1, H, Replace, Result, Result0),
    find_replace_(T1, Find, Replace, Result0).

find_replace_comp_(true, _, Tail, Tail, _H, Replace, Result, Result0) :-
    append(Replace, Result0, Result).
find_replace_comp_(false, T, _, T, H, _Replace, [H|Result], Result).

lists_begin_t(Short, Long, LongTail, Bool) :-
    lists_begin_t_(Short, Long, m([], []), LongTail, Bool).

lists_begin_t_([], Long, Maybes, LongTail, Bool) :-
    lists_begin_t_comp_(Bool, Maybes, Long, LongTail).
lists_begin_t_([S|Short], Long, Maybes, LongTail, Bool) :-
    lists_begin_t_l_(Long, S, Short, Maybes, LongTail, Bool).

lists_begin_t_l_([], _S, _Short, _Maybes, _LongTail, false).
lists_begin_t_l_([L|Long], S, Short, Maybes, LongTail, Bool) :-
    (   S \= L
    % Fail fast
    ->  Bool = false
    ;   (   S == L
        ->  Maybes1 = Maybes
        ;   Maybes = m(Ss, Ls),
            Maybes1 = m([S|Ss], [L|Ls])
        ),
        lists_begin_t_(Short, Long, Maybes1, LongTail, Bool)
    ).

lists_begin_t_comp_(true, m(Ss, Ls), Long, Long) :-
    % Could be empty lists
    (   Ss == Ls
    % No need to check false
    ->  !
    ;   Ss = Ls
    ).
lists_begin_t_comp_(false, m(Ss, Ls), _, _) :-
    dif(Ss, Ls).

Result in swi-prolog:

?- time(find_replace([b,X], [1,2,3], [a,b,c,b,Y], R)).
% 41 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 1511186 Lips)
X = Y, Y = c,
R = [a, 1, 2, 3, 1, 2, 3] ;
% 66 inferences, 0.000 CPU in 0.000 seconds (102% CPU, 1324689 Lips)
X = c,
R = [a, 1, 2, 3, b, Y],
dif(Y, c) ;
% 52 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 1457113 Lips)
X = Y,
R = [a, b, c, 1, 2, 3],
dif(Y, c) ;
% 53 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 702526 Lips)
R = [a, b, c, b, Y],
dif(X, c),
dif(Y, X).