Fixing list output in Prolog

Question

I'm trying to make a solver for the Dutch National flag problem. Basically, given a list, I want to sort them in the order of Red-White-Blue. Red, White and Blue are defined by their predicates (i.e. red(x), white(x) etc.) Currently, I have the following code:

red(1).
white(2).
blue(3).

dutch(Xs,Ys):- 
    getRed(Xs,[], Red), getWhite(Xs,[],White), getBlue(Xs,[],Blue), 
    append([], Red, Y1), append(Y1, White, Y2), append(Y2, Blue, Ys).

getRed([],Rs,Rs).
getRed([X|Rest], Acc, Rs) :- red(X), getRed(Rest, [X,Acc] , Rs).
getRed([X|Rest], Acc, Rs) :- getRed(Rest, Acc, Rs).

getWhite([],Rs,Rs).    
getWhite([X|Rest], Acc, Rs) :- white(X), getWhite(Rest, [X,Acc], Rs).
getWhite([X|Rest], Acc, Rs) :- getWhite(Rest, Acc, Rs).

getBlue([],Rs,Rs).
getBlue([X|Rest], Acc, Rs) :- blue(X), getBlue(Rest, [X,Acc], Rs).    
getBlue([X|Rest], Acc, Rs) :- getBlue(Rest, Acc, Rs).

My output looks like this :

?- dutch([1,2,3],R).
R = [1, [], 2, [], 3, []]
R = [1, [], 2, []]
R = [1, [], 3, []]
R = [1, []]
R = [2, [], 3, []]
R = [3, []]
R = []

What I want is for it to look like this:

R = [1, 2, 3]

I've tried a few ways to force the output to what i want, but haven't been able to get anywhere close.

Edit: Looks like i can solve it by using a brute force solution of permuting all possible sets and evaluating whether the set is in "Dutch Flag" order. Is there a better solution though?

Answer 1

I see two errors in your code:

1) your terminal clauses getRed([],Rs,Rs), getWhite([],Rs,Rs), getBlue([],Rs,Rs) accepting, as value result, the empty list (when Rs is equal to []); I suggest to rewrite they as

getRed([],Rs,Rs)   :- Rs \= [].
getWhite([],Rs,Rs) :- Rs \= [].
getBlue([],Rs,Rs)  :- Rs \= [].

2) in the accepting clause (when X is the searched color), you add it in the accumulator with a comma when you should use a pipe ([X,Acc]; should be ([X|Acc]); I suggest to rewrite they as

getRed([X|Rest], Acc, Rs)   :- red(X),   getRed(Rest, [X|Acc], Rs).
getWhite([X|Rest], Acc, Rs) :- white(X), getWhite(Rest, [X|Acc] , Rs).
getBlue([X|Rest], Acc, Rs)  :- blue(X),  getBlue(Rest, [X|Acc], Rs).

Off Topic: There is no reason to append Red to an empty list; the result list (Y1) is Red itself; I suggest to semplify

append([], Red, Y1), append(Y1, White, Y2), append(Y2, Blue, Ys)

as follows

append(Red, White, Mid), append(Mid, Blue, Ys)

--- EDIT ---

Not sure about what do you exactly want but I suspect a third error in the third version clauses: when X isn't accumulated.

I think you should add a check to be sure that X isn't the searched color; I suggest to rewrite they as follows

getRed([X|Rest], Acc, Rs)   :- \+ red(X),   getRed(Rest, Acc, Rs).
getWhite([X|Rest], Acc, Rs) :- \+ white(X), getWhite(Rest, Acc, Rs).
getBlue([X|Rest], Acc, Rs)  :- \+ blue(X),  getBlue(Rest, Acc, Rs).

--- EDIT 2 ---

I don't see the need of an accumulator in your getRed/3, getWhite/3 and getBlue/3 clauses.

I propose a version with only 2 arguments

red(1).
white(2).
blue(3).

dutch(Xs,Ys):- 
    getRed(Xs, Red), getWhite(Xs, White), getBlue(Xs, Blue), 
    append(Red, White, Mid), append(Mid, Blue, Ys).

getRed([],[]).
getRed([X|Rest], [X|Rs]) :- red(X),    getRed(Rest, Rs).
getRed([X|Rest], Rs)     :- \+ red(X), getRed(Rest, Rs).

getWhite([],[]).
getWhite([X|Rest], [X|Rs]) :- white(X),    getWhite(Rest, Rs).
getWhite([X|Rest], Rs)     :- \+ white(X), getWhite(Rest, Rs).

getBlue([],[]).
getBlue([X|Rest], [X|Rs]) :- blue(X),    getBlue(Rest, Rs).
getBlue([X|Rest], Rs)     :- \+ blue(X), getBlue(Rest, Rs).