我想在 Prolog 中替换 DCG 语法中的一系列标记。换句话说，用子列表 B：[b] 替换序列或子列表 A：[a,a,a,a]。
chain --> chain_where_sublist_A_is_replaced_by_sublist_B 但完全使用 DCG 形式主义。
例如：[c,a,a,a,a,d] 给出 [c,b,d]
第一个解决方案：
eos_([], []).
transform --> call(eos_).
transform, [b] --> [a,a,a], transform.
transform, [c] --> [c], transform.
transform, [d] --> [d], transform.
然后查询：
?- phrase(transform, "caaad", Cs).
Cs = "cbd"
第二种解决方案：
step(b) --> [a,a,a].
step(C) --> [C].
transform([]) --> [].
transform([C|Cs]) --> step(C), transform(Cs).
然后查询：
?- phrase(transform(Cs), "caaad").
Cs = "cbd"
兼容非接地元素，合理避免不必要的选择点：
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).
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).
如 Prolog - 用字符串本身未使用的字母替换字符串的子串
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).
在 swi-prolog 中：
?- substitute([a,a,a,a], [b], [c,a,a,a,a,d], S).
S = [c,b,d].
使用差异列表而不是 DCG，速度更快（部分归因于尾端递归）并且与 Prolog 系统更广泛地兼容：
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).
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)
结果：
?- find_replace_list([a,a,a,a], [b], [c,a,a,a,a,d], S).
S = [c,b,d].