4

私はPrologにかなり慣れていないので、小さな問題について助けが必要です。

カップルのリストを2つのリストに分割しようとしています。最初のリストには、指定されたキーを持つすべてのカップルが含まれ、2番目のリストには他のすべてのオブジェクトが含まれます。

これは私がこれまでに持っているコードです：

splitList([],_,[],[]).
splitList([(A,X)|Rest], B, [Elem1|List1], [Elem2|List2]):-
    (
        A == B
    ->
        Elem1 = (A,X),
        splitList(Rest, B, List1, [Elem2|List2])
    ;
        Elem2 = (A,X),
        splitList(Rest, B, [Elem1|List1], List2)
    ).

私がそれをテストしようとすると、これは私が得るものです：

[trace] [3] 143 ?- splitList([(1,yellow),(1,blue),(2,yellow),(2,blue)],1,X,Y).
   Call: (37) splitList([ (1, yellow), (1, blue), (2, yellow), (2, blue)], 1, _G4821, _G4822) ? creep
   Call: (38) 1==1 ? creep
   Exit: (38) 1==1 ? creep
   Call: (38) _G4928= (1, yellow) ? creep
   Exit: (38) (1, yellow)= (1, yellow) ? creep
   Call: (38) splitList([ (1, blue), (2, yellow), (2, blue)], 1, _G4929, [_G4931|_G4932]) ? creep
   Call: (39) 1==1 ? creep
   Exit: (39) 1==1 ? creep
   Call: (39) _G4940= (1, blue) ? creep
   Exit: (39) (1, blue)= (1, blue) ? creep
   Call: (39) splitList([ (2, yellow), (2, blue)], 1, _G4941, [_G4931|_G4932]) ? creep
   Call: (40) 2==1 ? creep
   Fail: (40) 2==1 ? creep
   Call: (40) _G4931= (2, yellow) ? creep
   Exit: (40) (2, yellow)= (2, yellow) ? creep
   Call: (40) splitList([ (2, blue)], 1, [_G4949|_G4950], _G4932) ? creep
   Call: (41) 2==1 ? creep
   Fail: (41) 2==1 ? creep
   Call: (41) _G4958= (2, blue) ? creep
   Exit: (41) (2, blue)= (2, blue) ? creep
   Call: (41) splitList([], 1, [_G4949|_G4950], _G4959) ? creep
   Fail: (41) splitList([], 1, [_G4949|_G4950], _G4959) ? creep
   Fail: (40) splitList([ (2, blue)], 1, [_G4949|_G4950], _G4932) ? creep
   Fail: (39) splitList([ (2, yellow), (2, blue)], 1, _G4941, [_G4931|_G4932]) ? creep
   Fail: (38) splitList([ (1, blue), (2, yellow), (2, blue)], 1, _G4929, [_G4931|_G4932]) ? creep
   Fail: (37) splitList([ (1, yellow), (1, blue), (2, yellow), (2, blue)], 1, _G4821, _G4822) ? creep
false.

明らかな解決策はX=[（1、yellow）、（1、blue）]およびY = [（2、yellow）、（2、blue）]であるはずですが、代わりにfalseになります。誰かが私が間違っていることを教えてもらえますか？

前もって感謝します、

ウォーリー

4

3 に答える 3

6

最後から2番目の再帰呼び出しを見てみましょう。

splitList([(2,blue)], 1, [Elem1|List1], [Elem2|List2])
                          ^^^^^^^^^^^

私がマークした場所では、最初のリストに少なくとも1つの要素が残っていると予想されます。ただし、最後の再帰呼び出しはこの条件を満たすことができません。それが失敗している理由です。トレースの関連部分は次のとおりです。

# penultimate call:
Call: (40) splitList([ (2, blue)], 1, [_G4949|_G4950], _G4932) ? creep
[…]
# last call:
Call: (41) splitList([], 1, [_G4949|_G4950], _G4959) ? creep
Fail: (41) splitList([], 1, [_G4949|_G4950], _G4959) ? creep

最後の呼び出しで_G4949変数が存在できるようにする置換はありません。

私はそれをこのように書きます：

splitList([], _, [], []).
splitList([(A, X)|Rest], A, [(A, X)|Rest1], Rest2) :-
        splitList(Rest, A, Rest1, Rest2).
splitList([(A, X)|Rest], B, Rest1, [(A, X)|Rest2]) :-
        A =\= B,
        splitList(Rest, B, Rest1, Rest2).

ところで、よくある質問です！

于 2012-10-19T16:06:49.600 に答える
4

問題は基本ケースにあります。体内の2つのケースのいずれかを取ります。

splitList(Rest, B, List1, [Elem2|List2])

最後に到達すると、最後の引数、つまりRest=[], B=_, List1=[]...を除いてすべてが正しく統合されますが、。[Elem2|List2]と統合されません[]。

したがって、手順は失敗します。

このようなことを試してください（私はそれを実行していません）：

splitList([],_,[],[]).
splitList([(A,X)|Rest], A, [(A,X)|List1], List2):- !
        splitList(Rest, A, List1, List2).
splitList([(B,X)|Rest], A, List1, [(B,X) | List2]):- 
        splitList(Rest, A, List1, List2).
于 2012-10-19T16:05:07.993 に答える
1

再帰的なコードを書くことについて（そしてそれを正しくすることについても）心配する必要はありません！

次のように定義splitList/4します（ tpartition/4、ラムダ、およびを使用(=)/3）。

:- use_module(library(lambda)).

splitList(KVs,K,Hits,Misses) :-
   tpartition(K+\(K0,_)^(K0=K),KVs,Hits,Misses).

サンプルクエリ：

？-splitList（[（1、yellow）、（2、green）、（1、blue）、（2、red）]、1、Hits、Misses）。
ヒット=[（1、yellow）、（1、blue）]、ミス= [（2、g​​reen）、（2、red）]。％決定論的

もう少し一般的なものはどうですか？

？-splitList（[（1、yellow）、（2、green）、（1、blue）、（2、red）]、K、Hits、Misses）。
      K = 1、ヒット= [（1、黄色）、（1、青）]、ミス= [（2、緑）、（2、赤）]
;               K = 2、ヒット= [（2、緑）、（2、赤）]、ミス= [（1、黄色）、（1、青）]
; dif（K、1）、dif（K、2）、ヒット= []、ミス= [（1、黄色）、（1、青）、
                                                              （2、緑）、（2、赤）]。
于 2015-08-20T19:44:29.813 に答える