3 
union([H|T],[],[H|T]).     
union([],[H|T],[H|T]).    
union([H|T], SET2, RESULT) :- member(H,SET2), union(T,SET2,RESULT).    
union([H|T], SET2, [H|RESULT]) :- not(member(H,SET2)), union(T,SET2,RESULT).

要素が2番目のリストのメンバーであるかどうかに基づいて、最初のリストをトラバースして追加していることがわかります。私は論理を得ました。ただし、最初のリストが使い果たされると、「2番目のリスト」の要素が結果に追加されるワークフローは私には不思議です。

誰かがのような簡単な例を取り上げてunion([1,2], [2,3], Result)、ワークフローを説明してもらえますか。

4

3 に答える 3

7

I'll assume that you are calling union/3 with the first and second arguments instantiated. The third argument can be either uninstantiated upon calling and will be unified at return with the union of the two lists or if it's already instantiated it can be used to check whether it matches the (ordered) union of the first two lists.

The first clause states that if the second argument is the empty list and the first list has at least one element then the union is just this first list. Likewise, the second clause states that if the first argument is the empty list and the second list has at least one element then the union is just this second list.

The third clause recurses over the first list and checks the second list to see if the item is already there. In that case it just calls itself with the tail of the first list.

The fourth clause tests the head of the first list to check that it is not contained in the second list and calls recursively with the tail (just like the third clause). However upon return of recursion it adds the item to the head of the third list, thus adding the item to the union.

Note that in your implementation, the union of two empty sets will always fail. You can fix this by modifying the first or second clause to allow an empty list, or the add another clause for this case. E.g.

union([],[],[]).

Now let's see what happens when we call union([1,2],[2,3], Result):

The first two clauses will fail to match as neither of them are the empty list.

We enter the third clause and check to see that element 1 is not a member of the second list thus failing there.

We try now the fourth clause and test that element 1 i not in the second list, so we call union([2], [2,3], Result), we mark this execution point (*1).

Again the two first clauses will fail to match, so we enter the third clause. Here we test that indeed element 2 is contained in the second list so we call union([], [2,3], Result), we mark this execution point (*2)

Now the first clause fails as the first argument is the empty list. We now enter the second clause unifying the third argument with the second list ([2,3]).

At this point we return to (*2) where now Result gets instantiated with [2,3]. This clauses end there so we bound the third argument with [1,2,3], and we return to (*1).

We are now at (*1) where Result and therefore the third argument gets instantiated with [1,2,3].

This gives us the first result [1,2,3].

However a choice point was left when we succedded in (*2), so if we ask Prolog to search for another answer it still has to try the fourth clause of union([2],[2,3], Result).

So we enter the fourth clause to test if 2 is not a member of [2,3] which fails, so Prolog will tell us that there are no other answers.

于 2012-10-16T02:01:54.560 に答える
1

検査SET2していないため、重複がないと仮定すると、基本再帰は単一の述語になる可能性があります

union([], U, U).

@gusbroHは、SET2に属していない場合、再帰呼び出しが成功した後、結果の（ローカル）前に配置されることをすでに説明しました。

not説明は疑問を解消するはずですが、 / 1は基本的に、前の（失敗した）呼び出しですでに実行されたのとまったく同じテストを繰り返すことに注意してください。次に、より良いコードは

union([H|T], SET2, RESULT) :-
   member(H,SET2), !, % note the commit
   union(T,SET2,RESULT).    
union([H|T], SET2, [H|RESULT]) :- 
   % useless now 
   % not(member(H,SET2)),
   union(T,SET2,RESULT).

member/ 2に副作用がないと仮定すると、これはコードと同等です（そしてそうです）。

not!/ 1は、 /0を使用して実装できます。

于 2012-10-16T07:28:10.647 に答える
1

関連する質問「2つのリストの交差と結合」に対する私の回答では、交差と結合の論理的に純粋な実装を提示します。

あなたの質問に対する他の回答とは異なり、純粋なバリアントは単調であるため、根拠のない用語で使用しても論理的に健全なままです。

于 2015-04-30T08:37:40.710 に答える