list - プロローグ: 最初の重複値

Question

リスト内の最初の重複値を見つける必要があります。

prep(3,[1,3,5,3,5]).本当のはずです。

prep(5,[1,3,5,3,5]).偽でなければなりません。

重複が見つかるまで、現在の値と前のリストメンバーとの同等性をチェックすることを考えました。重複が見つかった場合は、X との同等性をテストしますが、Prolog でそれを行う方法がわかりません!

どんな助けにも感謝します！ありがとう

Answer 1

dif/2これは、音の不等式を実装する純粋なバージョンです。dif/2B-Prolog、YAP-Prolog、SICStus-PrologおよびSWI-Prologによって提供されます。

firstdup（E、[E | L]）：-
    member（E、L）。
firstdup（E、[N | L]）：-
    non_member（N、L）、
    firstdup（E、L）。

member（E、[E | _L]）。
member（E、[_X | L]）：-
    member（E、L）。

non_member（_E、[]）。
non_member（E、[F | Fs]）：-
    dif（E、F）、
    non_member（E、Fs）。

利点は、より一般的なクエリでも使用できることです。

？-firstdup（E、[A、B、C]）。
E = A、A = B;
E = A、A = C;
E = C、
B = C、
dif（A、C）;
false。

ここでは、3つの答えが得られます。A最初の2つの答えは重複していますが、2つの異なる理由で：またはAに等しい可能性があります。3番目の回答では、は重複していますが、がと異なる場合にのみ重複します。BCBCA

定義を理解するために:-、矢印として読んでください←したがって、右側にあるのはあなたが知っていることであり、左側にあるのはあなたが結論することです。述語をその方向に読むのは、最初は少しイライラすることがよくあります。結局のところ、「実行のスレッド」をたどりたくなるかもしれません。しかし、多くの場合、このスレッドはどこにもつながりません–複雑すぎて理解できません。

最初のルールは次のとおりです。

提供されているのは、最初に重複していると私たちが結論付けるEリストの要素です。L[E|L]E

2番目のルールは次のとおりです。

提供EされるのはL（ここで慌てず、それを知らないと言ってはいけない...）の最初の複製であり、それが最初の複製であると結論付けるN要素ではないという条件で。L[N|L]E

述語は多くのmember/2Prologシステムで提供されており、non_member(X,L)として定義することができますmaplist(dif(X),L)。したがって、次のように定義firstdup/2します。

firstdup（E、[E | L]）：-
    member（E、L）。
firstdup（E、[N | L]）：-
    maplist（dif（N）、L）、
    firstdup（E、L）。

Answer 2

この回答では、この以前の回答で提示された論理的に純粋なコードを改善します。ステップバイステップ:

1. 2 つの述語memberd/2andnon_member/2を 1 つに結合memberd_t/3します。これは、追加の引数を使用して、リスト メンバーシップを真理値 ( trueor false) に具体化します。

   memberd_t/3memberd/2は+と同等なnon_member/2ので、次のように定義できます。

   memberd_t(X、Xs、真) :-
      memberd(X,Xs)。
   memberd_t(X,Xs,false) :-
      non_member(X,Xs)。
   

   または、逆に、次のように定義することもできます。memberd/2non_member/2

   メンバー (X、X) :-
      memberd_t(X,Xs,true).
   
   非メンバー (X、Xs) :-
      memberd_t(X,Xs,false)。
   

   実際には、調整された実装を使用しますmemberd_t/3—決定性が向上したもの。

   実際にと!のmemberd_t/3両方をカバーしていることを見てみましょう。memberd/2 non_member/2

   ?- memberd_t(X,[1,2,3],T)。
     T = 真、X=1
   ; T = 真、X=2
   ; T = 真、X=3
   ; T = false、dif(X,1)、dif(X,2)、dif(X,3)。
   

2. 出発点として、述語の次のバリアントfirstdup/2(以前に定義された) を使用します。

   firstdup(E,[X|Xs]) :-
      ( memberd(X,Xs),
         E=X      
      ; non_member(X,Xs),
         firstdup(E,Xs)
      ）。
   

3. memberd/2との使用をnon_member/2に置き換えましょうmemberd_t/3!

   firstdup(E,[X|Xs]) :-
      ( memberd_t(X,Xs,true),
         E=X
      ; memberd_t(X,Xs,false),
         firstdup(E,Xs)
      ）。
   

4. 上げようmemberd_t/3！

   firstdup(E,[X|Xs]) :-
      memberd_t(X,Xs,T),
      ( T=真
      -> E=X      
      ; T=偽、
         firstdup(E,Xs)
      ）。
   

5. 上記のパターンは、 と書くpred_t(OtherArgs,T), (T = true -> Then ; T = false, Else)とより簡潔に表現できます。if_/3if_(pred_t(OtherArgs),Then,Else)

   firstdup(E,[X|Xs]) :-
      if_(memberd_t(X,Xs),
          E=X、
          firstdup(E,Xs))。
   

---

クエリを実行してみましょう。

?- firstdup( 1 ,[ 1 ,2,3, 1 ])。
真実。% は決定論的に成功します

?- firstdup( X ,[ 1 ,2,3, 1 ])。
X = 1 . % は決定論的に成功します

?- firstdup(X,[A,B,C])。% が成功し、choicepoint が残ります
      A=X , B=X % ... 完全な解セットを保持します。
; A=X , dif(B,X), C=X
; dif(A,X), B=X , C=X
; 間違い。

Answer 3

rep(N,List) :- append(L1,[N|_],List),append(_,[N|_],L1),\+(rep(_,L1)).

Answer 4

これが宿題かどうかはわかりません/使用できる述語には制限がありますが、これによりプロローグが再帰を実行します。

それは言います..すべての重複を見つけます。ここで、リスト インデックス I1 の項目と I2 の別の項目があり、両方とも同じ値 N を持ち、インデックスが同じではありません。つまり、同じリスト項目を重複と見なさないでください。

これらの重複はリスト AllDups に (見つかった順序で、決定的に最初から) 配置され、最初に見つかった重複がチェックしている値である M と一致する場合、述語は true になります。

最初の試行: これは機能しますが、非常に非効率的で、すべての重複のリストを作成します

prep(M, List) :-
    findall(N,
        (nth0(I1, List, N),
        nth0(I2, List, N),
        not(I1 =:= I2)),
        AllDups),
    nth1(1, AllDups, M).


?- prep(3,[1,3,5,3,5]).
true.

?- prep(5,[1,3,5,3,5]).
false.

findall の使用が許可されていない場合でも、「手動で」行う方法を理解するのに役立つ場合があります。

2 回目の試行: これは機能しません / バックトラックが多すぎて誤検知が発生します

findall がなくても実行できます。 nth0 を使用して最初の重複項目を見つけ、それがチェックしている値と一致する場合は true を返し、そうでない場合は false を返します。

prep(N, List) :-
        nth0(I1, List, N),
        nth0(I2, List, N),
        not(I1 =:= I2).

3 回目の試行: これは機能し、最初の重複が見つかるとすぐに戻ります

prep(M, List) :-
        nth0(I1, List, N),
        nth0(I2, List, N),
        not(I1 =:= I2), !,
        M == N.