Prolog: a list of characters <=> list of character list 字符列表
Prolog: a list of characters <=> list of character list
我正在实现一个 words/2 谓词，其中可以将字符列表呈现为字符列表作为列表中的单词。我使用数学符号 <=> 表示它们在任何模式下工作。有没有更好的表达方式请指教
例子：
?- words([p,r,o,l,o,g,' ',i,s,' ',g,o,o,d],Y).
Y = [[p,r,o,l,o,g],[i,s],[g,o,o,d]]
?- words(X,[[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
X = [p,r,o,l,o,g,' ',i,s,' ',g,o,o,d]
我所做的是尝试使用 append/3 如下所示，尝试将空字符串放在中间，并将它们连接在一起。并使用 NewCharList 递归 List，但因“超出本地堆栈”而失败。
% base case, empty list
words([],[]).
% X is a list of characters
% Y is a list with characters list as a word
words(CharList,[WordList|List]):-
append(WordList,[' '],NewWord),
append(NewWord,CharList,NewCharList),
words(NewCharList,List).
我该如何改进代码？谢谢。
编辑1
来自@rajashekar 的百万感谢。现在我明白了代码
% base case
split(_, [], [[]]).
% when the the element list of Ys is empty
% add a C to the Xs, in this case, C is a empty string ' '
split(C, [C|Xs], [[]|Ys]) :-
split(C, Xs, Ys).
% put the X character from [X|Y] list to Xs
% and goes on next word list
split(C, [X|Xs], [[X|Y]|Ys]) :-
split(C, Xs, [Y|Ys]).
但在我的 SWI-prolog 中，似乎很奇怪：
?-split(' ', X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
X = [p, r, o, l, o, g, ' ', i, s|...]
跟踪记录如下：
[trace] ?- split(X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
Call: (10) split(_5702, [[p, r, o, l, o, g], [i, s], [g, o, o, d]]) ? creep
Call: (11) split(_6210, [[r, o, l, o, g], [i, s], [g, o, o, d]]) ? creep
Call: (12) split(_6266, [[o, l, o, g], [i, s], [g, o, o, d]]) ? creep
Call: (13) split(_6322, [[l, o, g], [i, s], [g, o, o, d]]) ? creep
Call: (14) split(_6378, [[o, g], [i, s], [g, o, o, d]]) ? creep
Call: (15) split(_6434, [[g], [i, s], [g, o, o, d]]) ? creep
Call: (16) split(_6490, [[], [i, s], [g, o, o, d]]) ? creep
Call: (17) split(_6546, [[i, s], [g, o, o, d]]) ? creep
Call: (18) split(_6596, [[s], [g, o, o, d]]) ? creep
Call: (19) split(_6652, [[], [g, o, o, d]]) ? creep
Call: (20) split(_6708, [[g, o, o, d]]) ? creep
Call: (21) split(_6758, [[o, o, d]]) ? creep
Call: (22) split(_6814, [[o, d]]) ? creep
Call: (23) split(_6870, [[d]]) ? creep
Call: (24) split(_6926, [[]]) ? creep
Exit: (24) split([], [[]]) ? creep
Exit: (23) split([d], [[d]]) ? creep
Exit: (22) split([o, d], [[o, d]]) ? creep
Exit: (21) split([o, o, d], [[o, o, d]]) ? creep
Exit: (20) split([g, o, o, d], [[g, o, o, d]]) ? creep
Exit: (19) split([' ', g, o, o, d], [[], [g, o, o, d]]) ? creep
Exit: (18) split([s, ' ', g, o, o, d], [[s], [g, o, o, d]]) ? creep
Exit: (17) split([i, s, ' ', g, o, o, d], [[i, s], [g, o, o, d]]) ? creep
Exit: (16) split([' ', i, s, ' ', g, o, o, d], [[], [i, s], [g, o, o, d]]) ? creep
Exit: (15) split([g, ' ', i, s, ' ', g, o, o|...], [[g], [i, s], [g, o, o, d]]) ? creep
Exit: (14) split([o, g, ' ', i, s, ' ', g, o|...], [[o, g], [i, s], [g, o, o, d]]) ? creep
Exit: (13) split([l, o, g, ' ', i, s, ' ', g|...], [[l, o, g], [i, s], [g, o, o, d]]) ? creep
Exit: (12) split([o, l, o, g, ' ', i, s, ' '|...], [[o, l, o, g], [i, s], [g, o, o, d]]) ? creep
Exit: (11) split([r, o, l, o, g, ' ', i, s|...], [[r, o, l, o, g], [i, s], [g, o, o, d]]) ? creep
Exit: (10) split([p, r, o, l, o, g, ' ', i|...], [[p, r, o, l, o, g], [i, s], [g, o, o, d]]) ? creep
X = [p, r, o, l, o, g, ' ', i, s|...] .
EDIT2
我发现使用 !（剪切）可以减少回溯。
% base case
split(_, [], [[]]).
% when the the element list of Ys is empty
% add a C to the Xs, in this case, C is a empty string ' '
split(C, [C|Xs], [[]|Ys]) :-
split(C, Xs, Ys),!.
% put the X character from [X|Y] list to Xs
% and goes on next word list
split(C, [X|Xs], [[X|Y]|Ys]) :-
split(C, Xs, [Y|Ys]),!.
split(_, [], [[]]).
split(C, [C|Xs], [[]|Ys]) :-
split(C, Xs, Ys).
split(C, [X|Xs], [[X|Y]|Ys]) :-
split(C, Xs, [Y|Ys]).
| ?- split(' ', [p,r,o,l,o,g,' ',i,s,' ',g,o,o,d], X).
X = [[p,r,o,l,o,g],[i,s],[g,o,o,d]] ?
yes
| ?- split(' ', X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
X = [p,r,o,l,o,g,' ',i,s,' ',g,o,o,d] ?
yes
- 你可以使用模式声明来说明谓词在两种模式下都有效。例如，您可以说
words/2 谓词需要在 words(+Chars, -Words) 和 words(-Chars, +Words) 模式（或 words(+, -) 和 words(-, +) 模式下工作）。 See for mode details. These are mostly used for documentation purposes in prolog (check out mercury 他们真正工作的地方）。
- 使用
Definite Clause Grammers DCG 将使此类问题变得容易得多。
- 当您感到 运行 远离递归时，请尝试使用
trace。如果你使用它，大多数时候你可以发现问题。
代码完全符合您的要求。
这里：
?-split(' ', X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
X = [p, r, o, l, o, g, ' ', i, s|...]
X 正是预期的输出。
如果您想查看所有 X，请执行：
?-split(' ', X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]), write_canonical(X).
[p,r,o,l,o,g,' ',i,s,' ',g,o,o,d]
X = [p, r, o, l, o, g, ' ', i, s|...]
SWI 序言中的输出会缩短长列表。
我正在实现一个 words/2 谓词，其中可以将字符列表呈现为字符列表作为列表中的单词。我使用数学符号 <=> 表示它们在任何模式下工作。有没有更好的表达方式请指教
例子：
?- words([p,r,o,l,o,g,' ',i,s,' ',g,o,o,d],Y).
Y = [[p,r,o,l,o,g],[i,s],[g,o,o,d]]
?- words(X,[[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
X = [p,r,o,l,o,g,' ',i,s,' ',g,o,o,d]
我所做的是尝试使用 append/3 如下所示，尝试将空字符串放在中间，并将它们连接在一起。并使用 NewCharList 递归 List，但因“超出本地堆栈”而失败。
% base case, empty list
words([],[]).
% X is a list of characters
% Y is a list with characters list as a word
words(CharList,[WordList|List]):-
append(WordList,[' '],NewWord),
append(NewWord,CharList,NewCharList),
words(NewCharList,List).
我该如何改进代码？谢谢。
编辑1 来自@rajashekar 的百万感谢。现在我明白了代码
% base case
split(_, [], [[]]).
% when the the element list of Ys is empty
% add a C to the Xs, in this case, C is a empty string ' '
split(C, [C|Xs], [[]|Ys]) :-
split(C, Xs, Ys).
% put the X character from [X|Y] list to Xs
% and goes on next word list
split(C, [X|Xs], [[X|Y]|Ys]) :-
split(C, Xs, [Y|Ys]).
但在我的 SWI-prolog 中，似乎很奇怪：
?-split(' ', X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
X = [p, r, o, l, o, g, ' ', i, s|...]
跟踪记录如下：
[trace] ?- split(X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
Call: (10) split(_5702, [[p, r, o, l, o, g], [i, s], [g, o, o, d]]) ? creep
Call: (11) split(_6210, [[r, o, l, o, g], [i, s], [g, o, o, d]]) ? creep
Call: (12) split(_6266, [[o, l, o, g], [i, s], [g, o, o, d]]) ? creep
Call: (13) split(_6322, [[l, o, g], [i, s], [g, o, o, d]]) ? creep
Call: (14) split(_6378, [[o, g], [i, s], [g, o, o, d]]) ? creep
Call: (15) split(_6434, [[g], [i, s], [g, o, o, d]]) ? creep
Call: (16) split(_6490, [[], [i, s], [g, o, o, d]]) ? creep
Call: (17) split(_6546, [[i, s], [g, o, o, d]]) ? creep
Call: (18) split(_6596, [[s], [g, o, o, d]]) ? creep
Call: (19) split(_6652, [[], [g, o, o, d]]) ? creep
Call: (20) split(_6708, [[g, o, o, d]]) ? creep
Call: (21) split(_6758, [[o, o, d]]) ? creep
Call: (22) split(_6814, [[o, d]]) ? creep
Call: (23) split(_6870, [[d]]) ? creep
Call: (24) split(_6926, [[]]) ? creep
Exit: (24) split([], [[]]) ? creep
Exit: (23) split([d], [[d]]) ? creep
Exit: (22) split([o, d], [[o, d]]) ? creep
Exit: (21) split([o, o, d], [[o, o, d]]) ? creep
Exit: (20) split([g, o, o, d], [[g, o, o, d]]) ? creep
Exit: (19) split([' ', g, o, o, d], [[], [g, o, o, d]]) ? creep
Exit: (18) split([s, ' ', g, o, o, d], [[s], [g, o, o, d]]) ? creep
Exit: (17) split([i, s, ' ', g, o, o, d], [[i, s], [g, o, o, d]]) ? creep
Exit: (16) split([' ', i, s, ' ', g, o, o, d], [[], [i, s], [g, o, o, d]]) ? creep
Exit: (15) split([g, ' ', i, s, ' ', g, o, o|...], [[g], [i, s], [g, o, o, d]]) ? creep
Exit: (14) split([o, g, ' ', i, s, ' ', g, o|...], [[o, g], [i, s], [g, o, o, d]]) ? creep
Exit: (13) split([l, o, g, ' ', i, s, ' ', g|...], [[l, o, g], [i, s], [g, o, o, d]]) ? creep
Exit: (12) split([o, l, o, g, ' ', i, s, ' '|...], [[o, l, o, g], [i, s], [g, o, o, d]]) ? creep
Exit: (11) split([r, o, l, o, g, ' ', i, s|...], [[r, o, l, o, g], [i, s], [g, o, o, d]]) ? creep
Exit: (10) split([p, r, o, l, o, g, ' ', i|...], [[p, r, o, l, o, g], [i, s], [g, o, o, d]]) ? creep
X = [p, r, o, l, o, g, ' ', i, s|...] .
EDIT2
我发现使用 !（剪切）可以减少回溯。
% base case
split(_, [], [[]]).
% when the the element list of Ys is empty
% add a C to the Xs, in this case, C is a empty string ' '
split(C, [C|Xs], [[]|Ys]) :-
split(C, Xs, Ys),!.
% put the X character from [X|Y] list to Xs
% and goes on next word list
split(C, [X|Xs], [[X|Y]|Ys]) :-
split(C, Xs, [Y|Ys]),!.
split(_, [], [[]]).
split(C, [C|Xs], [[]|Ys]) :-
split(C, Xs, Ys).
split(C, [X|Xs], [[X|Y]|Ys]) :-
split(C, Xs, [Y|Ys]).
| ?- split(' ', [p,r,o,l,o,g,' ',i,s,' ',g,o,o,d], X).
X = [[p,r,o,l,o,g],[i,s],[g,o,o,d]] ?
yes
| ?- split(' ', X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
X = [p,r,o,l,o,g,' ',i,s,' ',g,o,o,d] ?
yes
- 你可以使用模式声明来说明谓词在两种模式下都有效。例如，您可以说
words/2谓词需要在words(+Chars, -Words)和words(-Chars, +Words)模式（或words(+, -)和words(-, +)模式下工作）。 See for mode details. These are mostly used for documentation purposes in prolog (check out mercury 他们真正工作的地方）。 - 使用
Definite Clause GrammersDCG 将使此类问题变得容易得多。 - 当您感到 运行 远离递归时，请尝试使用
trace。如果你使用它，大多数时候你可以发现问题。
代码完全符合您的要求。 这里：
?-split(' ', X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
X = [p, r, o, l, o, g, ' ', i, s|...]
X 正是预期的输出。
如果您想查看所有 X，请执行：
?-split(' ', X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]), write_canonical(X).
[p,r,o,l,o,g,' ',i,s,' ',g,o,o,d]
X = [p, r, o, l, o, g, ' ', i, s|...]
SWI 序言中的输出会缩短长列表。