Prolog Listing

Question

I am new to Prolog and I need help with a little problem:

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

This is the code that I still have:

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 instead I get false. Can someone tell me what I'm doing wrong?

Thanks in advance,

Walle

Answer 1

Let's look at the penultimate recursive call:

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

In the place I noted, you expect at least one element to remain in the first list. However, the last recursive call cannot fulfill this condition. That is why he fails. Relevant part of your footprint:

 # 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 the _G4949 variable to exist in the last call.

I would write like this:

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

By the way, the question asked!

Answer 2

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

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

When you get to the end, everything joins correctly except for the last argument, i.e. Rest=[], B=_, List1=[] ... but [Elem2|List2] does not merge with [] .

Thus, the procedure failed.

Try something like this (I did not 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). 

Answer 3

No need to worry about writing recursive code (and how to do it right)!

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

Request example:

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