8

免責事項：これは、私自身の時間に行う非公式で評価されていないコースワークです。私はそれを自分で試しましたが、失敗し、現在いくつかのガイダンスを探しています。

リストのメンバーを1回だけ返すバージョンのmember/2関数を実装しようとしています。

例えば：

| ?- member(X, [1,2,3,1]).
X = 1 ? ;
X = 2 ? ;
X = 3 ? ;
X = 1 ? ;

各番号を最大1回だけ印刷してほしい。

| ?- once_member(X, [1,2,3,1]).
X = 1 ? ;
X = 2 ? ;
X = 3 ? ;
no

カット「！」でこれを行うように言われました。オペレーターですが、私は自分のコースのメモを調べてカットやオンラインを増やしましたが、それでも頭の中でクリックすることはできません！

これまでのところ、私はなんとか取得できました：

once_member(E, [E | L]) :- !.
once_member(E, [_, L]) :-
    once_member(E, L).

これは1を返し、それ以外は何も返しません。カットが間違った場所にあり、可能な試合ごとにバックトラックを妨げているように感じますが、次にどこに行くのか本当にわかりません。

コースノートと、http：//www.cs.ubbcluj.ro/~csatol/log_funk/prolog/slides/5-cuts.pdfおよびProgramming in Prolog（Googleブックス）も確認しました。

カットを論理的に適用する方法についてのガイダンスが最も役立ちますが、答えは私がそれを自分で理解するのに役立つかもしれません。

また、失敗による'\ +'否定を使用する別の方法を実行するように言われましたが、カットが私のために小刻みに動いたら、これはもっと簡単かもしれませんか？

4

4 に答える 4

2

冗長な答えを削除し、純粋なままにしてください！

とmemberd/2に基づいて定義します：if_/3(=)/3

memberd（X、[E | Es]）：-
   if_（X = E、true、memberd（X、Es））。

特にメタ述語では、異なる引数の順序が役立つ場合があります。

list_memberd(Es, X) :-
   memberd(X, Es).

サンプルクエリ：

?- memberd(X, [1,2,3,1]).
X = 1 ;
X = 2 ;
X = 3 ;
false.
于 2015-04-03T13:27:24.683 に答える
1 
once_member(X, Xs) :-
   sort(Xs, Ys),
   member(X, Ys).

投稿された他のほとんどすべてのソリューションと同様に、これにはいくつかの異常があります。

?- X = 1, once_member(X, [A,B]).
X = A, A = 1 ;
X = B, B = 1.

?- X = 1, once_member(X, [A,A]).
X = A, A = 1.
于 2011-11-28T08:34:24.773 に答える
1

カットによる解決策...最初はかなり面倒に聞こえます。

最初の引数がインスタンス化されると仮定すると、解決策は簡単です。

once_member(X,L):-
    member(X,L),!.

ただし、最初の引数がインスタンス化されていない場合、これは希望する動作をしません。
リスト要素のドメイン（たとえば、1から42までの数字）がわかっている場合は、最初の引数をインスタンス化できます。

once_member(X,L):-
    between(1,42,X),
    member_(X,L).

member_(X,L):-
    member(X,L),!.

しかし、これは非常に非効率的です

この時点で、カットだけでは不可能だと思い始めました（+またはlist_to_set / 2を使用しないと仮定します
！<ここにアイデアの絵文字を挿入>

リストを取得し、すべての重複要素が削除されたリストを生成する述語（ swi-prologのlist_to_set / 2など）を実装できれば、通常のmember / 2を使用するだけで、重複した結果は得られません。やってみて、自分で書けると思います。

--------ネタバレ------------

    one_member(X,L):-
        list_to_set(L,S),
        member(X,S).

    list_to_set([],[]).
    list_to_set([H|T],[H|S]):-
        remove_all(H,T,TT),
        list_to_set(TT,S).

%remove_all(X,L,S): S is L if we remove all instances of X
    remove_all(_,[],[]).
    remove_all(X,[X|T],TT):-
        remove_all(X,T,TT),!.
    remove_all(X,[H|T],[H|TT]):-
        remove_all(X,T,TT).

ご覧のとおり、remove_all / 3でカットを使用する必要がremove_all(X,[X|_],_)あります。そうしないと、HがXと異なることを指定しないため、3番目の句が一致する可能性があります。notを使用したソリューションは簡単だと思います。

ところで、notを使用したソリューションは、cutを使用したソリューションよりも宣言型であると見なすことができます。使用したカットは、プログラムの動作を変更するため、通常はレッドカットと呼ばれます。そして、他にも問題があります。remove_all(1,[1,2],[1,2])カットしても成功することに注意してください。

一方、状態を2回チェックするのは効率的ではありません。したがって、if-then-else構造を使用するのが最適です（ただし、これも使用できないと思います。実装はカットで実行できます）。

一方、notを使用した別のより簡単な実装があります。Xがリストのメンバーであるかどうかだけでなく、以前にXに遭遇したことがあるかどうかも確認する必要があります。したがって、アキュムレータが必要になります。

-------------ネタバレ--------------------

once_member(X,L):-
    once_member(X,L,[]).
once_member(X,[X|_T],A):-
    \+once_member(X,A).
once_member(X,[H|T],A):-
    once_member(X,T,[H|A]).
于 2011-11-27T00:35:50.943 に答える
-1

これは、 once_member/2の定義のカットを従来のmember/2述語と一緒に使用するアプローチです。

once_member(X,[H|T]) :-
    member(H,T),
    !,
    once_member(X,T).
once_member(H,[H|_]).
once_member(X,[_|T]) :-
    once_member(X,T).

上記の例に適用：

?- once_member(X,[1,2,3,1]).

X = 2 ;

X = 3 ;

X = 1 ;
no

注：奇妙に見える3つの句の定義にもかかわらず、once_member / 2は、最初の自己呼び出しの前にカットが配置されるため、最後の呼び出し/末尾再帰の最適化に適格です。

于 2011-11-27T14:51:13.977 に答える