4

我对 Prolog 很陌生,我需要一些帮助来解决一个小问题:

我正在尝试将情侣列表分成两个列表。第一个列表包含具有给定键的所有对,第二个列表包含所有其他对象。

这是我到目前为止的代码:

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)],但我却错了。有人可以告诉我我做错了什么吗?

提前致谢,

瓦勒

4

3 回答 3

6

让我们看看倒数第二个递归调用:

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

在我标记的地方,您希望第一个列表仍然具有至少一个元素。然而最后的递归调用不能满足这个条件。这就是它失败的原因。跟踪的相关部分是:

# 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

问题在于基本情况。采取身体中的两种情况中的任何一种:

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/4lambdas(=)/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,黄色),( 1,蓝色)],未命中 = [(2,绿色),(2,红色)]。% 确定性

更一般东西怎么样?

?- splitList([(1,yellow),(2,green),(1,blue),(2,red)], K ,Hits,Misses)。
      K=1,命中 = [(1,黄色),(1,蓝色)],未命中 = [(2,绿色),(2,红色)]
;               K=2,命中 = [( 2 , green),( 2 , red)], Misses = [(1,yellow),(1,blue)]
; dif(K,1), dif(K,2), Hits = [] , Misses = [(1,yellow),(1,blue),
                                                              (2,绿色),(2,红色)]。
于 2015-08-20T19:44:29.813 回答