テーブル内のプロローグスポット

Question

2次元リストxを表すリストがあります。あなたは以下の例でわかるように、このテーブルには、1の2つの「スポット」を含んでいます

xxxxxxxxxxxxxxxx 
xx1111xxxx111xxx 
xxx1111xxxx11xxx 
x1111xxxxxx111xx 

私は以下の例のように1から2への唯一の二箇所を変更する必要があります。

xxxxxxxxxxxxxxxx 
xx1111xxxx222xxx 
xxx1111xxxx22xxx 
x1111xxxxxx222xx 

私は最初のリストLを取ると第二のテーブルM

我々は「findAllの」などのような任意の標準述語を使用せずにこの問題を解決することができればそれは素晴らしいだろうが生成されますseparate(L,M)と呼ばれる述語を...必要

Answer 1

DCG（Definite Clause Grammars）を使用して、有限状態トランスデューサを実装することができます。 DCGはプロダクション側で多くの構成操作を提供しませんが、認識側の実装にはかなり優れています。

あなたが認識したいのは、2つの異なるタイプの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' 文字コードのプロローグ表記法です。アスキーでは、0'x = 120,0'1 = 49,0'2 = 50となり、結果が説明されます。上記は、DCGをサポートしているため、ほとんどのPrologシステムで実行する必要があります。

さようなら

確定節文法
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

solに似ています@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