表中的 Prolog 点

Question

我有一个给定的列表，表示二维列表 x。该表包含两个 1 的“点”，如下例所示：

xxxxxxxxxxxxxxxx
xx1111xxxx111xxx
xxx1111xxxx11xxx
x1111xxxxxx111xx

我只需将第二个点从 1 更改为 2，如下例所示：

xxxxxxxxxxxxxxxx
xx1111xxxx222xxx
xxx1111xxxx22xxx
x1111xxxxxx222xx

我需要一个名为 separate(L,M)< 的谓词/code> 将采用第一个列表 L 并生成第二个表 M

如果我们能够在不使用任何标准谓词（如“findall”等）的情况下解决这个问题，那就太好了......

Answer 1

您可以使用定语从句语法 (DCG) 来实现有限状态转换器。尽管 DCG 在生产方面没有提供太多组合操作，但它们在识别方面的实现相当出色。

所以你想要识别的是两种不同类型的 1 序列。所以基本上我猜输入行在扩展巴科斯范式（EBNF）中看起来如下：

line :== exs run1 exs run2 exs | exs.
exs  :== { "x" } "x".
run1 :== { "1" } "1".
run2 :== { "1" } "1".

对于识别问题，您可以编写一个没有属性的DCG（接下来是Prolog文本，您可以放入文件中或直接通过？ - [用户]）：

line --> exs, run1, exs, run2, exs | exs.

run1 --> "1", run1.
run1 --> "1".

run2 --> "1", run2.
run2 --> "1".

exs --> "x", exs.
exs --> "x".

以下是一些运行示例：

?- phrase(line,"xxx").
Yes 
?- phrase(line,"xxx111xxx111xxx").
Yes 
?- phrase(line,"xxx111xxx"). 
No

对于生产问题，您只需向 DCG 添加属性即可。使用
差异列表最简单：

line(I,O) --> exs(I,H), run1(H,J), exs(J,K), run2(K,L), exs(L,O) | exs(I,O).

run1([0'1|I],O) --> "1", run1(I,O).
run1([0'1|H],H) --> "1".

run2([0'2|I],O) --> "1", run2(I,O).
run2([0'2|H],H) --> "1".

exs([0'x|I],O) --> "x", exs(I,O).
exs([0'x|H],H) --> "x".

以下是一些运行示例：

?- phrase(line(R,[]),"xxx").
R = [120, 120, 120] 
?- phrase(line(R,[]),"xxx111xxx111xxx").
R = [120, 120, 120, 49, 49, 49, 120, 120, 120, 50, 50, 50, 120, 120, 120] 
?- phrase(line(R,[]),"xxx111xxx").
No

注意：0' 是字符代码的 Prolog 表示法。在 ascii 中，我们有 0'x = 120、0'1 = 49、0'2 = 50，这解释了结果。上面的代码应该可以在大多数 Prolog 系统上运行，因为它们支持 DCG。

再见

定语从句语法
http://en.wikipedia.org/wiki/Definite_clause_grammar

有限状态传感器
http://en.wikipedia.org/wiki/Finite_state_transducer

Answer 2

我们可以应用临时音译（仅适用于“水平”列表）：

transliteration(Matrix, Translit) :-
  maplist(transliteration(not_seen), Matrix, Translit).

transliteration(_State, [], []).
transliteration(State, [X|Xs], [Y|Ys]) :-
  transliteration(State, X, NewState, Y),
  transliteration(NewState, Xs, Ys).

% handle only required state change
transliteration(not_seen, 0'1, seen_first, 0'1).
transliteration(seen_first, C, seen_last, C) :- C =\= 0'1.
transliteration(seen_last, 0'1, seen_last, 0'2).
% catch all, when no change required
transliteration(State, C, State, C).

Answer 3

与@chac建议的解决方案类似，但更直接。

walk(L, R) :- walk(s0, L, R).
walk(_, [], []). % finish
walk(s0, [0'1|T], [0'1|R]) :- walk(s1, T, R).
walk(s1, [0'x|T], [0'x|R]) :- walk(s2, T, R).
walk(s2, [0'1|T], [0'2|R]) :- walk(s2, T, R).
walk(S, [H|T], [H|R]) :- walk(S, T, R). % keep state and do nothing