在Prolog中拆分一个列表

Question

我对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,黄色),(1,蓝色)]和Y = [(2,黄色),(2，蓝色)],但我得到的是false。 有人能告诉我我错在哪里吗？

提前致谢，

Walle

- Walle

Answer 1

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

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).

顺便说一句，问得好！

- liori

Answer 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).

- NotAUser

Answer 3

不需要担心编写递归代码（也不需要担心正确性！）

我们使用元谓语 tpartition/4, lambda表达式和(=)/3来定义splitList/4，具体如下：

:- 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).
Hits = [(1,yellow),(1,blue)], Misses = [(2,green),(2,red)].   % 确定性结果

再来点更加通用的东西怎么样?

?- splitList([(1,yellow),(2,green),(1,blue),(2,red)],K,Hits,Misses).
      K=1 ,           Hits = [(1,yellow),(1,blue)], Misses = [(2, green),(2, red)]
;               K=2 , Hits = [(2, green),(2, red)], Misses = [(1,yellow),(1,blue)]
; dif(K,1), dif(K,2), Hits = []                   , Misses = [(1,yellow),(1,blue),
                                                              (2, green),(2, red)].

- repeat