Splitting a list in prolog

Question

I'm pretty new to Prolog, and I need some help with a small problem:

I'm trying to split a list of couples in two lists. The first list contains all the couples with the given key, the second list contains all the other objects.

This is the code I have so far:

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

When I try to test it, this is what I get:

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

The obvious solution should be X = [(1,yellow),(1,blue)] and Y = [(2,yellow),(2,blue)], but I get false instead. Can someone tell me what I'm doing wrong?

Thanks in advance,

Walle

score 6 · Accepted Answer · answered Oct 19 '12 at 16:06

Let's look at the penultimate recursive call:

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

In the place I marked you expect the first list to still have at least one element. However the last recursive call cannot fulfill this condition. That's why it is failing. The relevant part of your trace is:

# 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

There is no substitution that would allow _G4949 variable to exist in the last call.

I'd write it this way:

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

BTW, well-asked question!

score 4 · Answer 2 · answered Oct 19 '12 at 16:05

The problem is in the base case. Take any of the two cases in the body:

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

When you get to the end everything unifies correctly except the last argument, i.e. Rest=[], B=_, List1=[]... but [Elem2|List2] doesn't unify with [].

So the procedure fails.

Try something like this (I haven't run it):

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

score 1 · Answer 3 · edited May 23 '17 at 12:02

No need to worry about writing recursive code (and about getting it right, too)!

We define splitList/4 as follows (using meta-predicate tpartition/4, lambdas, and (=)/3):

:- use_module(library(lambda)).

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

Sample query:

?- splitList([(1,yellow),(2,green),(1,blue),(2,red)],1,Hits,Misses).
Hits = [(1,yellow),(1,blue)], Misses = [(2,green),(2,red)].   % deterministic

How about something a lil' bit more general?

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

Splitting a list in prolog

3 Answers3