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/4、lambdas和(=)/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 回答